[pgrouting-users] The 2nd fastest route

[Stephen Woodbridge]

Hi Dave,

This is probably the solution that you are looking for:

http://algo2.iti.kit.edu/download/altgraph_tapas_ extended.pdf

If you are interested in having this implemented in pgRouting and can 
provide some funding, please contact me off list. If you want to have a 
go at it yourself, we would love to get anything you develop contributed 
back to pgRouting.

I just added the link to this pdf to a ticket for pgRouting:
https://github.com/pgRouting/pgrouting/issues/11

Thanks,
   -Steve

On 1/10/2012 3:08 AM, Dave Potts wrote:
> Thanks Steve
>
> I will see what I can make of the solutions for the K-Shortest paths.
>
> Dave.
> 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
>>
>
>