Introduction

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.

Try 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)s(i, j) = d(0, i) + d(0, j) - d(i, j)

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

<!-- Demo layout: info bar + canvas for route visualization + control buttons -->
<div class="info-bar">
  <span id="total-dist">Total distance: —</span>
  <span id="step-info"></span>
</div>
<canvas id="canvas" width="360" height="270"></canvas>
<p class="hint-txt" id="hint-txt">Each customer has its own out-and-back trip. Press Step to apply the best savings merge.</p>
<div class="btns">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run all</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Styles for the Clarke-Wright savings demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Clarke-Wright Savings Algorithm
// 1. Start with one route per customer (depot -> customer -> depot).
// 2. Compute savings s(i,j) = d(0,i) + d(0,j) - d(i,j) for all pairs.
// 3. Greedily merge the highest-saving pair that respects capacity.

// Depot node (center of canvas)
const DEPOT = { x: 180, y: 135, label: 'D' };
// Customer nodes with positions and unit demand
const CUSTOMERS = [
  { x:  60, y:  60, label: 'A', demand: 1 },
  { x: 290, y:  55, label: 'B', demand: 1 },
  { x: 310, y: 180, label: 'C', demand: 1 },
  { x: 240, y: 240, label: 'D', demand: 1 },
  { x:  80, y: 230, label: 'E', demand: 1 },
  { x: 150, y: 170, label: 'F', demand: 1 }
];
// Truck capacity: max customers per route
const CAPACITY = 3;

function dist(a, b) {
  // Euclidean distance between two points
  const dx = a.x - b.x, dy = a.y - b.y;
  return Math.sqrt(dx * dx + dy * dy);
}

// Compute and sort all pairwise savings (descending)
function computeSavings() {
  const n = CUSTOMERS.length;
  const sav = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const s = dist(DEPOT, CUSTOMERS[i]) + dist(DEPOT, CUSTOMERS[j]) - dist(CUSTOMERS[i], CUSTOMERS[j]);
      sav.push({ i, j, s });
    }
  }
  sav.sort((a, b) => b.s - a.s);
  return sav;
}

// Mutable state: list of routes, sorted savings, step counter
let routes = [];
let savings = [];
let stepsDone = 0;
let mergeCount = 0;

// Initialize: one singleton route per customer
function initRoutes() {
  routes = CUSTOMERS.map((c, idx) => ({ nodes: [idx], load: c.demand }));
  savings = computeSavings();
  stepsDone = 0;
  mergeCount = 0;
}

// Sum of all route distances (depot out + edges + depot back)
function totalDistance() {
  let d = 0;
  for (const r of routes) {
    // Leg from depot to first customer
    d += dist(DEPOT, CUSTOMERS[r.nodes[0]]);
    for (let k = 0; k < r.nodes.length - 1; k++) {
      d += dist(CUSTOMERS[r.nodes[k]], CUSTOMERS[r.nodes[k + 1]]);
    }
    // Leg from last customer back to depot
    d += dist(CUSTOMERS[r.nodes[r.nodes.length - 1]], DEPOT);
  }
  return d;
}

// Check if merging routes rA and rB at endpoints si->sj is feasible
function canMerge(rA, rB, si, sj) {
  // Merge is valid only if si is the tail of rA and sj is the head of rB
  // or the reverse — and the combined load must not exceed CAPACITY
  const endA = rA.nodes[rA.nodes.length - 1] === si;
  const startB = rB.nodes[0] === sj;
  const startA = rA.nodes[0] === si;
  const endB = rB.nodes[rB.nodes.length - 1] === sj;
  const ok1 = endA && startB;
  const ok2 = startA && endB;
  if (!ok1 && !ok2) return null;
  if (rA.load + rB.load > CAPACITY) return null;
  return ok1 ? 'forward' : 'reverse';
}

// Concatenate routes in the correct direction
function doMerge(rA, rB, dir) {
  if (dir === 'forward') {
    return { nodes: [...rA.nodes, ...rB.nodes], load: rA.load + rB.load };
  }
  // Reverse merge: B’s tail meets A’s head
  return { nodes: [...rB.nodes, ...rA.nodes], load: rA.load + rB.load };
}

// Apply the next feasible merge from the sorted savings list
function step() {
  while (stepsDone < savings.length) {
    const sv = savings[stepsDone];
    stepsDone++;
    const { i, j } = sv;
    // Find which routes currently contain customers i and j
    let rIdxA = -1, rIdxB = -1;
    for (let k = 0; k < routes.length; k++) {
      if (routes[k].nodes.includes(i)) rIdxA = k;
      if (routes[k].nodes.includes(j)) rIdxB = k;
    }
    if (rIdxA === -1 || rIdxB === -1 || rIdxA === rIdxB) continue;
    const dir = canMerge(routes[rIdxA], routes[rIdxB], i, j);
    if (!dir) {
      // Try the other direction (j at tail of rB, i at head of rA)
      const dir2 = canMerge(routes[rIdxB], routes[rIdxA], j, i);
      if (!dir2) continue;
      const merged = doMerge(routes[rIdxB], routes[rIdxA], dir2);
      const keep = routes.filter((_, k) => k !== rIdxA && k !== rIdxB);
      routes = [...keep, merged];
    } else {
      const merged = doMerge(routes[rIdxA], routes[rIdxB], dir);
      const keep = routes.filter((_, k) => k !== rIdxA && k !== rIdxB);
      routes = [...keep, merged];
    }
    mergeCount++;
    return true;
  }
  return false;
}

// Draw all routes, depot, and customers on the canvas
const ROUTE_COLORS = ['#e63946', '#457b9d', '#2a9d8f', '#e9c46a', '#f4a261', '#8338ec'];

function draw() {
  const canvas = document.getElementById('canvas');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Draw each route as a colored polyline from depot to customers and back
  routes.forEach((r, ri) => {
    ctx.strokeStyle = ROUTE_COLORS[ri % ROUTE_COLORS.length];
    ctx.lineWidth = 2;
    ctx.beginPath();
    ctx.moveTo(DEPOT.x, DEPOT.y);
    r.nodes.forEach(ni => ctx.lineTo(CUSTOMERS[ni].x, CUSTOMERS[ni].y));
    ctx.lineTo(DEPOT.x, DEPOT.y);
    ctx.stroke();
  });

  // Draw the depot as a filled circle with ’D’ label
  ctx.fillStyle = '#1d3557';
  ctx.beginPath();
  ctx.arc(DEPOT.x, DEPOT.y, 8, 0, Math.PI * 2);
  ctx.fill();
  ctx.fillStyle = '#fff';
  ctx.font = 'bold 9px system-ui';
  ctx.textAlign = 'center';
  ctx.textBaseline = 'middle';
  ctx.fillText('D', DEPOT.x, DEPOT.y);

  // Draw each customer as a white circle with a letter label
  CUSTOMERS.forEach((c, i) => {
    ctx.fillStyle = '#fff';
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 1.5;
    ctx.beginPath();
    ctx.arc(c.x, c.y, 10, 0, Math.PI * 2);
    ctx.fill();
    ctx.stroke();
    ctx.fillStyle = '#1d3557';
    ctx.font = 'bold 10px system-ui';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(c.label, c.x, c.y);
  });
}

function updateUI() {
  const d = totalDistance();
  document.getElementById('total-dist').textContent =
    i18nFmt('Total distance: %d% px', { d: Math.round(d) });
  const done = stepsDone >= savings.length;
  document.getElementById('btn-step').disabled = done;
  document.getElementById('btn-run').disabled = done;
  if (done) {
    document.getElementById('hint-txt').textContent =
      i18nFmt('All %m% merge(s) applied — %r% route(s) remain. That’s the Clarke-Wright solution!', { m: mergeCount, r: routes.length });
    document.getElementById('step-info').textContent = 'Done';
  }
}

document.getElementById('btn-step').addEventListener('click', () => {
  const merged = step();
  draw();
  updateUI();
  if (merged) {
    document.getElementById('step-info').textContent =
      i18nFmt('Step %s% / %t%', { s: stepsDone, t: savings.length });
    document.getElementById('hint-txt').textContent =
      i18nFmt('Merged %m% time(s) — now %r% route(s).', { m: mergeCount, r: routes.length });
  }
});

document.getElementById('btn-run').addEventListener('click', () => {
  while (step()) {}
  draw();
  updateUI();
});

document.getElementById('btn-reset').addEventListener('click', () => {
  initRoutes();
  draw();
  document.getElementById('total-dist').textContent =
    i18nFmt('Total distance: %d% px', { d: Math.round(totalDistance()) });
  document.getElementById('step-info').textContent = '';
  document.getElementById('hint-txt').textContent = 'Each customer has its own out-and-back trip. Press Step to apply the best savings merge.';
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled = false;
});

initRoutes();
draw();
document.getElementById('total-dist').textContent =
  i18nFmt('Total distance: %d% px', { d: Math.round(totalDistance()) });
Result
Console

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 Real Complexity

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 nn customers there are roughly n!n! orderings; with 20 customers that already exceeds 101810^{18}.
  • Clarke-Wright runs in O(n2)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 32\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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/vehicle-routing-savings/Content licensed under CC BY-NC 4.0.