With the following application of tour planning with two schoolbuses, an important problem is introduced: the capacitated vehicle routing problem (CVRP). A precise definition is given in the next section. With this gentle introduction, several concepts are explained that will be formalized later when the general model with several formulations are defined. So, let’s start with this easy problem.
A school owns two busses with a capacity of 35 persons each. Each morning they must make the same tour to collect the children from their homes. The bus stops are given locations and at each stop a certain number of children have to board one of the two busses. The two busses start each at the school and return – after collecting all 55 children – to the school. Find the tours such that the total travel distance (or travel time) of the two busses is as small as possible. The routing network with the bus stops is given in Figure 1. There are 29 stops (yellow circles) (’0’ is the school where the two busses start each morning). The data are given in file schoolbus.txt. The problem is from a competition (see [2]).
There are two (K = 2) busses with a capacity of 35 (C = 35). Furthermore we have 30 locations (i ∈ I = {0,…, 29}) where the bus stops. At each location, there are c_{i} children at each location waiting. And finally, all travel time (or distances) between the stops is given as the distance matrix d_{i,j}. We build a (sparse) graph G = (I,E,d) from this network, and complete the graph with missing links by the shortest paths D_{i,j}. The complete graph now is G′ = (I,I × I,D). The data are read from a file using the following data model. Note that the data file contains three subsets (Table 3) used for the three subtour eliminations :
model data; //schoolbus data
parameter d{i,j}; X{i}; Y{i};; //coordinates
K:=2 "number of busses";
C:=35 "bus capacity";
Read{i}('schoolbus.txt,%1:Table', i,c,X,Y);
Read{i,j}('%2', i,j,d);
Read{s}('%3', {i} S); --define the 3 subsets
-- The Floyd-Warshall algorithm
D{i,j} := if(i=j,0,d or d[j,i],Max(d,d[j,i]),999);
for {k} do D{i,j} := Min(D[i,j],D[i,k]+D[k,j]); end
end
A binary variable x_{i,j} is introduced, saying whether the edge (i,j) is traversed by one of the two busses.
The objective is to minimize the length of all traversed edges by the two busses that is:
At the school both buses arrive and leave exactly once (K = 2):
At each location (except the school) exactly one bus arrives and leaves the place.
At this point, we may solve the problem. The solution, we get is shown in Figure 2. This solution is illegal.
We encounter a similar problem here as we saw in the TSP problem: there are subtours. For example, one bus just makes the tour 16 - 17 - 18 - 16. But there are other problems: another bus just does the small cycle 0 - 1 - 9 - 0. Clearly it starts at the school, but it is too short, because then a third bus must make the whole rest and would not have enough capacity to load all the remaining children. What to do? Well, we try the same as we did in the TSP problem: forbid all “illegal” subtours. However, the concept of “illegal” subtours is slightly more complicated than in the TSP: a tour is illegal, (1) if it does not contain the school and (2) if it is too long and exceeds the capacity. So let’s add a constraint that excludes these subtours. In our case, we could add the two constraints (note that we have an undirected graph):
(It is easier to add the smaller cycle, it is “illegal” too. Why? We may argue as follows: Since there are only two busses, one bus cannot just do the small cycle 0 - 1 - 9 - 0, since otherwise the other bus must do the rest which is too long from the capacity point of view.)
After adding the two constraints, the model can be solved again. Now, it turns out that one bus does the cycle 0 - 12 - 13 - 0, which is too short, so just add a constraint to forbid it and solve again. The constraint is:
The solution is given by Figure 3.
We are lucky, this is an legal and optimal solution: There are no subtours and both tours fullfill the capacity condition of maximally 35 children (one bus loads 26 and the other loads 29 children). Note, after adding only three constraints we already get a solution. The three subtour constraints are given by the general formulation as follows (the sum of all edges in an illegal subtour must be smaller than the cardinality of the subset of locations in the subtour):
model cvrp "Vehicle Routing Problem";
set i,j,k "Nodes set";
s; S{s,i} "Subsets for subtours";
parameter c{i}; D{i,j}; K; C;
binary variable x{i,j|i<j};
constraint
A: sum{j} x['0',j] = 2*K;
B{i|i<>1}: sum{j} (x[i,j]+x[j,i]) = 2;
SU{s}: sum{i,j|S[s,i] and S[s,j]} x <= sum{i|S}1-1;
minimize obj: sum{i,j} D*x;
end
The general capacitated vehicle routing problem is now introduced and several mathematical formulations are given.
See also model /MOlocHTMLcvrp-1.tex.html See also model /MOlocHTMLcvrp-2.tex.html See also model /MOlocHTMLcvrp-3.tex.html
[1] MatMod. Homepage for Learning Mathematical Modeling : https://matmod.ch.
[2] SVOR. SVOR Optimization Competition 2006. Internet (http://www.svor.ch).
[3] Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.