Vehicle Routing Problem
CAPACITATED VRP · CANONICAL FORMULATION
Logistics · Transportation · OperationalGiven a central depot, a fleet of vehicles each with finite capacity, and a set of customers with known demands and coordinates, the Capacitated Vehicle Routing Problem asks: which subset of routes starting and ending at the depot serves every customer exactly once, respects every vehicle's capacity, and minimises total travel distance? Introduced by Dantzig & Ramser (1959) under the title “The Truck Dispatching Problem,” CVRP is a strict generalisation of the travelling-salesman problem and is one of the most studied problems in operations research. This page presents the canonical two-index MILP formulation, an interactive Clarke & Wright (1964) savings solver on a Euclidean instance, and cross-links to applied instances across logistics, agriculture, healthcare, and construction.
Why CVRP matters
Three facts that anchor the problem
Problem definition
Inputs · decision · objective · constraints
Let $G = (V, E)$ be a complete graph on $n + 1$ nodes. Node $0$ is the depot; nodes $1, \ldots, n$ are customers. Each customer $i$ has a non-negative demand $q_i$, and each edge $(i,j)$ has a non-negative travel cost $c_{ij}$ (in symmetric CVRP, $c_{ij} = c_{ji}$). A homogeneous fleet of $K$ vehicles, each with capacity $Q$, operates from the depot. The decision is a set of routes (closed walks starting and ending at the depot) such that:
every customer is visited exactly once, the total demand on each route does not exceed $Q$, and the number of routes does not exceed $K$. The objective is to minimise the total travel cost over all routes. The problem is NP-hard in the strong sense — it contains the Hamiltonian tour problem as a special case.
Mathematical formulation
Two-index MILP · after Toth & Vigo (2014), Ch. 1
Notation
| Symbol | Meaning |
|---|---|
| $V = \{0,1,\ldots,n\}$ | node set — $0$ is the depot, $V' = V \setminus \{0\}$ the customers |
| $c_{ij}$ | travel cost on edge $(i,j)$, $i \ne j$ |
| $q_i$ | demand of customer $i \in V'$ |
| $Q$ | capacity of every vehicle (homogeneous fleet) |
| $K$ | number of vehicles available |
| $x_{ij} \in \{0,1\}$ | 1 if edge $(i,j)$ is used by some vehicle, 0 otherwise |
| $u_i$ | auxiliary MTZ variable — cumulative load on entry to customer $i$ |
Objective
Constraints
Alternative formulations. The original Dantzig-Fulkerson-Johnson (DFJ) subtour elimination cuts $\sum_{i \in S}\sum_{j \notin S} x_{ij} \ge \lceil \sum_{i \in S} q_i / Q \rceil$ for every non-empty $S \subset V'$ yields a stronger LP relaxation but exponentially many constraints — handled via branch-and-cut. A three-index formulation with an explicit vehicle index $k$ is easier to read but weaker in the LP. The set-partitioning formulation, solved by branch-cut-price (Fukasawa et al. 2006; Pessoa et al. 2020), is the state-of-the-art exact method.
Real-world to OR mapping
How the abstract formulation maps to applied instances
| Real-world concept | OR symbol / role |
|---|---|
| Central warehouse or depot | node $0$ |
| Customer / delivery stop | node $i \in V' = \{1,\ldots,n\}$ |
| Parcel volume / mass demanded | $q_i$ |
| Van / truck payload capacity | $Q$ |
| Fleet size | $K$ |
| Road-network travel distance or time | $c_{ij}$ |
| “Van $k$ drives from stop $i$ to stop $j$” | $x_{ij} = 1$ (some vehicle) |
Interactive solver
Clarke-Wright savings on a Euclidean random instance
The Clarke & Wright (1964) savings algorithm is the most enduring constructive heuristic for CVRP. It starts with one route per customer (depot $\to i \to$ depot), then repeatedly merges the pair of routes producing the largest savings $s_{ij} = c_{0i} + c_{0j} - c_{ij}$, provided the merge remains capacity-feasible. The algorithm runs in $O(n^2 \log n)$ and is typically within 5–10% of the best-known solution on small-to-medium benchmarks. Use the controls below to generate random instances and watch Clarke-Wright build a routing.
Standard benchmarks
Where the literature lives · where you can test your own algorithms
Three canonical benchmark libraries are used across CVRP research:
- CVRPLIB (Uchoa et al. 2017) — the de-facto standard; 100 X-class instances with 100–1000 customers, plus legacy classes A, B, E, F, M, P. Best-known solutions continually updated. vrp.atd-lab.inf.puc-rio.br
- Augerat (1995) — small classical instances A/B/P (30–80 customers) used as algorithm-debugging baselines. Included in CVRPLIB.
- Christofides, Mingozzi, Toth (1979) — the 14 original CMT instances (50–200 customers). Now superseded by CVRPLIB but still cited.
All instances use the TSPLIB .vrp file format: coordinates, demands, capacity, and an
optional depot specification. Exact solvers (branch-cut-price, e.g., VRPSolverEasy) routinely
solve instances up to ~300 customers; metaheuristics (HGS, LKH-3) handle 1000+ customers within a few
percent of optimal.
Key references
DOIs & permanent URLs