Capacitated Vehicle Routing Problem

In the Capacitated Vehicle Routing Problem, identical vehicles with limited capacity, based at a single depot, must serve a set of customers with known demands. Each customer is visited exactly once by one vehicle, the load of each route cannot exceed the vehicle capacity, and the goal is to minimize the total distance. Some classic instances also limit the duration of each route, which may include a service time at each customer.

Mathematical Definition

Let $V = \{0, 1, \dots, n\}$ be the set of vertices, where $0$ is the depot and $V_+ = V \setminus \{0\}$ are the customers. Each customer $i \in V_+$ has a demand $q_i > 0$, travelling between $i$ and $j$ costs $c_{ij}$, and the vehicles have capacity $Q$. A route is a sequence $r = (0, i_1, \dots, i_p, 0)$ of distinct customers, with load $q(r) = \sum_{k=1}^{p} q_{i_k}$ and cost $c(r) = c_{0 i_1} + \sum_{k=1}^{p-1} c_{i_k i_{k+1}} + c_{i_p 0}$.

A solution is a set of routes $R$ in which every customer belongs to exactly one route and $q(r) \le Q$ for every $r \in R$. The CVRP asks for a solution of minimum total cost $\sum_{r \in R} c(r)$.

Instance sets differ in how $c_{ij}$ is computed and rounded, in how the number of routes $|R|$ is limited, and in extra constraints such as a maximum route duration. The table of instance sets below gives the conventions of each set.