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?
Thanks
Nicklas Avén
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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
Thank you Stephen
In my case things are a little simpler than in your example. Almost
always the truck goes to 1 place to get the whole load or at least to
one area with the same conditions.
So it is not really a "Traveling Sales person" problem.
Thanks
Nicklas
On Sun, 2014-12-14 at 14:34 -0500, Stephen Woodbridge wrote:
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@lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users@lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users