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

Nicklas Avén nicklas.aven at jordogskog.no
Sun Dec 14 12:02:58 PST 2014


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




More information about the Pgrouting-users mailing list