Clarke-Wright

319. Clarke-Wright

The savings algorithm (Clarke & Wright, 1964) — the classical constructive heuristic for VRP. Simple, fast, surprisingly good for capacitated VRP.

319.1. The savings concept

Two single-customer routes: depot $\to 𝑖 \to$ depot and depot $\to 𝑗 \to$ depot. Cost = $2 𝑐_{0 𝑖} + 2 𝑐_{0 𝑗}$ .

Merge into depot $\to 𝑖 \to 𝑗 \to$ depot. Cost = $𝑐_{0 𝑖} + 𝑐_{𝑖 𝑗} + 𝑐_{0 𝑗}$ .

Saving:

𝑠_{𝑖 𝑗} = (2 𝑐_{0 𝑖} + 2 𝑐_{0 𝑗}) - (𝑐_{0 𝑖} + 𝑐_{𝑖 𝑗} + 𝑐_{0 𝑗}) = 𝑐_{0 𝑖} + 𝑐_{0 𝑗} - 𝑐_{𝑖 𝑗}

By triangle inequality $𝑠_{𝑖 𝑗} \geq 0$ . Large savings → customers $𝑖$ and $𝑗$ are close to each other and far from the depot.

319.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 routes

Sort: $𝑂 (𝑛^{2} log 𝑛)$ . Merge checks: $𝑂 (𝑛^{2})$ pairs. Total: $𝑂 (𝑛^{2} log 𝑛)$ .

319.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.

319.4. Variants & enhancements

Modified savings: $𝑠_{𝑖 𝑗} = 𝑐_{0 𝑖} + 𝑐_{0 𝑗} - 𝜆 𝑐_{𝑖 𝑗}$ with $𝜆 > 1$ — biases toward shorter inter-customer edges
Probabilistic Clarke-Wright: randomize merge order to find better solutions
Followed by 2-opt within routes: standard polish

319.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.

319.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.

319.7. See also

VRP — problem solved
TSP — single-vehicle ancestor
VRPTW — extension to time windows
Daganzo — large-scale alternative