[pgrouting-users] The 2nd fastest route

Dave Potts dave.potts at pinan.co.uk
Tue Jan 10 03:08:58 EST 2012

Thanks Steve

I will see what I can make of the solutions for the K-Shortest paths.

Stephen Woodbridge wrote:
> 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
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users


More information about the Pgrouting-users mailing list