Skip to main content
Question

Shortest path along a network between multiple points

  • August 23, 2013
  • 3 replies
  • 242 views
A
Hi,

 

I have a network and a set of points I would like to visit. Is there a way to find the Shortest Path between the points? So the shortest path to visit all the points?

 

I know of the shortestpathfinder, but that transformer only determines the shortest path between two points...

 

 

Greetz,

 

Arno
This post is closed to further activity.
It may be an old question, an answered question, an implemented idea, or a notification-only post.
Please check post dates before relying on any information in a question or answer.
For follow-up or related questions, please post a new question or idea.
If there is a genuine update to be made, please contact us and request that the post is reopened.

3 replies

takashi
Celebrity
  • takashiCelebrity
  • August 23, 2013
Hi Amo,

 

 

If you are using FME 2013, try these steps:

 

1) Create a line connecting those points in the order of visiting (PointConnector).

 

2) Split the line into individual segments (Chopper: Mode = By Vertex, Maximum Vertices = 2).

 

3) Find shortest paths using the segments as FROM-TO (ShortestPathFinder).

 

  Takashi
Why not inspect features with Visual/Data Preview and Feature/Record Information before writing them into a destination dataset?
A
  • arno
  • Author
  • August 23, 2013
HI Takashi,

 

Thankx for the quick reponse. The problem is that I would like to calculate the order of the points to visit in an optimal route. So I can't create the line you suggest in 1)

 

 

Arno
takashi
Celebrity
  • takashiCelebrity
  • August 23, 2013
Hi Arno,

 

 

When the visiting order is undefined, it will be the famous "Travelling salesman problem".

 

http://en.wikipedia.org/wiki/Travelling_salesman_problem

 

Only if the number of points is limited, you can find the exact shortest path after calculating shortest paths of all the possible visiting orders.

 

Otherwise, you will have to implement an approximation algorithm being described in the link or other technical papers. It's too difficult to me...

 

 

Takashi
Why not inspect features with Visual/Data Preview and Feature/Record Information before writing them into a destination dataset?

Community Stats

32,730
Posts
124,163
Replies
41,223
Members
Terms & ConditionsAccessibility statement
A product of
Safe Software respectfully acknowledges that we live, learn and work on the traditional and unceded territories of the Kwantlen, Katzie, and Semiahmoo First Nations.