Glossary · approach
Clarke-Wright Savings
Classical 1964 heuristic for the Capacitated Vehicle Routing Problem: start with each customer on its own route, iteratively merge pairs of routes that yield the largest 'savings' in distance, until capacity blocks further merges.
Clarke-Wright AlgorithmSavings AlgorithmClarke and Wright 1964
The Clarke-Wright Savings algorithm, introduced by Clarke and Wright in 1964 in *Operations Research*, is the classical and simplest constructive heuristic for CVRP. The algorithm starts with every customer on its own back-and-forth route (depot → customer → depot). For each pair of customers (i, j), it computes the 'savings' s(i, j) = d(depot, i) + d(depot, j) − d(i, j) — the distance reduction from merging the two single-customer routes into one route that visits i then j. Pairs are sorted by descending savings; the algorithm walks the list and merges two routes whenever the merge respects vehicle capacity. It runs in seconds on 100-200 customers and typically lands within 5-10% of the optimal solution. Despite being over sixty years old and predating digital optimization, Clarke-Wright remains a practical benchmark for moderate-size CVRP and a standard warm-start for more sophisticated metaheuristics such as 2-opt, Or-opt and ALNS.
Örnek
Two single-customer routes (depot → A → depot and depot → B → depot) have a savings of 8 km when merged into depot → A → B → depot. If capacity allows, the merge proceeds; the savings list is walked top-down until no more capacity-feasible merges remain.