Sequential Formulation

Run LPL Code  ,  PDF Document

Problem

The capacitated vehicle routing problem (CVRP) has been already defined. Implement a model that replicates the idea of the sequential formulation of the TSP (see tsp-1).

Modeling Steps

The formulation is basically the same as the sequential formulation of the TSP, instead of using the potential variables ui, we use Li – the remaining capacity left on the vehicle after visiting i. (We use a formulation for a directed graph).

  1. First, let’s introduce a binary variable xi,j which is 1 if an edge is traversed by a vehicle, otherwise it is 0 (same as in the TSP).

  2. The first constraint A (below) says that the number of vehicles leaving the depot is K.

  3. The next constraints B1 and B2 say that all customers (except the depot) must be visited exactly once (once arriving, once leaving)).

  4. The constraint LD prevents subtours by defining the load Li at the location i. It says, that the load Li (that is, the remaining capacity on the vehicle) must be at least the load of Lj + ci if the vehicle goes from i to j, since then the load of ci is discharged (or charged – then ci is negative) at costumer i, otherwise there is no restriction on Li - Lj.

  5. The load Li can be bounded (constraint D).

  6. In addition or alternatively – but this is no anymore part of the core model – the travel time (or distance) can be limited (see constraint TD). The constraint says that the covered mileage (or time) Tj at the location j must be at least the mileage Ti + di,j if the vehicle goes from i to j, otherwise Tj - Ti is not limited. TA is an upper bound on Ti.

The model is (due to [1] page 13):

∑ min ci,jxi,j i,j∈V ∑ subjectto x1,j = K (A ) j∈∑V \{1} xi,j = 1 forall i ∈ V \ {1 } (B1 ) j∈V ∑ xi,j = 1 forall j ∈ V \ {1} (B2 ) i∈V Li ≥ Lj + cj - C (1 - xi,j) forall i ∈ V, j ∈ V \ {1} (LD ) ci ≤ Li ≤ C forall i ∈ V [ Tj ≥ Ti + Di,j - T A (1 - xi,j) forall i ∈ V, j ∈ V \ {1} (TD ) ] x ∈ {0, 1} forall i,j ∈ V, i ⁄= j i,j n = |V |

Listing 1: The Main Model implemented in LPL [3]
model cvrp2 "Sequential Formulation"; 
  set i,j,k "nodes set"; 
  parameter c{i}; D{i,j}; K; C; 
  binary variable x{i,j|i<>j}; 
  variable L{i} [c..C]; T{i}; TZ; 
  constraint 
    A: sum{j} x[1,j] = K; 
    B1{i|i<>1}: sum{j} x[i,j] = 1; 
    B2{j|j<>1}: sum{i} x[i,j] = 1; 
    S2{i,j|i<j}: x[i,j]+x[j,i]<=1; 
    S3{i,j,k|i<j<k}: //length 3 subtours 
      x[i,j]+x[j,k]+x[k,i]+x[i,k]+x[k,j]+x[j,i]<=2; 
    LD{i,j|j<>1}: L[i] - L[j] <= (1-x)*C - c[i]; 
  minimize obj: sum{i,j} D*x; 
end

Solution

As expected the schoolbus problem is easy to solve. However, even for small problems from the VRP-library found here, it is difficult to find the optimal solution. Problem 1 (the easiest takes 25 secs by the HIGHS solver to find the optimum – even by eliminating the subtours of length 2 and 3 (constraints S2, S3) (which potentially removes optimal solutions!) (Gurobi 11.0 takes 1.5 secs). Nevertheless, we get good solutions after several minutes. Interesingly, the gap between to upper and lower bound, while Gurobi solves the problem, stays quite large. The lower bound is typically far from the optimum, but the upper bound get quite close to the optimum. This suggests the use of this approach to find a good integer solution and to get a good lower bound with the previous model (Two-index sutour).

For larger instances use the model cvrp1 and solve it with the Hexaly solver.

Questions

  1. Solve the schoolbus problem using this model.

  2. Suppose in the schoolbus problem, the school wants to replace the busses and has to decide whether to buy 2, 3 or 4 buses. What must the maximal capacity of the busses be? What is the solution?

Answers

  1. Replace the data and the output correspondingly and solve.

  2. For 2 busses the capacity must be at least 28. Here is a solution: 

       Length of Tour 1: 36  , children: 27 
   Length of Tour 2: 44  , children: 28 
   Tour 1: 0 1 6 7 8 9 12 13 14 15 16 17 18 19 20 
   Tour 2: 0 2 3 4 5 10 11 21 22 23 24 25 26 27 28 29

    For three buses the capacity must be at least 19 and a solution is: 

       Length of Tour 1: 26  , children: 17 
   Length of Tour 2: 29  , children: 19 
   Length of Tour 3: 35  , children: 19 
   Tour 1 : 0 1 2 3 4 5 6 9 12 13 14 
   Tour 2 : 0 7 8 15 16 17 18 19 20 
   Tour 3 : 0 10 11 21 22 23 24 25 26 27 28 29

    For 4 busses the cacacity is at least 14 and a solution is (Gurobi 7.5 takes almost 10 mins to solve the problem): 

       Length of Tour 1: 26  , children: 14 
   Length of Tour 2: 29  , children: 13 
   Length of Tour 3: 26  , children: 14 
   Length of Tour 4: 26  , children: 14 
   Tour 1 :   0  1  6  7  9 14 15 19 20 
   Tour 2 :   0  2  3  4  5 13 28 29 
   Tour 3 :   0  8 10 12 16 17 18 
   Tour 4 :   0 11 21 22 23 24 25 26 27

References

[1]   Rieck J. Tourenplanung mittelständischwer Speditionsunternehmen, Modelle und Methoden. Gabler Edition Wissenschaft, 2008.

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

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