Series · 76 entries in 13 parts
Vehicle Routing, End to End
A complete reference on vehicle routing: from the TSP to production routing engines, in 13 parts.
- Who it's for
- Someone starting from zero who wants to understand VRP end to end.
- Running example
- berlin52 from TSPLIB: 52 cities, optimal tour length 7,542. Every post shows its gap to optimal.
- Solvers, from Part 5
- PyVRP (the ILS example); reinterpretcat/vrp in Rust (the ruin-and-recreate contrast)
Every post follows the same format
- Read first: prerequisites, each with a one-line refresher, and the question the post answers
- Intuition, built on a hand-worked example of 6–10 stops
- The formal idea, with just enough math
- Common misconceptions
- Try it in Python (Parts 0–4, plain Python, no libraries), then In PyVRP / in reinterpretcat/vrp from Part 5 on
- A short exercise
Parts 1–7 form a chain: each post ends with a limitation that the next post fixes. Parts 8–12 are reference parts you can read in any order.
Part 0 · 7 entries
Start here
Part 0 orients the reader before any algorithm appears.
History and series map
A timeline from Dantzig, Fulkerson and Johnson (1954) and Dantzig and Ramser (1959) through Clarke-Wright, Lin-Kernighan, Christofides, Concorde and HGS; where each part fits; suggested reading paths
Primer: graphs
Nodes, edges, weights; directed vs. undirected; paths, cycles, spanning trees, matchings; distance matrices
Primer: algorithms and complexity
Big-O; recursion; arrays, linked lists and heaps; polynomial vs. exponential growth
Primer: linear and integer programming
Variables, constraints, objective; LP relaxation; simplex intuition; duality and reduced costs; integer variables
Primer: probability and statistics
Random sampling; expectation and variance; distributions; comparing results across runs
Primer: Python, and reading Rust
Enough Python for the code in each post; enough Rust syntax to follow reinterpretcat/vrp
Glossary and notation (reference page)
Every term and symbol used in the series, linked from each post
Part 1 · 3 entries
The Traveling Salesman Problem
Part 1 defines the TSP, shows why it is hard, and introduces its family of variants.
What is the TSP?
Cities, tours, tour cost; a tour as a permutation; symmetric vs. asymmetric; shortest path (Dijkstra) is not the TSP
How hard can it be?
Why is the TSP hard?
(n−1)!/2 tours; brute force on 8 cities; P vs. NP and NP-hardness, intuitively; optimal vs. good enough
Real problems rarely look exactly like the TSP
The TSP family
Asymmetric TSP; multiple TSP (the bridge to VRP); TSP with time windows; prize-collecting TSP; orienteering
Can we still solve these exactly?
Part 2 · 5 entries
Exact methods
Part 2 covers the methods that prove a solution is optimal, and why they stop scaling.
Dynamic programming: Held-Karp
Subproblems over subsets of cities; O(n²·2ⁿ) time and memory
Memory explodes past a few dozen cities
Branch and bound
Branching on edges; lower bounds (assignment, 1-tree, Lagrangian relaxation); pruning; search order
Pruning is only as good as the bounds
Integer programming formulations
Decision variables per edge; degree constraints; subtour elimination (DFJ vs. MTZ); LP relaxation and the optimality gap
Exponentially many subtour constraints
Branch-and-cut and Concorde
Adding violated cuts only when needed; how Concorde solves very large TSPs exactly
Hard to model rich side constraints
Constraint programming for routing
Variables, domains and propagation; how Google OR-Tools' routing solver uses CP with local search
Too slow for daily operations at scale; we need fast answers
Part 3 · 2 entries
Fast first answers
Part 3 builds a tour quickly, with and without a guarantee on its quality.
Construction heuristics
Nearest neighbor; cheapest, nearest and farthest insertion; space-filling curves; speed vs. quality against the berlin52 optimum
No promise on how bad a tour can be
Approximation algorithms
Approximation ratio; MST-based 2-approximation; Christofides (at most 1.5× optimal); why guarantees need the triangle inequality; limits of approximability
Tours still have obvious flaws, such as crossing edges
Part 4 · 5 entries
Local search
Part 4 improves a tour with small changes until no change helps.
Neighborhoods and the 2-opt move
Removing crossing edges by reversing a segment; delta evaluation (a move's cost change without re-scoring the tour)
Only one kind of move
More moves
Or-opt, swap, relocate; first-improvement vs. best-improvement
Search gets slow as tours grow
Making local search fast
Neighbor lists; don't-look bits; tour data structures (arrays vs. linked lists)
Simple moves miss deeper improvements
k-opt and Lin-Kernighan
3-opt; variable-depth search; Lin-Kernighan; LKH, the strongest TSP heuristic
The search still stops improving
Local optima
Search landscapes; why local search gets stuck; why random restarts throw away good structure
We need a way to escape
Part 5 · 4 entries
Iterated local search on the TSP
Part 5 assembles ILS from four parts and tests it on berlin52.
The ILS idea
The four-part loop: starting solution, local search, perturbation, acceptance
How do we kick the solution?
Perturbation
The double-bridge move; choosing kick strength (too weak falls back, too strong is a random restart)
When do we keep the new solution?
Acceptance criteria
Accept only improvements, random walk, simulated-annealing style, late acceptance
The parts are not yet combined
Putting ILS together
Stopping criteria, tuning, results against the berlin52 optimum
Is ILS the only way to escape local optima?
Part 6 · 12 entries
The metaheuristic family
Part 6 covers the other main ways to escape local optima, each compared with ILS on berlin52.
Simulated annealing
Temperature; cooling schedules; accepting worse moves with a probability
Accepts worse solutions early, less often over time
Tabu search
Tabu list; tenure; aspiration criteria
Forbids recently undone moves so the search can't cycle back
Guided local search
Edge features; penalties on frequently used costly edges
Changes the cost function to push the search away
Variable neighborhood search
Systematic switching between neighborhoods; VND vs. VNS
A local optimum in one neighborhood may not be one in another
GRASP
Greedy randomized construction plus local search; restricted candidate lists
Many different, good starting points
Ant colony optimization
Pheromone trails; evaporation; building tours from learned edge preferences
Learns good edges from many constructed tours
Large neighborhood search: ruin-and-recreate and ALNS
Destroy and repair operators; adaptive operator selection; how reinterpretcat/vrp works
Rebuilds a large part of the solution at once
Genetic and memetic algorithms
Populations; crossover for tours (OX, EAX); mutation; adding local search (memetic)
Combines parts of different good solutions
Hyper-heuristics
Heuristics that choose which heuristic to run next; reinterpretcat/vrp's rosomaxa
Learns which search strategy works best during the run
Matheuristics
Combining exact solvers with heuristics; set-partitioning over routes found by a heuristic
Uses an exact solver to recombine heuristic solutions
Parallel search
Parallel restarts; cooperating searches; reproducibility trade-offs
Explores many regions at once
Choosing a metaheuristic
Single-solution vs. population methods; intensification vs. diversification; no free lunch
Summary of the family
Part 7 · 9 entries
From TSP to VRP
Part 7 extends the same ideas to many vehicles, capacity and time windows, ending with how PyVRP does it.
From one tour to many routes
The capacitated VRP (CVRP); giant tour + split (cutting one tour into routes that fit vehicles)
How do we build good routes directly?
VRP construction heuristics
Clarke-Wright savings; sweep; cluster-first route-second vs. route-first cluster-second
Moves only work inside one route
Capacity and moves between routes
Relocate, swap, 2-opt* and CROSS-exchange across routes; feasibility checks
Strict feasibility blocks good moves
Searching through infeasible solutions
Penalizing constraint violations instead of forbidding them; adjusting penalty weights
The pieces need to run as one search
ILS for the CVRP
The Part 5 loop with perturbations adapted for routes
Real customers have time windows
Adding time windows
VRPTW; forward time slack; segment concatenation to keep move evaluation fast
Can a population do better than one solution?
Hybrid Genetic Search (HGS)
Population of feasible and infeasible solutions; OX crossover + split; local search as education; diversity management; SWAP*
How do we prove a VRP solution is optimal?
Exact methods for VRP
Set partitioning; column generation; pricing with resource-constrained shortest paths; branch-cut-and-price
How do production-grade solvers combine all this?
How PyVRP's ILS works
Map each part to what readers built; why PyVRP moved from HGS to ILS
Real problems come in many variants
Part 8 · 14 entries
The VRP variant atlas
Part 8 gives each major variant its own post: what changes in the model, which methods adapt, and where it shows up in practice.
Pickup and delivery, and dial-a-ride
Paired stops; precedence; ride-time limits
Couriers, food delivery, ride-sharing, patient transport
Multi-depot VRP
Assigning customers to depots; depot-aware moves
Networks with several warehouses or hubs
Heterogeneous fleet and fleet sizing
Vehicle types with different capacity and cost; fleet mix decisions
Mixed fleets of bikes, vans and trucks
Open VRP and backhauls
Routes that don't return to the depot; deliveries before pickups
Contracted drivers; returns collection
Split delivery
One customer served by several vehicles
Large orders, bulk distribution
Multi-trip VRP
Vehicles reloading at the depot during a shift
Urban delivery with small vehicles
Periodic VRP
Planning visits over several days with visit frequencies
Maintenance, sales visits, waste collection
Prize-collecting and team orienteering
Choosing which customers to serve; profit vs. cost
Optional visits, limited capacity days
Time-dependent VRP
Travel times that change with time of day; FIFO property
Urban traffic, rush hours
Electric and green routing
Battery range; charging stops; emissions as an objective
EV fleets, sustainability targets
Location-routing and two-echelon VRP
Choosing depot locations together with routes; hubs and satellites
Network design, city logistics
Inventory routing
Deciding when and how much to deliver as well as the routes
Vendor-managed inventory, fuel and gas delivery
Arc routing
Serving streets instead of points; Chinese postman; capacitated arc routing
Garbage collection, street sweeping, meter reading
Drones, crowdsourcing and on-demand delivery
Truck-and-drone routing; crowdsourced drivers; instant delivery
Emerging last-mile models
Part 9 · 4 entries
Objectives, uncertainty and scale
Part 9 covers what changes when there is more than one goal, when the future is uncertain, and when instances get very large.
Multi-objective routing
Cost vs. vehicles vs. service quality vs. emissions; weighted sums; ranked (lexicographic) objectives; Pareto fronts
Stochastic and robust routing
Uncertain demands and travel times; chance constraints; recourse; robust plans
Dynamic and real-time routing
Orders arriving during the day; re-optimization; plan stability; policies instead of single plans
Large-scale routing and decomposition
Clustering; splitting big problems into regions; boundary effects; solving 10,000+ stops
Part 10 · 5 entries
Routing in the real world
Part 10 covers what it takes to run routing in production, beyond the algorithm.
Where the distance matrix comes from
Shortest-path algorithms on road networks (Dijkstra, A*, contraction hierarchies); OSRM and similar engines; asymmetric distances; n² matrix cost at scale
Real-world constraints
Skills, breaks, shifts, vehicle–order compatibility, priorities and workload balancing, shown in reinterpretcat/vrp
Data quality
Geocoding errors; service-time estimation; demand and capacity units; how bad inputs break good algorithms
Plans vs. what drivers actually do
Driver knowledge and route adherence; lessons from the Amazon Last Mile Routing Research Challenge
Architecture of a production routing engine
Request flow; matrix service; solver service; time limits and anytime behavior; re-planning; explaining routes to operations teams
Part 11 · 3 entries
Evaluation and the solver landscape
Part 11 covers how to judge solvers fairly and which ones exist.
Benchmarks and evaluating solvers
TSPLIB, CVRPLIB, Solomon, Gehring-Homberger, PyVRP/Instances; gap to best-known solution; fair comparison (time limits, seeds, hardware); PyVRP vs. reinterpretcat/vrp
Parameter tuning and experimental design
Automatic tuning (e.g. irace); avoiding overfitting to benchmarks; statistical comparison
The solver landscape
Open source: OR-Tools, PyVRP, reinterpretcat/vrp, VROOM, jsprit, Timefold, LKH-3; commercial solvers; how to choose
Part 12 · 3 entries
The frontier
Part 12 covers where the field is going and what is still unsolved.
Learning-based methods
Attention models and POMO; reinforcement learning; learned guidance inside classical solvers; where they stand against HGS and ILS
LLMs and routing
LLM-generated heuristics and operators; large routing models; what is hype and what works
Open problems and lessons from competitions
DIMACS 12th Implementation Challenge; EURO meets NeurIPS 2022; open research questions