[pgrouting-users] Evaluate swap

Tue Apr 11 09:15:25 PDT 2017

Hello Tom.

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.
This will help me flush my ideas in an organized manner, while trying to
understand the problem.
At the end I talk about your problem in particular.

Hope this helps

Regards
Vicky

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.

Then you have different flavours of VRP like:
CVRP
VRPPD
VRPTW
CVRPTW
VRPMT
OVRP
Each one has the own assumptions.

The Vehicle kind: truck, car, bicycle, air plane, tractor trailor, as a
start is irrelevant

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.

Traveling salesman problem
The inputs:
One Vehicle.
A set N of locations
PROBLEM
The Vehicles start and end the trip from the same location and visit all
locations, (no location is visited twice).
SOLVE
with any of "know" methods
http://www.math.uwaterloo.ca/tsp/
The problem is NP
  - with luck then its the global minimum
  - with brute force them N! (N factorial) seconds later get the global
minimum
RESULT
A route for the single truck that is a local minimum

VRP
The inputs:
A set of homogenous vehicles.
A set of locations
PROBLEM
The Vehicles start and end the trip from the same location and visit all
locations, (no location is visited twice).
SOLVE TRY 1
Distribute the locations among the Vehicles
Solve TSP for each Vehicle

Distributing the locations, was it a good distribution?, maybe not, so:

SOLVE TRY 2
While (I am not happy with the solution) {
  Distribute the locations among the Vehicles
  Solve TSP for each Vehicle of the fleet
}

lets refine a little:
SOLVE TRY 3
Distribute the locations the Vehicles
Solve TSP for each Vehicle of the fleet
While (I am not happy with the solution) {
  Re-distribute some of the locations among a subset of the Vehicles
  Solve TSP for each modified Vehicle of the fleet
}

more refining:
SOLVE TRY 3
Distribute the locations among Vehicles
Solve TSP for each Vehicle of the fleet
Now there is an initial solution
While (I am not happy with the solution) {
  Re-distribute "wisely" some of the locations among a subset of the
Vehicles
     - by inserting the location in the "best place" because the current
trip is already in a local minimum
  Re-Evaluate the whole trips of the fleet
}

Adding Time Windows
The Drivers shift defines the Vehicle's trip time windows: From what time
can the Vehicle depart, to what time can the Vehicle arrive
Remember they depart from the same location. well what actually I am doing
is that its not the same concept of location now.
Before: depot location location(x,y)
Now: depot location (x,y,open,close)
The before in terms of now: location(x,y,0,inf)

Time is involved now, before everything was distance. more information is
needed about the truck, like Speed.
When reading some papers the Speed is implicitly 1 and they don't bother
about the speed, actually pgr_gsoc_vrppdtw, does exactly that.

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:

while (The solution found is not valid)
  Distribute the locations among the Vehicles
  Solve TSP for each Vehicle of the fleet
}
Currently this is what I am trying to improve.

*So, talking about the trailer trucks of your problem using pgRouting:*
its an almost pick and delivery? Cargo goes from A to H:
- traliler 1 departs from A, arrives at B delivers cargo,  continues trip,
arrives at destination C
- trailer 2 departs from D, arrives at B pickups cargo, on arrival at E
delivers cargo, continues trip, arrives at destination F
- trailer 3 departs from G, arrves at E pickups cargo, continues trip,
arrives at destination H and unloads cargo

I say almost, because for example at point B:
- truck 1 arrives unload the cargo, after that it can leave
- truck 2 arrives loads the cargo, it can leave after that.

So data is needed somehow like this:
>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)

>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.

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.

Note that the time windows are given as data, they are not calculated.
What I mean by this, is that, the algorithm will try to find a suitable
trucks that can accomplish the time windows restriction.
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.
btw
- locations given by (x,y) and speed 1 is pgr_gsoc_vrppdtw
- working on: locations given by (x,y) and different speeds on vehicles (so
the vehicles are no homogeneous)
- working on: cost matrix is an input
  - if the cost matrix is a distance matrix, then trucks must have a speed
  - if the cost matrix is a time matrix, then trucks must have a factor (to
simulate different speeds)

(If being working on this topic since November any donation is appreciated.
http://pgrouting.org/)

On Tue, Apr 11, 2017 at 8:45 AM, Tom White <tom.white at gmail.com> wrote:

> Hello,
>
> 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.
>
> 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?
>
> Thank you,
>
> Tom White
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/pgrouting-users
>

-- 

Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany

Vicky Vergara
Operations Research

eMail: vicky at georepublic.de
Web: https://georepublic.info

Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20170411/9f423fa2/attachment-0001.html>