316. Clarke-Wright
The savings algorithm (Clarke & Wright, 1964) — the classical constructive heuristic for VRP. Simple, fast, surprisingly good for capacitated VRP.
316.1. The savings concept
Two single-customer routes: depot depot and depot depot. Cost = .
Merge into depot depot. Cost = .
Saving:
By triangle inequality . Large savings → customers and are close to each other and far from the depot.
316.2. Algorithm
Initialize: one route per customer (depot → i → depot)
Compute s[i,j] for all pairs and sort descending
For each (i, j) in sorted order:
If merging routes containing i and j is feasible:
- i and j must be on the same "endpoint" of their routes
- i and j must be on different routes (not the same one)
- Merged route's total demand ≤ Q (capacity)
Then merge them
Return routesSort: . Merge checks: pairs. Total: .
316.3. Two variants
Parallel (the original): consider all savings in one sorted list; merge eagerly. Multiple routes grow simultaneously.
Sequential: process one route at a time; finish growing it before starting another. Tends to produce longer routes; sometimes better, sometimes worse than parallel.
316.4. Variants & enhancements
- Modified savings: with — biases toward shorter inter-customer edges
- Probabilistic Clarke-Wright: randomize merge order to find better solutions
- Followed by 2-opt within routes: standard polish
316.5. Real-world significance
For 60 years (1964–today), Clarke-Wright + 2-opt has been the standard quick-and-dirty VRP heuristic:
- Implementable in 100 lines of code
- Fast on 1000+ customer instances
- Within 5-10% of optimum for capacitated VRP
- Easy to adapt for time windows, heterogeneous fleets, etc.
Modern heuristics (ALNS, HGS) do better but at significantly more complexity.
316.6. Daganzo continuous-approximation alternative
For very large fleets, instead of optimizing each route, use Daganzo’s continuous-approximation formulas to design route structure. See Daganzo.