[pgrouting-users] Shortest path with edge-parameters affecting the whole path

[Stephen Woodbridge]

Nicklas,

This is an interesting problem. The dynamic nature of it is more of a 
vehicle routing problem (VRP) than a simple path through the network 
problem like (Dijkstra).

To do what you want requires some level of back tracking or abandoning 
part of the current solution to move forward again.

Let me explain with a simple idea. Say your truck needs to cross a 
bridge and pickup a load of logs on an island. But the bridge has a 
weight restriction. If you cross the bridge when the trucks capacity is 
near the the weight limit of the bridge, then you are overweight on the 
return trip. This is a problem because the bridge is the ONLY 
access/egress to the island, so the truck is now stuck on the island and 
can not return without unloading to get below the limit.

In VRP, you are doing route optimization, so you can try this order of 
pickups and other order of pickups and keep the best. When you compute a 
path between any two nodes A to B, you can do things like check the the 
current load of the truck against the path and make it infinity if it is 
not viable, then the algorithm will be forced to look for a lower cost 
solution, like picking up the island load earlier in the path.

-Steve

On 12/14/2014 1:58 PM, Nicklas Avén wrote:
> On Sat, 2014-12-13 at 21:05 +0100, Nicklas Avén wrote:
>> Hallo list
>>
>> I have a question that I don't know if it is a question worth a
>> rtfm-answer or if it needs hacking the source to solve. I have tried to
>> find any obvious answers but failed.
>>
>> The problem is in my case connected to transportation of timber. All
>> roads have a classification of maximum aloud weight of the truck (or per
>> axle to be more accurate). The result is that the cost (in money) for a
>> transport is defined by the worst part of the path because that limits
>> how much timber the truck can take. That might be just a bridge or a
>> part of the road that is too weak to take a full loaded truck, which
>> gives a higher price for the whole transport.
>>
>> This classification is a property of the edges. So the shortest path
>> algorithms needs to carry the classification information about the, so
>> far worst road part, as a parameter in the cost calculations.
>>
>> Is there any feature in pgrouting handling this?
>>
>> I have read some about Dijkstra and as far as I understand it should be
>> quite straight forward to handle. What is needed is that not only the
>> cost is stored for each resulting vertexes but also the worst
>> classification to get to that vertex. Then that classification is
>> inherited along the path until an even worse classification is found.
>>
>> So, first: Is something like this already implemented?
>> Second, if not; Does the idea about how it could be solved make sense?
>>
>
> I realize my solution won't work. If, for instance in the beginning of
> the path there is a part ow the road that can take very little weight,
> that path might still be chosen since it in the beginning won't give
> that big effect, but might give big consequences later if there is a
> long way with better roads later.
>
> So I think the only way for me might be to do the shortest path
> calculations with all classes. So first do it with all edges, then with
> all edges but the worst and then all except the worst and the second
> worst and so on. At last I have to compare what path was the cheapest.
>
> Thanks
>
> Nicklas
>
>> Thanks
>>
>> Nicklas Avén
>>
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>