[pgrouting-users] The 2nd fastest route

Stephen Woodbridge woodbri at swoodbridge.com
Mon Jan 9 18:54:33 EST 2012


On 1/9/2012 5:35 PM, Dave Potts wrote:
>
> Is there anyway of getting of the TSP, Driving Distance calculation, etc
> to return  the 2nd or 3rd route instead of always the fastest way of get
> from source to target?
>

One algorithm for doing this is K-Shortest Paths. I think this applies 
to Dijkstra shoertest Path and maybe to A* Search. TSP and Driving 
distance do not really apply to this concept.

I don't think we have a K-Shortest paths solution implemented. And 
intuitively thinking about it I'm not sure that you would not get 
basically the same path with one nearly parallel path to some segment 
that cost slightly more substituted for the original.

It would be nice to be able to do something like what google does by 
presenting alternate route options. Part of what I think they might do 
is something like.

At the start and end include all segments in the network for some 
distance, and then only include the highways for the longer haul. Then 
if you ask for K-Shortest paths, you can ignore alternatives at the 
start and end and present a few alternatives over the longer haul 
highway routes.

But we don't have anything like that at the moment and we need a 
K-Shortest Path solution first.

-Steve


More information about the Pgrouting-users mailing list