topic Re: K-th best route solution in Network Analyst in Transportation Questions

K-th best route solution in Network Analyst

BrianFrizzelle — Tue, 11 May 2010 11:42:19 GMT

I have an application where I need to calculate several different possible routes between origin and destination points on a road network. The best option that I can come up with at this time is what is commonly called the kth best route, which would return the shortest route, the second shortest, third shortest, etc. I've searched around on the web for a solution to this and have come up empty.

Does anyone have any experience with this, or do you know if it is possible to extract this information out of Network Analyst? Any help you can provide would be most appreciated.

Brian Frizzelle

Re: K-th best route solution in Network Analyst

MichaelRice — Wed, 12 May 2010 14:57:46 GMT

At the 10 release, you can approximate a k-shortest paths solver using the enhanced barrier features that will be available in Network Analyst. Specifically, all Network Analyst solvers at 10 will support point, line, and polygon barriers. 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 (this is essentially the same as what Bill suggests above, but I am providing specific steps using the newly-supported barrier functionality):

Solve the route to get the best path

Take the current best path and load it as a polyline barrier with a scale factor of x

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. Does this make sense?

Let me know if there are any questions.

Re: K-th best route solution in Network Analyst

MichaelRice — Wed, 12 May 2010 19:13:19 GMT

Also, just to be absolutely clear on this: 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. The good thing, however, is that it is therefore a parameterizable approach, which can be tuned to the user's needs.