[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