Network Analyst and ArcPy: finding k-alternate path

Using ArcGIS Network Analyst extension, it is possible to find out the best route between a pair of points (best is defined in terms of the impedance — it can the shortest or the fastest route, for instance). However, you might like having multiple alternatives to the best route which one usually refers to as the K shortest paths.

The K shortest path routing algorithm is

an extension algorithm of the shortest path routing algorithm in a given network.

When solving a route between a pair of points, Network Analyst finds only a single route that is considered to be the best. That is, one cannot get a number of routes while solving a Route layer. However, this is something many of you have seen when routing using Google Maps or HERE, for instance.

I got curious and have started searching for this algorithm implementation using ArcGIS Network Analyst. I’ve found a very useful Esri forums post by a former Esri Network Analyst product engineer Michael Rice who wrote that

At the ArcGIS 10 release, you can approximate a k-shortest paths solver using the enhanced barrier features. Additionally, for line and polygon barriers, instead of just restricting the parts of the network that are covered by their geometry, you can opt to simply scale the costs of the parts of the network covered by the geometry.

Therefore, to approximate k-shortest paths, you can do the following:

1. Solve the route to get the best path
2. Take the current best path and load it as a polyline barrier with a scale factor of x
3. Repeat

Note that by scaling the polyline barrier instead of restricting it, this will allow
the next path to reuse some of the same edges along the previous path if necessary, but at a higher cost than in previous paths. Also note that when multiple line barriers apply to the same edge, the final scale factor for the cost of that edge becomes the product of their individual scale factors. For example, if there are two line barriers applied to some edge with scale factors x and y, respectively, the scaled cost of traversing that edge will be x*y*originalEdgeCost.

This means that the more an edge is reused across different paths, the less likely it will be to be used in any subsequent paths as the process discussed above continues to iterate.

This approach will technically not guarantee a true k-shortest path solve, so we must
be careful not to incorrectly label it as such. As I said previously, it is merely an
approximation for this concept. A more appropriate name might be to call this a
k-alternate path approach (as opposed to shortest). The alternate paths you get will
ultimately depend on the scale factors you use.

I’ve written a Python add-in that given a number of alternative routes to find, will generate a new feature layer with a number of routes solved. I have used the workflow Michael described loading a solved route as a polyline barrier for all subsequent solve operations. You can use this code when you want to generate multiple alternate routes. This is how it looks in ArcMap.

2017-04-27 15_12_00-Routing.mxd - ArcMap

The Python code to be used to make the add-in:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s