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