[pgrouting-users] Alternate routes (but same cost mechanism)

[Stephen Woodbridge]

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.

-Steve