Introduction

Every morning a depot fills its trucks and sends them out. A hundred packages, six drivers, one question: who delivers what, and in which order? Get it wrong and trucks crisscross the city burning fuel and overtime. Get it right and the same deliveries finish hours earlier.

This is the Vehicle Routing Problem (VRP). You have one depot, a fleet of vehicles, and a set of customers to serve. Each truck leaves the depot, visits some customers, and returns. The goal is to serve everyone at the least total cost — usually total distance or time — often while respecting limits like how much each truck can carry.

It sounds like a scheduling chore. It is, in fact, one of the most studied hard problems in all of optimization, and shaving even a few percent off the answer is worth billions to the companies that move the world's goods.

Assign the Stops

Below is a depot (the square) and eight delivery stops. Two trucks must cover them all. Click a stop to send it to the other truck, and each truck instantly re-orders its own stops with a quick nearest-neighbor tour. Watch the total length at the bottom.

<p class="hint">The square is the <b>depot</b>; the circles are delivery stops. Two trucks must cover them all. Click a stop to <b>move it to the other truck</b> — each truck instantly re-routes itself with a nearest-neighbor tour. Lower total = better.</p>
<svg id="map" viewBox="0 0 320 240" role="img" aria-label="Routing map"></svg>
<div class="legend">
  <span><i class="sw a"></i>Truck A <b id="lenA">0</b></span>
  <span><i class="sw b"></i>Truck B <b id="lenB">0</b></span>
  <span class="tot">Total <b id="total">0</b></span>
</div>
<div class="btns">
  <button id="balance" type="button">Auto-balance</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status">Click any stop to reassign it.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#map { width: 100%; max-width: 460px; height: auto; background: #f5f7fa;
       border: 1px solid #d7dee6; border-radius: 10px; display: block; }
.stop { cursor: pointer; }
.stop circle { transition: r .1s; }
.stop:hover circle { r: 9; }
.legend { display: flex; gap: 1.1rem; flex-wrap: wrap; align-items: center;
          font-size: .92rem; margin: .6rem 0; }
.legend b { font-variant-numeric: tabular-nums; }
.legend .tot { font-weight: 600; }
.sw { display: inline-block; width: 14px; height: 4px; border-radius: 2px; margin-right: .4rem; vertical-align: middle; }
.sw.a { background: #2563eb; } .sw.b { background: #e8590c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.3em; color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Vehicle Routing (2 trucks, 1 depot). Each truck visits its assigned stops with a nearest-neighbor tour starting and ending at the depot; the route length is the sum of leg distances. The total cost is lenA + lenB. Clicking a stop flips which truck owns it. "Auto-balance" brute-forces all 2^8 assignments and keeps the best — exactly the kind of exponential search that makes VRP NP-hard at real scale.
const DEPOT = { x: 160, y: 120 };
const STOPS = [
  { x: 60, y: 50 }, { x: 110, y: 40 }, { x: 250, y: 55 }, { x: 285, y: 110 },
  { x: 250, y: 190 }, { x: 150, y: 205 }, { x: 55, y: 180 }, { x: 40, y: 110 }
];
// assign[i] = 0 (Truck A) or 1 (Truck B)
let assign = STOPS.map((_, i) => (i % 2));

const dist = (p, q) => Math.hypot(p.x - q.x, p.y - q.y);

// Nearest-neighbor tour from the depot through `idxs`, back to depot. Returns {len, order} where order is the visiting sequence of stop indices.
function tour(idxs) {
  if (idxs.length === 0) return { len: 0, order: [] };
  const remaining = idxs.slice();
  const order = [];
  let cur = DEPOT, len = 0;
  while (remaining.length) {
    let best = 0;
    for (let k = 1; k < remaining.length; k++)
      if (dist(cur, STOPS[remaining[k]]) < dist(cur, STOPS[remaining[best]])) best = k;
    const next = remaining.splice(best, 1)[0];
    len += dist(cur, STOPS[next]); order.push(next); cur = STOPS[next];
  }
  len += dist(cur, DEPOT); // return to depot
  return { len, order };
}

function costOf(a) {
  const A = [], B = [];
  a.forEach((t, i) => (t === 0 ? A : B).push(i));
  const ta = tour(A), tb = tour(B);
  return { lenA: ta.len, lenB: tb.len, total: ta.len + tb.len, ta, tb, A, B };
}

function path(d, color) {
  if (!d.order.length) return '';
  const pts = [DEPOT, ...d.order.map(i => STOPS[i]), DEPOT];
  const dd = pts.map((p, i) => (i ? 'L' : 'M') + p.x + ' ' + p.y).join(' ');
  return `<path d="${dd}" fill="none" stroke="${color}" stroke-width="2.5" stroke-linejoin="round" opacity="0.85"/>`;
}

function render() {
  const c = costOf(assign);
  const svg = document.getElementById('map');
  let s = path(c.ta, '#2563eb') + path(c.tb, '#e8590c');
  STOPS.forEach((p, i) => {
    const col = assign[i] === 0 ? '#2563eb' : '#e8590c';
    s += `<g class="stop" data-i="${i}"><circle cx="${p.x}" cy="${p.y}" r="7" fill="${col}" stroke="#fff" stroke-width="1.5"/></g>`;
  });
  s += `<rect x="${DEPOT.x - 9}" y="${DEPOT.y - 9}" width="18" height="18" rx="3" fill="#1d3557" stroke="#fff" stroke-width="1.5"/>`;
  svg.innerHTML = s;
  svg.querySelectorAll('.stop').forEach(g => g.addEventListener('click', () => {
    const i = +g.dataset.i; assign[i] = assign[i] === 0 ? 1 : 0;
    setStatus('Stop reassigned — routes recomputed.'); render();
  }));
  document.getElementById('lenA').textContent = Math.round(c.lenA);
  document.getElementById('lenB').textContent = Math.round(c.lenB);
  document.getElementById('total').textContent = Math.round(c.total);
}
function setStatus(t) { document.getElementById('status').textContent = t; }

// Brute force: try every 0/1 assignment of the 8 stops, keep the cheapest total.
function balance() {
  const n = STOPS.length; let best = null, bestCost = Infinity, checked = 0;
  for (let mask = 0; mask < (1 << n); mask++) {
    checked++;
    const a = []; for (let i = 0; i < n; i++) a.push((mask >> i) & 1);
    const t = costOf(a).total;
    if (t < bestCost) { bestCost = t; best = a; }
  }
  assign = best; render();
  setStatus(fmt('Best split found after checking %checked% of %v% assignments.', { checked: checked, v: 1 << n }));
  console.log('Optimal (under NN routing) total =', Math.round(bestCost), '| checked', checked, 'splits');
}

document.getElementById('balance').addEventListener('click', balance);
document.getElementById('reset').addEventListener('click', () => {
  assign = STOPS.map((_, i) => (i % 2)); setStatus('Click any stop to reassign it.'); render();
});
render();
Result
Console

Try to make the total as small as you can, then press Auto-balance to let the computer search. Notice the tension: each truck wants a short, tight loop, but the two loops must together cover every stop. With just eight stops there are already 282^{8} = 256 ways to split them between two trucks — and real fleets have hundreds of stops and many trucks, where the number of splits is astronomically larger.

The Real Complexity

How hard is the Vehicle Routing Problem, really?

  • It contains TSP. Give VRP a single truck with unlimited capacity and the problem collapses into the Traveling Salesman Problem: find one shortest tour through every stop. Because that special case is already NP-hard, VRP is NP-hard too — at least as hard, and usually harder.
  • Capacity makes it worse. The standard industrial version, the Capacitated VRP (CVRP), adds a load limit per truck, so you must simultaneously partition the stops into feasible groups and route each group. Two hard problems welded together.
  • Brute force is hopeless. Splitting n stops among k trucks and then ordering each route blows up factorially. Exact solvers using branch-and-cut and column generation can prove optimality for instances up to a few hundred customers, but they can grind for hours and don't scale to a nationwide fleet.
  • Status: NP-hard, not undecidable, not a Millennium problem. There is no known efficient (polynomial-time) algorithm, and finding one would settle P vs NP. So in practice, industry abandons "perfect" and runs heuristics and metaheuristics — savings algorithms, local search, large-neighborhood search — that return very good routes fast, without any guarantee they are the absolute best.

That is the quiet truth behind your delivery app: the route you got was almost certainly not provably optimal. It was good enough, found fast enough, because optimal is out of reach.

Where It Matters

"Send a fleet out and bring it back cheaply" describes a startling share of the physical economy:

  • Parcel and grocery delivery: the last mile is the single most expensive leg of shipping, and routing is where it is won or lost.
  • Waste collection and street sweeping: garbage trucks are classic capacitated routing, with the dump as a second depot.
  • School buses: route students to school under time windows and capacity — a VRP that touches millions of children daily.
  • Field service and home health: technicians or nurses visiting clients are vehicles serving customers with time windows.
  • Ride-pooling and on-demand transit: matching riders to shared vehicles is dynamic vehicle routing solved in real time.

Because the prize is so large, VRP is one of the most commercially valuable optimization problems on Earth — close cousin to bin packing when capacity dominates, and built on the same intractable core as the Traveling Salesman Problem.

Conclusion

The Vehicle Routing Problem is the Traveling Salesman Problem grown up: not one traveler but a whole fleet, not just an order but also a partition, and capacity limits on top. That extra structure keeps it firmly NP-hard, with no efficient algorithm known and none expected unless P vs NP surprises us all.

And yet the trucks still roll. The lesson of VRP is the lesson of modern optimization: when "best" is unreachable, "demonstrably very good, found fast" is what keeps the world's parcels moving. Every package you receive is a small monument to a hard problem we cannot solve — but have learned to live with brilliantly.

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/Content licensed under CC BY-NC 4.0.