317. VRP

The Vehicle Routing Problem: given a fleet of vehicles based at a depot, serve a set of customers with minimum total cost (distance / time). Generalization of TSP to multiple vehicles.

Core supply-chain problem: last-mile delivery, beverage distribution, waste collection, school bus routing, mobile maintenance.

317.1. Capacitated VRP (CVRP)

Standard formulation. Each vehicle has capacity $𝑄$. Each customer $𝑖$ has demand ${𝑞}_{𝑖}$.

Decision variable ${𝑥}_{𝑖𝑗𝑘}$: $1$ if vehicle $𝑘$ traverses arc $\left(𝑖,𝑗\right)$.

s.t.:

• Each customer visited exactly once
• Vehicle starts and ends at the depot
• Total demand on each vehicle’s route $\le 𝑄$
• Subtour elimination (like TSP)

317.2. Why it’s harder than TSP

• NP-hard even worse than TSP (TSP is the single-vehicle case)
• Combinatorial explosion: must simultaneously partition customers into routes and route each
• Exponential number of subtour constraints, plus capacity constraints

317.3. Variants

• VRP-TW (with time windows) — each customer has a delivery window $\left[{𝑎}_{𝑖},{𝑏}_{𝑖}\right]$; see VRPTW
• Pickup-and-delivery VRP (PDVRP) — pickups must precede deliveries on the same route
• Heterogeneous fleet VRP — vehicles with different capacities / costs
• Stochastic VRP — random demand or travel times
• Periodic VRP — multi-day delivery schedules with frequency constraints
• Open VRP — vehicles don’t return to depot (typical for last-mile contractors)
• Multi-depot VRP — vehicles from multiple depots

317.4. Solution methods

Exact (small instances, $𝑛\le 200$):

• Branch-and-cut on the LP formulation
• Branch-and-price (column generation)
• Dynamic programming for very small fleets

Heuristics:

• Constructive: Clarke-Wright savings (the classic), Sweep, Fisher-Jaikumar
• Improvement: 2-opt, Or-opt, 3-opt within routes; inter-route swaps
• Metaheuristics: tabu search, simulated annealing, genetic algorithms, large-neighborhood search
• Modern: Adaptive Large Neighborhood Search (ALNS), HGS (Hybrid Genetic Search)

Open-source solvers:

• OR-Tools (Google) — fast LS-based heuristics
• VROOM — open-source CVRP / VRPTW solver
• VRPSolver — academic branch-cut-price

317.5. Continuous approximation

For large-scale VRP design (how many vehicles? how big are routes?), Daganzo’s continuous approximation gives clean formulas. See Daganzo.

317.6. See also

• TSP — single-vehicle case
• VRPTW — with time windows
• Clarke-Wright — standard heuristic
• Daganzo Continuous Approximation
• Assignment Problem — sub-problem in some methods