The Vehicle Routing Problem (VRP) asks: given a fleet of vehicles based at one or more depots, and a set of customers each requiring a delivery or service visit, what is the minimum-cost set of routes such that every customer is visited exactly once and every vehicle returns to its depot?
The decisions are assignment (which vehicle serves which customers) and sequencing (in what order each vehicle visits its customers). The classic version has one constraint: vehicle capacity. Real-world variants layer on time windows, multiple depots, heterogeneous fleets, split deliveries, and stochastic demand.
VRP is NP-hard. For a modest 50-customer, 5-vehicle instance, the number of valid route combinations exceeds the number of atoms in the observable universe. Exact solvers (branch-and-price, branch-and-cut) work well up to a few hundred customers; larger instances require metaheuristics such as Large Neighbourhood Search.
A courier company has 8 vans, each with capacity for 20 parcels, and 120 parcels to deliver across the city today. All vans start and end at a central warehouse.
Naïve approach: assign 15 parcels per van arbitrarily, deliver in any order. Total distance: ~380 km.
VRP-optimised: cluster geographically proximate customers onto the same van, sequence stops to avoid backtracking, balance load across the fleet. Total distance: ~240 km — a 37% reduction, same fleet, same parcels.
The gain comes entirely from the joint optimisation of assignment and sequencing. Optimising them separately — assign first, then sequence — leaves a significant gap because the best sequence for a given assignment may require a different assignment entirely.
VRP complexity comes from combining routing with capacity. Relaxing either constraint makes the problem polynomial — the combination is what makes it NP-hard, and what makes every real-world variant structurally distinct.