VRP Pickup Delivery Problem
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
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).
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
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}
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
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)
w1 - route duration weight
w2 - total number of time violation weight
w2 - total number of capacity violations
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
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()
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
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);
We need a simple way to create and manage our Tabu list. Some ideas are:
- 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.
- ...
- Find SPI move with highest PSC and implement move.
- If no more SPI move with positive PSC exists, find the best SPI move with BRSC and implement it. Goto 1.
- If no more SPI move with positive BRSC, find the SBR move with greatest saving and implement it. Goto 1.
- If no more SBR move with positive saving, find the best WRI move and implement it. Goto 1.
- If no WRI move found, stop.
NOTE: this probably means that the candidate is not on the TABU list.
-
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(R1, R2) = R1.cost() + R2.cost() - R1P.cost() - R2P.cost()
BRSC(R1P, R2P) = PSC(R1, R2) + P/(N1/2) - P/((N2+2)/2)
"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.
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
foreach pair of routes
foreach order in each route
swap the orders between the routes
hillclimb*
select the best PSC or BRSC
- move one pickup and delivery pair in the route
- if the cost is reduced and all constraints are satified, goto 1
- when all such moves have been tried, move clusters consisting of two pairs
- eventually, move clusters consisting of three pairs
-
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?
-
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?
