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

[Charles Galpin]

Thanks guys

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