<div dir="ltr"><div><div><div>This is very helpful, thank you. <br><br></div>In this particular case, only the lateness of the load is a concern because of contractual obligations. Earliness is inefficient, but a different problem. <br><br>Planning and dispatch appear to be a VRPTW problem. If we have to use a speed we generally use 55 miles per hour or the speed limit of the road if known.</div><div><div><br></div></div>In the case of "rescues" there are only a few points to consider if you are evaluating just two trucks, the "problem" truck and the possible solution.<br><br></div><div>Unit 1 location.<br></div><div>Unit 1 destination.<br></div><div>Unit 2 (evaluated truck)<br></div><div>Unit 2 destination (there may not be a destination if the unit is not under dispatch)<br></div><div>Swap location<br><br></div><div>Output: lateness of both trucks on their swapped destinations, along with "out of route" miles and projected date and time of meeting for each unit. <br></div><br><div>The problem is to find an ideal replacement truck and the best place to meet and exchange trailers (out of a set of given locations). The obvious way is to do this evaluation for all trucks, but that is extremely time consuming.<br></div><div></div><div><br></div><div></div>Thank you for your input and all of your work, I've been following the pgRouting project for several years now and it is very useful.<br><div><div><div><div></div><br><div>Tom White<br></div><div><div><br><div class="gmail_quote"><div dir="ltr">On Tue, Apr 11, 2017 at 11:15 AM Vicky Vergara <<a href="mailto:vicky@georepublic.de">vicky@georepublic.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Hello Tom.<br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">I am the one working on the code of the VRP pick & delivery, and I will write a little about the pgr_gsoc_vrppdtw and how I changing it.<br class="gmail_msg">This will help me flush my ideas in an organized manner, while trying to understand the problem.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">At the end I talk about your problem in particular.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Hope this helps<br class="gmail_msg"><br class="gmail_msg"></div>Regards<br class="gmail_msg">Vicky<br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">The VRP problem makes some assumptions, like having a single depot, a
homogeneous fleet of vehicles, one route per vehicle. if you have one Vehicle then it becomes the TSP problem, which is NP-HARD optimization problem.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg">Then you have different flavours of VRP like:<br class="gmail_msg">CVRP<br class="gmail_msg">VRPPD<br class="gmail_msg">VRPTW<br class="gmail_msg">CVRPTW<br class="gmail_msg">VRPMT<br class="gmail_msg">OVRP<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Each one has the own assumptions.<br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">The Vehicle kind: truck, car, bicycle, air plane, tractor trailor, as a start is irrelevant<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg">The methods to solve any of them, can go from brute force search trying all possible permutations, or simulated annaeling, or tabu search and many more that I don't know about. I am doing sort a of tabu-search: get different initail solutions with optimize until It can't. <br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Traveling salesman problem<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">The inputs:<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">One Vehicle.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">A set N of locations<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">PROBLEM<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">The Vehicles start and end the trip from the same location and visit all locations, (no location is visited twice).<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">SOLVE<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">with any of "know" methods<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><a href="http://www.math.uwaterloo.ca/tsp/" class="gmail_msg" target="_blank">http://www.math.uwaterloo.ca/tsp/</a><br class="gmail_msg"></div>The problem is NP<br class="gmail_msg"> - with luck then its the global minimum<br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"> - with brute force them N! (N factorial) seconds later get the global minimum<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"></div></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">RESULT<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">A route for the single truck that is a local minimum<br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">VRP<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">The inputs:<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">A set of homogenous vehicles.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">A set of locations<br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">PROBLEM<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">The Vehicles start and end the trip from the same location and visit all locations, (no location is visited twice).<br class="gmail_msg"></div></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">SOLVE TRY 1<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Distribute the locations among the Vehicles<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Solve TSP for each Vehicle<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Distributing the locations, was it a good distribution?, maybe not, so:<br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg">SOLVE TRY 2<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">While (I am not happy with the solution) {<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"> Distribute the locations among the Vehicles<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"> Solve TSP for each Vehicle of the fleet<br class="gmail_msg">}<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"></div></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">lets refine a little:<br class="gmail_msg"></div>SOLVE TRY 3<br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Distribute the locations the Vehicles<br class="gmail_msg"></div>Solve TSP for each Vehicle of the fleet<br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">While (I am not happy with the solution) {<br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"> Re-distribute some of the locations among a subset of the Vehicles<br class="gmail_msg"></div> Solve TSP for each modified Vehicle of the fleet<br class="gmail_msg"></div>}<br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">more refining:<br class="gmail_msg"></div>SOLVE TRY 3<br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Distribute the locations among Vehicles<br class="gmail_msg"></div>Solve TSP for each Vehicle of the fleet<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Now there is an initial solution<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">While (I am not happy with the solution) {<br class="gmail_msg"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"> Re-distribute "wisely" some of the locations among a subset of the Vehicles<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"> - by inserting the location in the "best place" because the current trip is already in a local minimum<br class="gmail_msg"></div> Re-Evaluate the whole trips of the fleet<br class="gmail_msg"></div>}<br class="gmail_msg"><br class="gmail_msg"></div></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Adding Time Windows<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">The Drivers shift defines the Vehicle's trip time windows: From what time can the Vehicle depart, to what time can the Vehicle arrive<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Remember they depart from the same location. well what actually I am doing is that its not the same concept of location now.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Before: depot location location(x,y)<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Now: depot location (x,y,open,close)<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">The before in terms of now: location(x,y,0,inf)<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Time is involved now, before everything was distance. more information is needed about the truck, like Speed.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">When reading some papers the Speed is implicitly 1 and they don't bother about the speed, actually pgr_gsoc_vrppdtw, does exactly that.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg">Adding time windows will affect the code, as a start TSP, keeping track of the time is needed now, and the "solution" found might be invalid because it can make the truck arrive time to the destination late. So the way to distribute the locations becomes difficult, consider that It will become NP-HARD, because to get the initial solution:<br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">while (The solution found is not valid)<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"> Distribute the locations among the Vehicles<br class="gmail_msg"></div> Solve TSP for each Vehicle of the fleet<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">}<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Currently this is what I am trying to improve.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"><br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><b class="gmail_msg">So, talking about the trailer trucks of your problem using pgRouting:</b><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">its an almost pick and delivery? Cargo goes from A to H:<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">- traliler 1 departs from A, arrives at B delivers cargo, continues trip, arrives at destination C<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">- trailer 2 departs from D, arrives at B pickups cargo, on arrival at E delivers cargo, continues trip, arrives at destination F<br class="gmail_msg">- trailer 3 departs from G, arrves at E pickups cargo, continues trip, arrives at destination H and unloads cargo<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">I say almost, because for example at point B:<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">- truck 1 arrives unload the cargo, after that it can leave<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">- truck 2 arrives loads the cargo, it can leave after that.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg">So data is needed somehow like this:<br class="gmail_msg">From the point of view of truck 1, the cargo at point B might have a time window [8:15, 8:30] with a service time of 0:02 minutes (time to unload the cargo)<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg">From point of view of truck 2 the cargo at point B has a time window [8:10, 8:35] with a service time of 0:19, that is, make sure it arrives before the one that unloads, make sure it leaves after the one that unloaded, and the 19 minutes is the time window length of the possible arrival time of the cargo + 2 minutes of uloading of the other truck + 2 minutes of loading to this truck.<br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">So the same cargo is a different cargo (different location, different time, different truck, different time window) the only similarity might be that is the same weight.<br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">Note that the time windows are given as data, they are not calculated.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">What I mean by this, is that, the algorithm will try to find a suitable trucks that can accomplish the time windows restriction.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">What the algorithm will not do is that based on the arrival time of the cargo, change the time windows of thcost matrixe departure time of another cargo.<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">btw <br class="gmail_msg">- locations given by (x,y) and speed 1 is pgr_gsoc_vrppdtw<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif">- working on: locations given by (x,y) and different speeds on vehicles (so the vehicles are no homogeneous)<br class="gmail_msg"></div><div style="font-family:arial,helvetica,sans-serif" class="gmail_default gmail_msg">- working on: cost matrix is an input <br class="gmail_msg"> - if the cost matrix is a distance matrix, then trucks must have a speed<br class="gmail_msg"> - if the cost matrix is a time matrix, then trucks must have a factor (to simulate different speeds)<br class="gmail_msg"><br class="gmail_msg"><br class="gmail_msg"></div><div style="font-family:arial,helvetica,sans-serif" class="gmail_default gmail_msg">(If being working on this topic since November any donation is appreciated. <a href="http://pgrouting.org/" class="gmail_msg" target="_blank">http://pgrouting.org/</a>)<br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"></div><div class="gmail_default gmail_msg" style="font-family:arial,helvetica,sans-serif"><br class="gmail_msg"></div></div><div class="gmail_extra gmail_msg"><br class="gmail_msg"><div class="gmail_quote gmail_msg"></div></div><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg">On Tue, Apr 11, 2017 at 8:45 AM, Tom White <span dir="ltr" class="gmail_msg"><<a href="mailto:tom.white@gmail.com" class="gmail_msg" target="_blank">tom.white@gmail.com</a>></span> wrote:<br class="gmail_msg"></div></div><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg">Hello,<br class="gmail_msg"><br class="gmail_msg"></div>I am trying to figure out a way to evaluate a swap between two vehicles. Tractor-trailers can meet and swap trailers and continue to each other's destinations. The advantage lies in drivable hours - drivers are limited to a certain number of driving hours and are required to take breaks of varying lengths. One truck may have enough hours available to prevent a load from being late. One truck may even have two drivers.<br class="gmail_msg"><br class="gmail_msg"></div>Does anyone know of any previous work in this area, either open source or academic research? Does anybody have an idea how this could be solved with pgRouting tools?<br class="gmail_msg"><br class="gmail_msg"></div>Thank you,<br class="gmail_msg"><br class="gmail_msg"></div>Tom White<br class="gmail_msg"></div>
<br class="gmail_msg"></blockquote></div></div><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">_______________________________________________<br class="gmail_msg">
Pgrouting-users mailing list<br class="gmail_msg">
<a href="mailto:Pgrouting-users@lists.osgeo.org" class="gmail_msg" target="_blank">Pgrouting-users@lists.osgeo.org</a><br class="gmail_msg">
<a href="https://lists.osgeo.org/mailman/listinfo/pgrouting-users" rel="noreferrer" class="gmail_msg" target="_blank">https://lists.osgeo.org/mailman/listinfo/pgrouting-users</a><br class="gmail_msg"></blockquote></div></div><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"></blockquote></div><br class="gmail_msg"><br class="gmail_msg" clear="all"><br class="gmail_msg">-- <br class="gmail_msg"><div class="m_-6307411087117139057gmail_signature gmail_msg" data-smartmail="gmail_signature"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><pre class="gmail_msg">Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany
Vicky Vergara
Operations Research
eMail: vicky@<a href="http://georepublic.de" class="gmail_msg" target="_blank">georepublic.de</a>
Web: <a href="https://georepublic.info" class="gmail_msg" target="_blank">https://georepublic.info</a>
Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9
Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
<span class="gmail_msg"></span></pre></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</div>
_______________________________________________<br class="gmail_msg">
Pgrouting-users mailing list<br class="gmail_msg">
<a href="mailto:Pgrouting-users@lists.osgeo.org" class="gmail_msg" target="_blank">Pgrouting-users@lists.osgeo.org</a><br class="gmail_msg">
<a href="https://lists.osgeo.org/mailman/listinfo/pgrouting-users" rel="noreferrer" class="gmail_msg" target="_blank">https://lists.osgeo.org/mailman/listinfo/pgrouting-users</a></blockquote></div></div></div></div></div></div></div>