Every morning, someone solves a problem no computer can solve.

One bus is a TSP. Several buses is an mTSP. Add capacity and it's a CVRP — which is the one districts actually solve.

Get the names right, because your students will meet them in the wild and the names are load-bearing.

Why it's hard

Count the answers. That's the whole argument.

One bus, n stops. Fix the depot, walk the stops in some order, come home. That's (n−1)! orders — and each tour is identical to its own reverse, so halve it: (n−1)! / 2. Nothing below is a lookup. Every digit is computed in your browser with BigInt, right now.

The algorithm that solved it

Six stages. Each one's flaw picks the next — and every cost here is measured, not claimed.

This table is live output from the school you picked on tab 1. Click any row to see that stage's routes on the map. Watch the crossings column: it's the one that tells the truth.

The pipeline, in the code that is actually running

Not pseudocode. This is copied from the script in this file — the same functions that produced the table above. Nothing here is magic, and you can read all of it.

// 1 · CLUSTER — sweep by angle from the depot, respecting capacity.
//     Fan a ray around the school. Fill a bus as it passes stops. Cut when full.
//     Target is re-balanced at each bus so the loads come out even.
function sweep(stops, dem, K, cap){
  const order = stops.slice().sort((a,b) => ang[a] - ang[b]);   // ang = atan2 from depot
  let b = 0, load = 0, left = total, busesLeft = K;
  let target = Math.min(cap, Math.ceil(left / busesLeft));
  for (const s of order){
    const d = dem[s];
    if (load > 0 && (load + d > cap || (b < K-1 && load + d > target)) && b < K-1){
      b++; busesLeft--; left -= load; load = 0;
      target = Math.min(cap, Math.ceil(left / Math.max(1, busesLeft)));
    }
    if (load + d > cap){ unserved.push(s); continue; }  // ← the fleet is too small. say so.
    routes[b].push(s); load += d;
  }
}

// 2 · CONSTRUCT — nearest neighbour. Greedy, fast, and it will regret this.
function nnTour(stops, D){
  let at = DEPOT, left = new Set(stops), out = [];
  while (left.size){
    let best = null, bd = Infinity;
    for (const s of left) if (D[at][s] < bd){ bd = D[at][s]; best = s; }
    out.push(best); left.delete(best); at = best;        // ← no lookahead. ever.
  }
  return out;
}

// 2b · CONSTRUCT — Clarke-Wright savings (1964). The classic, and worth the name.
//      Start with every stop on its own out-and-back. Merging i and j saves:
//          s(i,j) = d(depot,i) + d(depot,j) − d(i,j)
//      …the two half-trips you no longer drive. Merge biggest saving first,
//      while capacity allows. Notice what it does NOT need to be told: how many
//      buses. It discovers that — sometimes more than you own.
const S = pairs.map(([i,j]) => [ D[0][i] + D[0][j] - D[i][j], i, j ])
               .sort((a,b) => b[0] - a[0]);
for (const [saving, i, j] of S){
  if (saving <= 0) break;                      // merging costs more than it saves
  if (endpoint(i) && endpoint(j) && route(i) !== route(j)
      && load(i) + load(j) <= cap) merge(i, j);
}

// 3 · IMPROVE — 2-opt. THE line of this entire page is the delta:
function twoOpt(route, D){
  const t = [DEPOT, ...route, DEPOT];
  let improved = true;
  while (improved){
    improved = false;
    for (let i = 1; i < t.length-2; i++){
      for (let j = i+1; j < t.length-1; j++){
        const a = t[i-1], b = t[i], c = t[j], d = t[j+1];
        // drop edges a→b and c→d, add a→c and b→d, reverse everything between.
        const delta = (D[a][c] + D[b][d]) - (D[a][b] + D[c][d]);
        if (delta < -1e-9){ reverse(t, i, j); improved = true; }
      }
    }
  }
  return t.slice(1, -1);     // ← halts only when NO pair-swap helps. a local optimum.
}

// 4 · IMPROVE — Or-opt. Lift a run of 1–3 stops out and re-insert it elsewhere,
//     forwards or backwards. Catches what 2-opt structurally cannot: a single
//     stop sitting in the wrong cluster of the same route.

The schedule

Distance is what the algorithm minimises. Ride time is what a parent calls about.

One row per bus and driver. Blocks are stops — taller means more riders. The red line is the bell, and everyone has to be left of it. Riders whose ride is longer than your threshold turn amber.

Honesty markers

Everything this page is not.

—