VRP Pickup Delivery Problem - pgRouting/pgrouting GitHub Wiki

VRP-PDPTW : (Pickup and Delivery Problem with Time Windows)

Basic Idea :

VRP is an important problem in the fields of transportation, distribution and logistics. Often the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The pickup and delivery problem with time windows (PDPTW) is a generalization of the VRP which is concerned with the construction of optimal routes to satisfy transportation requests, each requiring both pickup and delivery under capacity, time window and precedence constraints.

http://www.dim.uchile.cl/~tcapelle/TESIS/NanryPDPTW.pdf

Tabu Search :

It uses a local or neighborhood search procedure to iteratively move from one potential solution x to an improved solution x' in the neighborhood of x, until some stopping criterion has been satisfied (generally, an attempt limit or a score threshold).

Steve's Notes and Implementation Ideas

The following ideas are taken from:

"Constructing initial solutions for the multiple vehicle pickup and delivery problem with time windows" by Manar Hosny and Christine Mumford, 2011

Algorithm 1: The Hill Climbing routing algorithm

1:  Given a route r
2:  repeat
3:      for (each possible pair of locations in r) do
4:          if (the latter location is more urgent in its upper time window bound) then
5:              swap the current two location in r to get a new route r'
6:              delta = cost(r') - cost(r)
7:              if (delta < 0) then
8:                  r = r'
9:  until (done) {stop when no improvement achieved in the previous pass}

Route Cost function

cost(r) {
    return w1*D(r) + w2*TWV(r) + w3*CV(r)
}

where:

w1+w2+w3 = 1.0
D(R)   = total route duration
TWV(r) = total number of time violations in the route
CV(r)  = total number of capacity violations in the route

and the w2 should impose the largest penalty on the route

Algorithm 2. The sequential construction

0.  Sort all requests by distance between depot and pickup location descending
1.  Let M = 0 {M is the number of vehicles used}
2.  repeat
3.      initialize an empty route r
4.      M = M + 1
5.      for (all unassigned requests) do
6.          get the next unassigned request i
7.          insert the request i at the end of the current route r
8.          call the HC routing heuristic to improve r
9.          if (r is a feasible route) then
10.             mark i as inserted
11.         else
12.             remove i from r
13. until (all requests have been inserted)

VRPDPTW

w1      - route duration weight
w2      - total number of time violation weight
w2      - total number of capacity violations

ORDER

oid     - uid of order (0 is depot)
pid     - pickup node id
did     - delivery node id
dist    - distance from pickup to depot
rid     - id of assigned route

ROUTE

id      - uid of the route
path[]  - ordered list of nodes
orders[]- list of order ids matching path node ids
updated - flag to indicate D, TWV and CV need to be updated
D       - route duration
TWV     - number of TW violations
CV      - number of capacity violations
---
appendOrder(order)
hillclimb()
update()
getCost()

NODE

nid     - node id
x       - x location
y       - y location
demand  - request size (+ for pickup, - for delivery)
twopen  - tw open
twclose - tw close
oid     - order id

The following ideas are taken from:

"Pickup and Delivery with Timw Windows: Algorithms and Test Case Generation" by Hoong Chuin LAU and Zhe LIANG

"Tabu Search: A Tutorial" by Fred Glover, 1990

"Chapter 6: Tabu Search" by Michel Gendreau and Jean-Yves Potvin

TABU Search

generate an initial solution, S0

S = S0;                     // set the working solution to S0
Cbest = S.getCost();        // cost of the best solution
Sbest = S0;                 // set the best solution to S0
T.clear();                  // clear the Tabu list
n = 0;                      // initialize the loop counter

while (true) {
    S = S.getBestOfNeighborhood();
    if (!S) break;

    if (S.getCost() < Cbest) {
        Sbest = S;
        Cbest = S.cost();
    }
    T.push_back(S);
    n++;
    if (n > maxIter) break;
}

report(Sbest, CBest);

TABU List representation

We need a simple way to create and manage our Tabu list. Some ideas are:

  1. put the order on the list and don't allow it to be moved again until it falls off the list or until is has aged N interations.
  2. ...

S.getBestOfNeighborhood()

  1. Find SPI move with highest PSC and implement move.
  2. If no more SPI move with positive PSC exists, find the best SPI move with BRSC and implement it. Goto 1.
  3. If no more SPI move with positive BRSC, find the SBR move with greatest saving and implement it. Goto 1.
  4. If no more SBR move with positive saving, find the best WRI move and implement it. Goto 1.
  5. If no WRI move found, stop.

NOTE: this probably means that the candidate is not on the TABU list.

Scoring the Moves

  • R1 - route to remove order

  • N1 - number of nodes in R1

  • R1P - updated R1 after removal

  • R2 - route to remove order

  • N2 - number of nodes in R1

  • R2P - updated R1 after removal

  • P - depot.tw_close + 1

Since the number of vehicles is more important than the total distance of the plan, the cost of each vehicle (route) is penalized with a coefficient P, which is set to be greater then the maximum possible total travel distance.

PSC - pure saving cost

PSC(R1, R2) = R1.cost() + R2.cost() - R1P.cost() - R2P.cost()

BRSC - Bias Route Saving Cost

BRSC(R1P, R2P) = PSC(R1, R2) + P/(N1/2) - P/((N2+2)/2)

Neighborhood moves

"Solving the pickup and delivery problem with time windows using reactive tabu search" by Nanry and Barnes, 1999 has a good detailed description of how to implement SPI, SBR and WRI algorithms mentioned below.

SPI - Single Pair Insertion

Move orders to another route with a bias toward reducing the total number of routes.

foreach order pair or cluster
    move order to another route
    hillclimb*
    select the best PSC or BRSC

SBR - Swapping Pair Between Routes

foreach pair of routes
    foreach order in each route
        swap the orders between the routes
        hillclimb*
        select the best PSC or BRSC

WRI - Within Route Insertion

  1. move one pickup and delivery pair in the route
  2. if the cost is reduced and all constraints are satified, goto 1
  3. when all such moves have been tried, move clusters consisting of two pairs
  4. eventually, move clusters consisting of three pairs

NOTES/QUESTIONS:

  1. I added hillclimb in these steps because it orders the nodes, I'm not sure if this is the fastest/best way to do this. For example, does this avoid looking at different ordering that may be valid?

  2. WRI seems to be just ordering of the nodes within the route. Is this still useful if we are using the hillclimb which is ordering the nodes?