Shortest Route Calculations with the ShortestPathFinder

Introduction

Shortest route calculations are done in FME using the ShortestPathFinder transformer. This transformer calculates the shortest path between a source and a destination node in 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.
• When implemented as the engine for 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. 

Data 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. 

Step-by-step Instructions

​​​​Example 1: Routes by Length

Follow these steps as an example of how to calculate the shortest route in a network. To follow along with this tutorial, please download the data from the article's File section.

1. Create a New Workspace

Open FME Workbench and create a blank workspace. 

2. Add an Autodesk AutoCAD DWG/DXF Reader

Add a 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, set the following:

• Format: Autodesk AutoCAD DWG/DXF
• Dataset: CompleteRoads.dwg
  • Click on the ellipses to navigate to the location of the file on your computer
• Workflow Options: Single Merged Feature Type

Click on Parameters.

Group Entities By Attribute Schema exposes the DWG attributes. In the parameters, set the following:

• Group Entities By: Attribute Schema

Click OK twice to finish adding the reader. 

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 and set the following:

• Format: Esri Shapefile
• Dataset: Route.shp
  • Click on the ellipses to navigate to the file location on your computer
• Workflow Options: Individual Feature Types

Click OK.

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. We are setting this parameter because the from-to endpoints may not sit exactly on the network.  In the parameters, set the following:

• Snapping:
  • From-To and Network Snapping: Yes
  • Snapping Tolerance: 200

5. Run Workspace

Connect an Inspector transformer to the ShortestPathFinder Path. 

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

After running the workspace, in Data Preview, you will see that 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 on a one-way street is avoided by using costs rather than 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 parameters, we will create two new attributes as follows:

• New Attribute: ForwardCost
  • Attribute Value: 1
• New Attribute: ReverseCost
  • Attribute Value: 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, set 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 set the following:

• Cost Type: By Two Attributes
• Forward Cost Attribute: ForwardCost
• Reverse Cost Attribute: ReverseCost
• Allow U-Turns: No

4. Run the Workspace

Run the workspace and view the output in Data 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, you need to use 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 ForwardCost 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. 

The expression should now be: 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 the Visual Preview should have a noticeably shorter path, since the distance is now included. 

Note that 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 open data made available by the City of Vancouver, British Columbia. It contains information licensed under the Open Government License - Vancouver.