Find the shortest path visiting all the given points

If the order of visiting points is defined, these transformers can be used to do that.
PointConnector: create a line connecting the points in the order of visiting.
Chopper: split the line into individual line segments.
ShortestPathFinder: find shortest paths for all the segments (FROM-TO lines).
* FME 2013+

It's not necessary to chop the line into individual line segments.
ShortestPathFinder help:
"It can contain intermediate stops before the final destination. For example, a FROM-TO line may be used to find the path from A to B to C to D. This can also be read as “the path from A to D that also passes through B and C.”

It's not so difficult, I recently created a practical workspace based on this approach for an actual project.
But when the the order of visiting is unknown - in other words, when you need to find the optimal route which visits all the given points, it will be the famous "Travelling salesman problem". Several approximation algorithms have been invented to solve the problem, however, FME currently doesn't support them.
> Community: Shortest path along a network between multiple points

No comments:

Post a Comment