Capacitated Vehicle Routing Problem formulation

There is a library in AIMMS that solves a Capacitated Vehicle Routing Problem (CVRP). It contains different options of formulating the problem. The difference between these articles is how subtours are eliminated. The objective function and most of the constraints are the same for all four options and will be explained in this article.

Linear integer programming model

A CVRP can be formulated as a linear integer programming model. The total distance of the route, where all costumers demands are met, should be minimized.

The binary variable \(x_{ijk}\) has a value of \(1\) if the arc from node \(i\) to node \(j\) is in the optimal route and is driven by vehicle \(k\).

\[x_{ijk} \in \{0,1\} \qquad \forall k \in \{1,...,p\},\enspace i,j \in \{1,...,n\}\]

Whereby, there is no travel from a node to itself:

\[x_{iik} = 0 \qquad \forall k \in \{1,...,p\},\enspace i \in \{1,...,n\}\]

The parameter \(d_{ij}\) describes the distance from node \(i\) to node \(j\). There are \(n\) nodes (depot = 1) and \(p\) vehicles. The objective function can be formulated as follows:

\[Min \sum_{k = 1}^{p}{\sum_{i = 1}^{n}{\sum_{j = 1}^{n}{d_{ij}x_{ijk}}}}\]

Every node should be entered and left once (expect for the depot) and by the same vehicle. The depot should be left and entered once by each vehicle. \(q_{i}\) describes the demand of each costumer and \(Q\) is the capacity of the vehicles. The sum of the demands of all costumers that vehicle \(k\) will serve, should not exceed the capacity of vehicle \(k\). All these constraints can be formulated as follows:

1. Vehicle leaves node that it enters

Ensure that the number of times a vehicle enters a node is equal to the number of times it leaves that node:

\[\sum_{i = 1}^{n}{x_{ijk}} = \sum_{i = 1}^{n}{x_{jik}} \qquad \forall j \in \{1,...,n\}, \enspace k \in \{1,...,p\}\]

2. Ensure that every node is entered once

\[\sum_{k = 1}^{p}{\sum_{i = 1}^{n}{x_{ijk}}} = 1 \qquad \forall j \in \{2,...,n\}\]

Together with the first constraint, it ensures that the every node is entered only once, and it is left by the same vehicle.

3. Every vehicle leaves the depot

\[\sum_{j = 2}^{n}{x_{1jk}} = 1 \qquad \forall k \in \{1,...,p\}\]

Together with constraint 1, we know that every vehicle arrives again at the depot.

4. Capacity constraint

Respect the capacity of the vehicles. Note that all vehicles have the same capacity.

\[\sum_{i = 1}^{n}{\sum_{j = 2}^{n}{q_{j} x_{ijk}}} \leq Q \qquad \forall k \in \{1,...,p\}\]

The above constraints are formulated in the Common Constraints and Variables section in the CVRP Library.

Eliminating subtours

However, a solution that satisfies the above constraints can still be infeasible to the actual problem; namely when the solution contains a subtour, as illustrated by the subtour through nodes 3, 4, and 5 below:

The different formulations in the library are different ways of eliminating these subtours, and are discussed in detail in the following articles:

1. Explicit Dantzig-Fulkerson-Johnson formulation

2. Implicit Dantzig-Fulkerson-Johnson formulation

3. Miller-Tucker-Zemlin formulation

4. Time Windows (provided non-zero travel times)