vrpdptw.txt

# 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?