Vehicle Routing (Savings)

Every morning, delivery vans leave a depot and fan out to dozens of customers. The question seems simple: which driver visits which addresses, and in what order? In practice, that question has an astronomically large number of answers, and finding the perfect one is one of the hardest problems in computer science.

This is the Vehicle Routing Problem (VRP) — a generalization of the Travelling Salesman where multiple vehicles share the load, each capped by a capacity (weight, volume, or time). It is NP-hard: no algorithm is known that finds the optimum in polynomial time for every instance.

Yet logistics companies don't grind to a halt. They rely on heuristics — fast methods that find good solutions without guaranteeing perfection. The most celebrated of these is the Clarke-Wright savings algorithm, published in 1964 by G. Clarke and J. W. Wright. Its idea is beautifully simple: start with a wasteful plan and greedily improve it.

The demo below starts with one truck per customer (every customer gets its own out-and-back trip from the depot). That is obviously wasteful — but it is a valid, capacity-respecting starting point. The algorithm then computes a savings value for every possible pair of customers:

$$s(i, j) = d(0, i) + d(0, j) - d(i, j)$$

where $d(0, i)$ is the distance from depot to customer $i$. Merging customers $i$ and $j$ into one route saves the depot-to-$i$ leg plus the depot-from-$j$ leg, minus the extra edge $d(i,j)$ now needed inside the route.

<!-- {{c_html_intro}} -->
<div class="info-bar">
  <span id="total-dist">{{lbl_total_dist}} —</span>
  <span id="step-info"></span>
</div>
<canvas id="canvas" width="360" height="270"></canvas>
<p class="hint-txt" id="hint-txt">{{hint_init}}</p>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.info-bar { display: flex; gap: 1rem; font-size: .85rem; font-weight: 600;
            margin-bottom: .4rem; flex-wrap: wrap; }
#total-dist { color: #1d3557; }
#step-info { color: #6c757d; }
canvas { display: block; border: 1px solid #dde3e8; border-radius: 8px;
         background: #f8fafc; width: 100%; max-width: 360px; height: auto; }
.hint-txt { font-size: .82rem; color: #555; margin: .4rem 0; min-height: 2em; line-height: 1.4; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Press Step to apply the single best merge, or Run all to apply them all at once. Notice how the total distance drops with each step, and how some merges are skipped when they would exceed the truck's capacity.

The Vehicle Routing Problem is NP-hard — it contains the Travelling Salesman Problem as a special case (set the capacity high enough to carry all customers in a single truck). That means:

• No known polynomial-time algorithm finds the optimum for every instance.
• Brute force is hopeless: for $n$ customers there are roughly $n!$ orderings; with 20 customers that already exceeds $10^{18}$.
• Clarke-Wright runs in $O(n^2)$ (compute all pairwise savings, sort, greedily merge). It is fast, but it is a heuristic — it can produce solutions that are far from optimal on adversarial inputs.

For the special case where distances satisfy the triangle inequality, Christofides' algorithm (1976, TSP) guarantees a solution within $\tfrac{3}{2}$ of optimal. No such tight worst-case bound is known for general multi-vehicle VRP, though Clarke-Wright typically achieves 5–10 % above optimal on real-world instances.

The gap between what we can compute quickly and what we want (the true optimum) is the same gap at the heart of P vs NP. Heuristics like Clarke-Wright are how industry navigates that gap every day.

Vehicle routing is not an academic curiosity — it is one of the most economically important combinatorial problems ever studied:

• Parcel and food delivery: companies like UPS, FedEx, and Amazon route thousands of vans daily. A 1 % reduction in total distance translates to millions of dollars in fuel and driver-hours saved.
• School buses and transit: assigning students to buses and planning routes under capacity and time-window constraints is a direct VRP variant.
• Field service management: scheduling technicians to customer sites (with skill requirements and time windows) is another VRP in disguise.
• Supply-chain logistics: replenishing retail stores from regional distribution centers is a capacitated VRP repeated every night.

Modern solvers combine Clarke-Wright with local-search improvements (2-opt, 3-opt, Lin-Kernighan), metaheuristics (simulated annealing, genetic algorithms), and — increasingly — machine learning to guide the search. But Clarke-Wright's 1964 greedy kernel remains at the heart of most production systems because it is fast, intuitive, and surprisingly good.

The same savings-maximization logic appears in facility location and network design: in every case you start from a wasteful baseline and greedily pocket the cheapest improvements first.

The Clarke-Wright savings algorithm is a lesson in pragmatic algorithmics: when the exact problem is NP-hard, find the structure that lets you make confident greedy choices. "Merge the pair that saves the most distance, as long as the truck can still carry the load" — that single rule, applied repeatedly, carves a good solution out of an exponential search space in quadratic time.

Sixty years after Clarke and Wright published it, their heuristic still runs inside routing software dispatching millions of vehicles every day. The problem it tackles — the Vehicle Routing Problem — remains NP-hard, and P vs NP remains unsolved. Until that changes, greedy savings and clever local search are the best tools we have.