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?
--
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
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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
--
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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users