Three-index Flow Formulation (cvrp-3)

Run LPL Code  ,  PDF Document

Problem

A variant of the capacitated vehicle routing problem implementation is to use a three-index version in which the binary variables are extended with the vehicle index. This has the advantage that the variables can directly be used to identify the vehicles. A disadvantage is that the number of variables is larger. Implement this idea as a mathematical model.

Modeling Steps

This model is similar to model cvrp-2, but the x binaries have three indexes. An additional index h H = {1,,K} for the vehicles is used.

  1. First, we introduce a binary variable xi,j,h with is 1 if an edge is traversed by vehicle h, otherwise it is 0. Another binary is yi,h defining which vehicle visits which customer.

  2. The first two constraints A1 and A2 (below) say that the number of vehicles visiting a customer is 1 and leaving the depot is K.

  3. Constraints B1 and B2 say that the same vehicle enters and leaves a given customer. It also links the y and the x variables.

  4. The other constraints are the capacity constraints. Constraint F limits the capacity of a vehicle (this constraint could be removed, because its already covered by LD). Adding them will speedup the solver, becuase the LP relaxation will be tighter.

  5. The constraint LD is similar to the capacity constraint already seen in the previous model: for each vehicle and at each location Li,h Lj,h - cj, if the vehicle h goes from i to j.

The model is due to [2] p.15 or [3] p.7 :

           ∑      ∑
min            ci,j    xi,j,h
           i,∑j∈V     h
subjectto     yi,h = 1                      forall i ∈ V \ {1}        (A1 )
            h
           ∑
              y1,h = K                                              (A2 )
           ∑h         ∑
              xi,j,h =    xj,i,h = yi,h       forall i ∈ V,h ∈ H     (B1,B2 )
           ∑j          j
               cy   ≤ C                    forall h ∈ H                (F )
                ii,h
           i|i>1
           Li,h ≤ Lj,h - cj + C (1 - xi,j,h)  forall i ∈ V,j ∈ V \ {1 }
                                              h ∈ H                 (LD )
           ci ≤ Li,h ≤ C                   forall i ∈ V,h ∈ H
           xi,j,h , yi,h ∈ {0, 1}            forall i,j ∈ V,i ⁄= j,h ∈ H

Listing 1: The Main Model implemented in LPL [4]
model cvrp3 "Three-index Flow Formulation"; 
  set i,j,k "nodes set"; 
  set h     "vehicles"; 
  set e0{i,j}; e1{i,j}; 
  parameter c{i}; D{i,j}; K; C; 
  binary variable x{i,j,h|i<>j}; y{i,h}; 
  --variable L{i,h|i<>1} [c..C]; 
  variable L{i,h} [c..C]; 
  constraint 
    A1{i|i>1}: sum{h} y = 1; 
    A2:   sum{h} y[1,h] = K; 
    B1{i,h}: sum{j} x[i,j,h] = y; 
    B2{i,h}: sum{j} x[j,i,h] = y; 
    F{h}: sum{i|i>1} c*y <= C; 
    --LD{i,j,h|i>1 and j>1 and i<>j}: L[i,h] -L[j,h]+c[j] <= C*(1-x); 
    LD{i,j,h|j>1 and i<>j}: L[i,h] -L[j,h]+c[j] <= C*(1-x); 
    S2{i,j,h|i<j}: x[i,j,h]+x[j,i,h]<=1; 
    --XX: sum{i,j,h} D*x>=780; 
    E0{e0[i,j]}: sum{h} (x[i,j,h]+x[j,i,h]) = 1; 
    --E1{e1[i,j],h}: x=0; 
  minimize obj: sum{i,j,h} D*x; 
end

Further Comments

The variables yi,h can be eliminated altogether by replacing yi,h with jxi,j,h. Whether this may help the solver is not clear.

References

[1]   MatMod. Homepage for Learning Mathematical Modeling :  https://matmod.ch.

[2]   Toth P. and Vigo D. (eds.). The Vehicle Routing Problem. Siam, Society for Industrial and Applied Mathematics, Philadelphia, 2002.

[3]   Toth P. and Vigo D. (eds.). Vehicle Routing, Problems, Methods, and Applicaions. Siam, Society for Industrial and Applied Mathematics, Philadelphia, 2014, 2nd edition.

[4]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.