Shortest Route Calculations with the ShortestPathFinder

Introduction

Shortest route calculations are done in FME using the ShortestPathFinder transformer. This transformer calculates the shortest path from a source node to a destination node on a given network.

Here, for example, a user is finding the shortest path between the start/end points of a given route, using a network of lines:

A from-to line defines the start and end of the route. Any number of from-to lines can be passed into the ShortestPathFinder for multiple calculations on the same network.

There are some simple variations and issues to be aware of:

Variations

• A path can be weighted by an attribute other than length; for example, each segment of the network can be given a "cost" related to (for example) speed limits or vehicle weight limits.
• The from-to line defines the start and end of the route, but can also contain intermediate points that the route must pass through.
• Implemented as the engine to a web service, the from-to points could be defined by a user in a web mapping tool.

Cautions

• The From-To input port accepts line features, not point features.
• The points on a from-to line should match a coordinate on the network. If they do not, then a parameter is available to set a permitted tolerance.

Video

This video was filmed with an older version of FME. The user interface may look different, but the concepts are the same. 

Step-by-step Instructions

Source
The first source dataset is the complete road network in an AutoCAD DWG format for the City of Vancouver. 


The second source dataset is an Esri Shapefile containing a line from point A to point B. 

​​​​​​​

Example 1: Routes by Length

Follow these steps as an example of how to calculate the shortest route in a network.

1. Create a New Workspace
Open FME Workbench and create a blank workspace. 

 
2. Add an Autodesk AutoCAD DWG/DXF Reader
Add an Autodesk AutoCAD DWG/DXF reader to the canvas by clicking on the Reader button on the top menu bar or by going to Readers > Add Reader. In the Add Reader dialog, select Autodesk AutoCAD DWG/DXF as the Format, then for Dataset, browse to the CompleteRoads.dwg dataset, which is available for download from the Files section on this article. Change the Workflow Options to Single Merged Feature Type, then open the Parameters. 

 
In the parameters, change Group Entities By to Attribute Schema, then click OK twice to finish adding the reader. Group Entities By Attribute Schema exposes the DWG attributes. 


In the Select Feature Type dialog, ensure all of the layers are selected, then click OK. 

 
3. Add an Esri Shapefile Reader
Add another reader to the canvas. This time set the Format to Esri Shapefile, then browse to the route.shp dataset. You may need to switch the Workflow Options back to Individual Feature Types. 

 
4. Find the Shortest Path
Click on the <ALL>  reader feature type to select it.  Then add a ShortestPathFinder transformer to the canvas by typing “ShortestPathFinder” to bring up the list of FME Transformers in the Quick Add Search. Select the ShortestPathFinder from the list of Transformers by double-clicking or by using the arrow keys and the Enter key to add it. 

 
Click and drag a connection line from the Route reader feature type to the From-To input port on the ShortestPathFinder. 


Double-click on the ShortestPathFinder to open the parameters. In the parameters, change From-To and Network Snapping to Yes, then set the Snapping Tolerance to 200. We are setting this parameter because the from-to end points may not sit exactly on the network. 


5. Run Workspace
Connect an Inspector transformer to the ShortestPathFinder Path. 


Run the workspace by clicking on the Run button on the top toolbar, or by using Run > Run Workspace on the top menu bar. 

 
After running the workspace, in Visual Preview,  will see a route has been created following the road network. 

 
6. Save Workspace
Save the workspace. This workspace will be used in Example 2. 
 

Example 2: Routes by Cost

Traveling the wrong way along a one-way street is avoided by using costs instead of distance. It is necessary for the one-way streets to be tagged (usually with an attribute) and for their direction (from the first coordinate to the last) to match the permitted direction of travel.
Follow these steps as an example of how to calculate the shortest route in a network and avoid traveling the wrong way along a one-way street.
 
1. Find One Way Streets
Continue in the same workspace from Example 1. Add a Tester transformer between the <All> reader feature type and the ShortestPathFinder. 

 
In the parameters, set the test to OneWay = Y

 
2. Create ForwardCost and ReverseCost
Next, we will define ForwardCost and ReverseCost. Add an AttributeCreator to the canvas and connect it between the Tester Passed output port and the ShortestPathFinder Network input port. 

 
In the parameter, create a new attribute called ForwardCost and assign it a value of 1. Next, create an attribute called ReverseCost and assign it a value of 9999. 1 represents the correct direction on a one-way street, and 9999 represents the incorrect direction. 
 

Duplicate the AttributeCreator (ctrl+d/cmd+d) and connect the AttributeCreator_2 to the Tester Failed output port and the ShortestPathFinder Network input port. 

 
In the parameters, change the value of ReverseCost to 1. Both attributes with a value of 1 represent two-way streets where the cost is equal in both directions.
 
 
3. Change Cost Type
Open the ShortestPathFinder parameters and change the Cost Type to Two Attributes. Next, set the Forward Cost Attribute to ForwardCost, and the Reverse Cost Attribute to ReverseCost. Finally, set Allow U-Turns to No. 
 

4. Run the Workspace
Run the workspace and view the output in Visual Preview. Notice the difference between this output and example 1. Example 1 was using one-way streets incorrectly, whereas example 2 avoids doing so.

 
5. Save Workspace
Save the workspace. This workspace will be used in Example 3. 
 

Example 3: Routes by Length AND Cost

Using only cost attributes to determine a route means that distance is no longer considered. For instance, in example 2 there is no difference between a road of 100 meters and 100 kilometers, provided it is not a one-way street. To solve that requires the use of both length AND cost.
Follow these steps as an example of how to calculate the shortest route in a network, applying both costs and length.
 
1. Use Distance 
Continue in the same workspace from Example 2. Open the AttributeCreator parameters and click on the drop-down arrow for the FowardCost value, then select Open Arithmetic Editor. 
 

In the Arithmetic Editor, after 1 add an asterisk ( * ) to indicate multiplication. Next, expand FME Feature Functions on the side and double-click on Length. The expression should now be:

1*@Length()

Click OK and repeat the same step with the ReverseCost value. 

9999*@Length()

 

Copy the ForwardCost value, close the AttributeCreator, then open the AttributeCreator_2. For both values, paste in:

@Evaluate(1*@Length())

@Evaluate tells FME that it is an expression, not plain text. 

 
2. Run Workspace
Run the workspace once more. The output in Visual Preview should have a noticeably shorter path since the distance is now considered. 

 
Note that the method of multiplying the cost by distance is only one example of what might be used. You could, for instance, weight the costs higher by multiplying the cost by half the distance (cost * (distance/2))

Data Attribution

The data used here originates from data made available by the City of Vancouver, British Columbia. It contains information licensed under the Open Government License - Vancouver.