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.
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.
First, we introduce a binary variable x_{i,j,h} with is 1 if an edge is traversed by vehicle h, otherwise it is 0. Another binary is y_{i,h} defining which vehicle visits which customer.
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.
Constraints B1 and B2 say that the same vehicle enters and leaves a given customer. It also links the y and the x variables.
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.
The constraint LD is similar to the capacity constraint already seen in the previous model: for each vehicle and at each location L_{i,h} ≤ L_{j,h} - c_{j}, if the vehicle h goes from i to j.
The model is due to [2] p.15 or [3] p.7 :
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
The variables y_{i,h} can be eliminated altogether by replacing y_{i,h} with ∑ _{j}x_{i,j,h}. Whether this may help the solver is not clear.
[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.