allanninal.dev/build

Part 3 of 7 · Delivery route planner series ~8 min read

How a route gets optimized

This is the heart of the system, and the part people assume needs clever AI — it doesn’t. This post is about the optimiser: how a flat list of geocoded stops becomes an ordered route with plain code, why nearest-neighbour then 2-opt is the right tool for a few dozen stops, and what ‘optimised’ honestly means when time windows and a van’s capacity get a veto.

Key takeaways

  • First build a matrix of travel times between the depot and every stop — from a hosted service, or a straight-line estimate.
  • Seed a route with nearest-neighbour: start at the depot, always hop to the closest stop not yet visited.
  • Improve it with 2-opt: repeatedly find two legs that cross and reverse the bit between them to uncross the route.
  • Time windows and van capacity are hard constraints — a swap that breaks either is rejected, not accepted because it’s shorter.
  • It’s a strong, fast heuristic for dozens of stops — reliably close to best, in milliseconds — not a proof of the shortest route.

First, a matrix

You can’t order stops without knowing the cost of going from each one to each other one. So the first thing the optimiser builds is a matrix: for every pair of points — the depot and all the stops — how long does it take to drive between them? With n stops plus the depot, that’s an (n+1) × (n+1) grid of travel times.

There are two honest ways to fill it. The accurate way is a hosted distance-matrix service, which knows real roads, one-way streets, and typical traffic; you send it the coordinates and it returns the grid. The cheap way is to compute straight-line (haversine) distances between coordinates and multiply by a fudge factor for the fact that roads aren’t straight. The hosted matrix gives a better route and costs per call; the straight-line estimate is free and good enough for dense urban rounds where everything is close together. The planner uses whichever the settings doc names, and caches the matrix for the day so the same grid isn’t bought twice. Either way, once the matrix exists, the rest of the optimiser never touches a map again — it just reads numbers from the grid.

A first guess: nearest-neighbour

With the matrix in hand, the optimiser needs a starting route — any complete, valid order it can then improve. The simplest sensible one is nearest-neighbour: start at the depot, look at every stop not yet visited, go to the closest one, and repeat until they’re all done, then return to the depot. It’s greedy — it only ever looks at the next hop — and it’s fast, and it produces a route that’s roughly right but usually has a few ugly legs near the end, where the only unvisited stops left are back the way you came.

Nearest-neighbour isn’t the answer; it’s the first draft. Its job is to give 2-opt something to chew on.

Uncrossing the route: 2-opt

The clearest sign of a bad route is a crossing — two legs of the round that overlap on the map. Whenever a route crosses itself, you can always make it shorter by uncrossing that pair of legs, and that’s exactly what 2-opt does. It takes two legs of the current route, reverses the run of stops between them, and checks the matrix: is the new route shorter? If yes, keep it. If no, put it back. Do that for every pair of legs, over and over, until a full pass finds no improving swap. What’s left is a route with no crossings and no obvious slack.

A nearest-neighbour route that crosses itself, and the same stops after a 2-opt swap uncrosses it Two panels side by side, each showing a depot and five stops labelled A through E. In the left panel, titled the nearest-neighbour seed, the route runs depot to A to C to B to E and back to depot; the leg from A to C and the leg from B to E cross over each other in the middle, and the route is labelled about 38 miles. In the right panel, titled after 2-opt, the same five stops are visited in the order depot to A to B to C to E and back to depot; no legs cross, the path makes a clean loop, and it is labelled about 33 miles. The point illustrated: reversing the segment between two crossing legs removes the crossing and shortens the route. Nearest-neighbour seed ~38 miles — A–C and B–E cross depot A B C E After 2-opt ~33 miles — no crossings depot A B C E
Fig 3. Nearest-neighbour gives a route that crosses itself (left): the leg A–C and the leg B–E overlap. 2-opt reverses the segment between them, visiting A–B–C–E instead (right). The crossing is gone and the round is shorter.

A worked example

Take the five stops above. Nearest-neighbour starts at the depot and goes to A (the closest). From A, the nearest unvisited stop turns out to be C, because the greedy step only looks at the next hop and C is marginally closer than B at that moment. From C it picks B, from B it picks E, and back to the depot. That gives the order depot → A → C → B → E → depot — about 38 miles — and you can see the problem on the left panel: the leg from A down to C and the leg from B down to E cross right through the middle of the map. The greedy “always go to the nearest” rule painted itself into that corner near the end.

2-opt spots it. It tries reversing the segment between those two crossing legs — the run C–B becomes B–C — turning the order into depot → A → B → C → E → depot. It checks the matrix: the new order is about 33 miles, five miles shorter, so it keeps it. The crossing is gone (right panel), and a second pass finds no further improving swap, so the optimiser stops. Five miles on one small round, every single day, is the whole reason this step exists.

Windows and capacity get a veto

Pure 2-opt only cares about distance. A real round has two extra rules that distance must never be allowed to break, so they’re enforced as hard constraints: every candidate route — the nearest-neighbour seed and every 2-opt swap — is checked against them before it can be accepted.

  • Time windows. The optimiser walks the candidate route forward from the depot, adding travel time and the average time spent at each stop, and asks: does every timed stop get reached inside its window? A swap that shaves a mile but pushes the “before noon” office to 12:10 is rejected, even though it’s shorter. Shorter is only better when it’s also on time.
  • Capacity. If a van can’t carry the whole day, the stops are split across vans (or across two trips), and no van’s running load is ever allowed to exceed what it holds. A swap that would overfill a vehicle is rejected the same way.

So the optimiser isn’t minimising distance in the abstract — it’s finding the shortest route among the ones that are actually allowed. That distinction is the difference between a clever-looking plan and a plan a driver can really run.

What “optimised” honestly means

It’s worth being straight about this, because the word “optimised” oversells easily. Nearest-neighbour plus 2-opt is a heuristic. It does not prove it has found the single shortest possible route — finding that, guaranteed, is the travelling-salesman problem, which gets brutally expensive as stops multiply. What this approach does is reliably get very close, very fast: for the few-dozen-stops range a small business actually runs, it returns a route within a few percent of optimal in milliseconds, on plain Lambda, for nothing. That trade — “almost certainly near-best, instantly and free” over “provably best, slowly and expensively” — is exactly the right one for a two-van florist, and it’s why there is no model anywhere in this step. The maths has been understood for fifty years; it just needed wiring up.

Why this shape

  • Build the matrix once. Every later step reads travel times from the grid instead of touching a map.
  • Seed, then improve. Nearest-neighbour gives a fast first draft; 2-opt polishes it by uncrossing legs.
  • Constraints beat distance. Time windows and capacity have a veto; a shorter route that breaks them is rejected.
  • Heuristic, not oracle. Near-best in milliseconds for nothing, not provably-best slowly — the right trade at this scale.
  • No model on the route. The whole optimiser is deterministic Python; the same stops always give the same plan.
All posts