Planning errands is the travelling salesman problem in disguise

For the Monash × Shortcut Asia Internship Challenge I built an Errand Route Planner: drop your stops on a map, and it tells you which order to visit them in so the whole trip is as short as possible.

It sounds like a small app. Underneath, it's one of the most famous hard problems in computer science.

The problem underneath

"Visit every stop once and come back home, as cheaply as possible" is the travelling salesman problem (TSP). It's NP-hard: no known algorithm solves every instance quickly, and the obvious approach (try every order) explodes.

With n stops after the starting point, there are n! orders to try:

Stops	Orders to try
5	120
10	3,628,800
15	about 1.3 trillion

Nobody runs 15 errands in one afternoon, but the table shows why "just try them all" stops being an option very quickly.

So the planner uses two strategies, and picks one based on how many stops there are.

Small trips: Held-Karp, the exact answer

Held-Karp is a dynamic-programming algorithm that finds the optimal route without trying every order. The key idea is that the best way to finish a route only depends on two things:

• which stops you've already visited (a set, stored as a bitmask), and
• where you are right now.

It doesn't matter what order you visited the earlier stops in. So instead of n! orders, there are only about 2ⁿ · n states to fill in:

best[visited][last] = shortest path that starts at home,
                      visits exactly the stops in `visited`,
                      and ends at `last`

best[{j}][j]        = dist(home, j)
best[S][j]          = min over k in S, k ≠ j, of
                      best[S − {j}][k] + dist(k, j)

answer              = min over j of best[all][j] + dist(j, home)

A simplified TypeScript version of the core loop:

function heldKarp(dist: number[][]): number {
  const n = dist.length - 1;             // stop 0 is home
  const FULL = 1 << n;
  const best = Array.from({ length: FULL }, () => new Array(n).fill(Infinity));

  for (let j = 0; j < n; j++) best[1 << j][j] = dist[0][j + 1];

  for (let mask = 1; mask < FULL; mask++) {
    for (let j = 0; j < n; j++) {
      if (!(mask & (1 << j)) || best[mask][j] === Infinity) continue;
      for (let k = 0; k < n; k++) {
        if (mask & (1 << k)) continue;   // already visited
        const next = mask | (1 << k);
        const cost = best[mask][j] + dist[j + 1][k + 1];
        if (cost < best[next][k]) best[next][k] = cost;
      }
    }
  }

  let answer = Infinity;
  for (let j = 0; j < n; j++) answer = Math.min(answer, best[FULL - 1][j] + dist[j + 1][0]);
  return answer;
}

The real version also remembers which stop each state came from, so it can walk backwards and recover the route itself, not just its length.

The cost is O(n² · 2ⁿ) time and O(n · 2ⁿ) memory. For a handful of stops that's instant. For 10 stops it's about 100,000 steps instead of 3.6 million orders. But 2ⁿ still grows fast, so past a certain size it's the wrong tool.

Big trips: nearest neighbour, then 2-opt

For larger trips the planner gives up on guaranteed optimal and aims for very good, very fast.

Step 1, nearest neighbour. Start at home and always go to the closest stop you haven't visited yet. It's O(n²) and gives a reasonable route, but it's greedy: it often paints itself into a corner and has to make one long, ugly trip back at the end.

Step 2, 2-opt. Take the greedy route and keep improving it. Pick two edges, A→B and C→D. If swapping them for A→C and B→D (and reversing the stretch in between) makes the route shorter, do it. Repeat until no swap helps.

before:  A → B → … → C → D      (the two edges cross)
after:   A → C → … → B → D      (the B…C stretch is reversed)

Geometrically, 2-opt uncrosses crossing paths. A route that crosses itself is never optimal, so removing every crossing gets you most of the way there. In practice, nearest neighbour plus 2-opt lands close to the true optimum.

The app around it

• Vite + React + TypeScript for the front end.
• Leaflet for the map: click to add stops, and the route is drawn as soon as it's solved.
• 17 passing tests. Route solvers are easy to get subtly wrong, and a wrong route still looks like a route on the map, so tests were the only way to trust them.

What I took away

• Recognise the classic problem under the product. "Order my errands" turned out to be TSP, and knowing that meant I could use 60 years of research instead of inventing something.
• Exact and heuristic can live together. Small inputs get a provably best answer; large ones get a fast, good answer. The user just sees a route.
• An exact solver is also a test oracle. On small inputs, Held-Karp gives the true optimum, which is the yardstick for how good the 2-opt routes really are.