16 Capacitated Vehicle Routing Problem (examp-cvrp)

Run LPL Code  ,  PDF Document

Another example of a permutation problem is the capacitated vehicle routing problem (cvrp). In this problem, we are looking for a “partitioned permutation”. A partitioned permutation is a permutation partitioned into subsequences. For example, the permutation {2, 3, 4, 1, 9, 8, 5, 6, 7, 10} could be partitioned into 3 subsequences as follows:

{{2,3, 4},{1,9,8,5}, {6,7,10}}

The first subsequence is {2, 3, 4}, the second is {1, 9, 8, 5}, etc. this is exactly what is needed for the capacitated vehicle routing problem.

Problem

A fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. An concrete application is given in cvrp. The models cvrp-1, cvrp-2, and cvrp-3 give MIP-formulations of the problem. These formulations are explained in my book Case Studies I.

To interpret this problem as a “partitioned permutation” problem is easy: Starting at a depot, the first vehicle visits the customers in the first subsequence and returns to the depot, the second vehicle, also starting from the depot, visits the customers in the second subsequence and returns to the depot, etc. Note that the depot is not part of the sequences itself.

Modeling Steps

Let i,j I = {1,,n - 1} be a set of customer locations (n is the number of locations including the warehouse (or the depot) and let k K = {1,,m} be a set of trucks. Let the capacity of each truck be CA, and let the demand quantity to deliver to a customer i be demi. Furthermore, the distance between two customer i and j is di,j. Finally, the distance from the warehouse – the depot from where the trucks start – to each customer i is dwi.

The customers are enumerated with integers from 1 to n - 1. If there were one single truck (that must visits all customers), every permutation sequence of the numbers 1 to n - 1 would define a legal tour. Since we have m trucks, to each truck a sequence of a subset of 1 to n - 1 must be assigned. Hence, each truck starts at the depot, visiting a (disjoint) subset of customers in a given order and returns to the depot.

The variables can now be formulated as a “partitioned permutation”. In LPL, we can declare these partitioned permutation with a (sparse) permutation variable xk,i [1n - 1]. For example, for the example above we have :

    (                                   )
      2  3   4   -  -   -   -  -   -   -
x = ( 1  9   8   5  -   -   -  -   -   -)
      6  7  10   -  -   -   -  -   -   -

Note that the two-dimensional table is sparse – it only contains n- 1 entries. The symbol “-“ (dash) means: no entry. Hence, x1,1 = 2 means that the customer 2 is visited by the truck 1 right after the depot, x1,2 = 3 means that the next customer (after 2) is 3, etc.

The unique constraint that must hold for the partitioned permutation is the capacity of the trucks: each subset sequence must be chosen in such a way that the capacity of the truck is larger than the cumulated demand of the customers that it visits – note, the variables xk,i are used as indexes as well as in the condition of the summation:

∑
    demxk,i ≤  CA    forall k ∈ K
i|xk,i

We want to minimize the total travel distance of the trucks. Let cck be the size of the subset k (the numbers of customers that the truck k visits). (In the example above ck = {3, 4, 3}.) Of course, these numbers is variable and cannot be given in advance! Let routeDistancesk be the (unknown) travel distance of truck k, then we want to minimize the total distances:

     ∑
min     routeDistancesk
      k

where

                    ∑
routeDistancesk  =       dxk,i-1,xk,i + if(cck > 0,dwxk,1 + dwxk,cck  forall k ∈ K
                   i∈2..cck

The term dwxk,1 denotes the distance of the truck k from the depot to the first customer, and dwxk,cc k is the distance of the truck tour k from the last customer to the depot, dxk,i-1,xk,i is the distance from a customer to the next, and i2..cck sums that distances of a tour k.

As a variant we may also minimize, in a first round, the number of trucks used – this is added as a comment in the code:


Listing 15: The Main Model implemented in LPL [10]
model cvrp "Capacitated Vehicle Routing Problem"; 
  set i,j  "customers"; 
      k    "trucks"; 
  parameter 
      d{i,j} "distances"; 
      dw{i}  "distance from/to the warehouse"; 
      dem{i} "demand"; 
      CA     "truck capacity"; 
  alldiff x{k,i} 'partition'; 
  expression 
    cc{k}: count{i} x; 
    trucksUsed{k}: cc[k] > 0; 
    routeDistances{k}: sum{i in 2..cc} d[x[k,i-1],x[k,i]] 
       + if(cc[k]>0, dw[x[k,1]] + dw[x[k,cc[k]]]); 
    nbTrucksUsed: sum{k} trucksUsed[k]; 
    totalDistance: sum{k} routeDistances[k]; 
  constraint CAP{k}: sum{i|x} dem[x[k,i]] <= CA; 
  --minimize obj1: nbTrucksUsed; 
  minimize obj2: totalDistance; 
end

Further Comments

The question is now what solver can solve this kind of model! I developed a simple Tabu-search solver that can deliver near optimal solution for small simple permutation problems, but not for partitioned permutation problems. However, there is a powerful commercial solver called LocalSolver that can find near optimal solutions to large problems. LPL contains an (experimental) interface to that solver.

Solution

The LPL data code reads the “A-n32-k5.vrp” file from the Augerat et al. Set A instances.


Listing 16: The Data Model
  model data; 
    set h; //h is i plus 1, 1 is depot (warehouse) 
    parameter de{h}; n; m; X{h}; Y{h}; string typ; dum; 
    Read('A-n32-k5.vrp,%1;-1:DIMENSION',dum,dum,n); 
    --Read('A-n45-k6.vrp,%1;-1:DIMENSION',dum,dum,n); 
    Read('%1;-1:EDGE_WEIGHT_TYPE',dum,dum,typ); 
    if typ<>'EUC_2D' then Write('Only EUC_2D is supported' n'); return 0; end; 
    Read('%1;-1:CAPACITY',dum,dum,CA); 
    Read{h}('%1:NODE_COORD_SECTION:DEMAND_SECTION', dum,X,Y); 
    Read{h}('%1:DEMAND_SECTION:DEPOT_SECTION', dum,de); 
    m:=Ceil(sum{h} de/CA); 
    k:=1..m; 
    i:=1..n-1; 
    d{i,j}:=Round(Sqrt((X[i+1]-X[j+1])^2+(Y[i+1]-Y[j+1])^2)); 
    dem{i}:=de[i+1]; 
    dw{i}:=Round(Sqrt((X[i+1]-X[1])^2+(Y[i+1]-Y[1])^2)); 
  end

The LocalSolver finds the optimal solution (see 6) after 25secs


PIC

Figure 6: Optimal Solution to the “A-n32-k5.vrp” Instance