In this tutorial we will use three different techniques to find the shortest path from
the start to and end locations. You will see the steps used to calculate routes by length,
routes by cost and routes by length and cost.
Shortest route calculations are done in FME using the shortestPathFinder transformer.
This transformer calculates the shortest path from the source node to a destination node
on a given road network. The output of the shortest route calculation will be a from
to line that defines the start and end of the path.
There are a few important things to keep in mind when using the shortestPathFinder.
First, the from to input port accepts line features but not quality features and second
the points on a from to line should match or snap to a coordinate on the roads network;
if they don't then you can use a parameter to manually set a search tolerance to the
nearest network to run the routes by length analysis.
Open FME workbench and create a new workspace.
Add an Esrishape file reader for the Route data set of the from to line.
Add a second reader for the AutoCAD DWG data set containing a road network.
In the add reader dialog click the option for single merged feature type; this will
add all of the AutoCAD data as a single layer.
Add a shortestPathFinder transformer to the canvas and connect the input ports.
Since the from to points on the line feature do not snap to the road network, we will adjust
the snapping tolerance .
Open the parameters dialog for the shortestPathFinder; change the parameter from to
and network snapping two yes and set a snapping tolerance of 200.
Add an inspector transformer to the path output port to see the output.
Go ahead and run the workspace.
Now let's review the output.
You can avoid traveling the wrong way down a one-way street using costs instead of distances.
To apply a cost to a route requires a clean data set where one way streets are tagged
with attributes and where streets have been digitized in the right direction of travel.
To run the routes by cost analysis open the example to workspace or continue along using
the previous example.
We will filter for roads that have been tagged as one-way streets by adding a tester transformer
to the canvas.
Open the tester parameters dialog. Set up a new test where the attribute for one way
equals Y. Add two attribute manager transformers, one connected to each of the tester output
ports; these will be used to assign the travel costs to road segments.
Open the parameters dialog for the first attribute manager, the one connected to tester passed
port. Add two new attributes forward cost and reverse cost. Set forward cost to a value
of one, to represent the correct direction to travel on a one-way street. Set the reverse
cost to a value of 9999, to represent the incorrect direction to travel on a one-way
street.
Next open the parameters dialog for the second attribute manager, the one connected to the
tester failed port. Add two new attributes forward cost and reverse cost. Set both attributes
to a value of one, since these are two-way streets where the travel cost is equal in
both directions.
Finally, we will modify the shortestPathFinder to use the travel cost weights we just assigned.
Open the parameters dialog change the cost type parameter from by length to by two attributes.
Set forwardcost as the forward cost attribute and perverse cost as the reverse cost attribute.
Go ahead and run the workspace.
Now let's review the output.
You will notice a difference between this path and the previous path in example 1. Example
1 was using one-way streets incorrectly where as example 2 avoids doing so.
Using only cost attributes to determine a route means that distance is no longer considered.
For instance, in our second example, there is no difference between a road of 1 m and
1 km provided it is not a one-way street. We will fix this using both length and cost
as parameters in the transformer.
To run the routes by length and cost analysis, open example 3 workspace or continue along
using the previous example.
Open the parameters dialog for the first attribute manager transformer. Next to the value for
the forward cost attribute click the drop-down arrow and select open arithmetic editor. In
the arithmetic editor add a multiplication symbol and double-click on length; this will
multiply the forwardcost value by the length of the road segment and give us a parameter
that takes into account both length and cost.
Repeat this step for the reverse cost attribute.
Open the second attribute manager and repeat the previous two steps.
Go ahead and run the workspace.
Now let's review the output.
Notice again the difference in results from examples one and two.
Some other considerations to keep in mind when using the shortestPathFinder are that
any number of from two lines can be passed into the shortestPathFinder for multiple
calculations on the same network.
The from two lines defines the start and end of the route but can also contain intermediate
points that the route must pass through.
A path can also be weighted by an attribute other than length for example each segment
of the network can be given a cost related to speed limits vehicle weight limits or another
factor.