I have what I consider a bit of a crazy requirement for routing. In addition to being able to influence the route with rules like shortest path, or fastest, etc. I need to also be able to offer alternative routes within a specific mode. So say they want to favor or avoid highways, I need to be able to give them a few alternatives as well.
Does anyone have any thoughts on this? I'm pretty sure even google is doing something like showing you fastest versus shortest, or some other weighting between the options they give in their alternate routes.
I have not played with any of the routing algorithms other than Dijkstra (for some reason I could never get A* to work for me when I first looked at pgRouting but will revisit it) so I am not sure if I can expect them to give different results (or with shooting star even), given the same weighting.
The only think I can think of is to throw "blocks" or penalty wieghts in at random locations (or somehow come up with a clever way to pick them) and re-route and take the new paths, but I suspect this will be very crude, and not useful anyway.
On Tue, Sep 6, 2011 at 11:52 PM, Charles Galpin <cgalpin@lhsw.com> wrote:
I have what I consider a bit of a crazy requirement for routing. In addition to being able to influence the route with rules like shortest path, or fastest, etc. I need to also be able to offer alternative routes within a specific mode. So say they want to favor or avoid highways, I need to be able to give them a few alternatives as well.
Hi Charles,
If you’re looking for something like the second shortest or third shortest path, etc., this is called k-shortest path.
But it’s not implemented in pgRouting (yet): http://www.pgrouting.org/rfc/rfc-04.html
Maybe someone wants to do this or want to sponsor the development.
Does anyone have any thoughts on this? I’m pretty sure even google is doing something like showing you fastest versus shortest, or some other weighting between the options they give in their alternate routes.
I guess that, as you say, they use different weights for their alternative routes.
Different routing algorithms shouldn’t give you a different result … then something might be wrong with them
Daniel
I have not played with any of the routing algorithms other than Dijkstra (for some reason I could never get A* to work for me when I first looked at pgRouting but will revisit it) so I am not sure if I can expect them to give different results (or with shooting star even), given the same weighting.
The only think I can think of is to throw “blocks” or penalty wieghts in at random locations (or somehow come up with a clever way to pick them) and re-route and take the new paths, but I suspect this will be very crude, and not useful anyway.
I have what I consider a bit of a crazy requirement for routing. In
addition to being able to influence the route with rules like
shortest path, or fastest, etc. I need to also be able to offer
alternative routes within a specific mode. So say they want to favor
or avoid highways, I need to be able to give them a few alternatives
as well.
Does anyone have any thoughts on this? I'm pretty sure even google
is doing something like showing you fastest versus shortest, or some
other weighting between the options they give in their alternate
routes.
I have not played with any of the routing algorithms other than
Dijkstra (for some reason I could never get A* to work for me when I
first looked at pgRouting but will revisit it) so I am not sure if I
can expect them to give different results (or with shooting star
even), given the same weighting.
The only think I can think of is to throw "blocks" or penalty wieghts
in at random locations (or somehow come up with a clever way to pick
them) and re-route and take the new paths, but I suspect this will be
very crude, and not useful anyway.
One way as Daniel mentioned is k-shortest paths. If all you want to do is say change the preference for highways or fastest time vs shortest path, then I would compute multiple cost columns where you weight the cost based on some factor as to shortest time versus shortest path. Or multiple the cost of using a highway by a factor. So if a highway segment cost X to traverse it, and you want to avoid highways, then you might say the cost of highway segments is X*F where F is you avoidance factor. If F=2.0, then you would be saying I will only take a highway route if it costs me more then 2X the cost to avoid it.
You can do this be modifying the plpgsql wrappers that pass the segments and costs to the lowlevel routing code.
Yes I'm good on adjusting the weights, and k-shortest paths is what I am after. I'm going to take a look at the google project that RFC mentions since they have a java implementation and we may be able to use that instead (since this service is written in Java).
Thanks,
charles
On Sep 6, 2011, at 1:52 PM, Stephen Woodbridge wrote:
On 9/6/2011 10:52 AM, Charles Galpin wrote:
I have what I consider a bit of a crazy requirement for routing. In
addition to being able to influence the route with rules like
shortest path, or fastest, etc. I need to also be able to offer
alternative routes within a specific mode. So say they want to favor
or avoid highways, I need to be able to give them a few alternatives
as well.
Does anyone have any thoughts on this? I'm pretty sure even google
is doing something like showing you fastest versus shortest, or some
other weighting between the options they give in their alternate
routes.
I have not played with any of the routing algorithms other than
Dijkstra (for some reason I could never get A* to work for me when I
first looked at pgRouting but will revisit it) so I am not sure if I
can expect them to give different results (or with shooting star
even), given the same weighting.
The only think I can think of is to throw "blocks" or penalty wieghts
in at random locations (or somehow come up with a clever way to pick
them) and re-route and take the new paths, but I suspect this will be
very crude, and not useful anyway.
One way as Daniel mentioned is k-shortest paths. If all you want to do is say change the preference for highways or fastest time vs shortest path, then I would compute multiple cost columns where you weight the cost based on some factor as to shortest time versus shortest path. Or multiple the cost of using a highway by a factor. So if a highway segment cost X to traverse it, and you want to avoid highways, then you might say the cost of highway segments is X*F where F is you avoidance factor. If F=2.0, then you would be saying I will only take a highway route if it costs me more then 2X the cost to avoid it.
You can do this be modifying the plpgsql wrappers that pass the segments and costs to the lowlevel routing code.
