Route optimisation software is selling a solution to a problem that has been proven hard for fifty years. Knowing which problem, and which part of it is hard, is the difference between evaluating a vendor and believing one.
The problem underneath
A driver leaves a depot, visits a set of stops once each, and returns. Minimise total travel. That is the travelling salesman problem, and it is a different thing from finding the shortest path between two points, which Dijkstra solved in 1956 and which runs in polynomial time. The TSP asks for an ordering, and the number of orderings grows factorially with the number of stops.
Note what has already been assumed. There is a travel cost between every pair of stops, so before any optimisation happens you need an n × n matrix — 200 stops is 39,800 ordered pairs. On real road networks that matrix is asymmetric, because one-way streets and turn restrictions mean the cost from A to B is not the cost from B to A. Building that matrix is often the expensive part of a production system, not the optimisation.
Four stops, worked by hand
Depot D at (0, 0), stops A (0, 3), B (4, 3), C (4, 0), in arbitrary distance units on a plane. With the depot fixed, four stops give 3! = 6 orderings, and each tour equals its own reversal, so there are three distinct tours:
edge lengths
D-A = 3 A-B = 4 B-C = 3 C-D = 4
D-B = sqrt(16+9) = 5 A-C = sqrt(16+9) = 5
tour 1 D-A-B-C-D = 3 + 4 + 3 + 4 = 14
tour 2 D-A-C-B-D = 3 + 5 + 3 + 5 = 16
tour 3 D-B-A-C-D = 5 + 4 + 5 + 4 = 18
Tour 1 is the rectangle’s perimeter and is optimal. Tour 3 is the bow tie: it uses both diagonals, and if you draw it the two edges D–B and A–C cross. That crossing is not a coincidence. In a metric space obeying the triangle inequality, a tour with crossing edges is never optimal, because replacing the two crossing edges with the two non-crossing ones is always shorter.
That replacement is the 2-opt move: pick two edges, remove them, reverse the segment between them and reconnect. Applied to tour 3, removing D–B and A–C and reconnecting gives D–A–B–C–D, taking 18 to 14 in one step. Almost every practical routing heuristic is built on repeatedly applying moves of this kind, and the reason they work well is exactly the geometric fact just used.
Why the same method dies at twenty
The method used above was enumeration: list every tour, keep the cheapest. For n stops plus a fixed depot there are (n − 1)! / 2 distinct tours. Turn the handle:
n = 4 3! / 2 = 3
n = 10 9! / 2 = 181,440
n = 15 14! / 2 = 87,178,291,200/2 = 43,589,145,600
n = 20 19! / 2 = 60,822,550,204,416,000
Ten stops is a hand calculation. Fifteen is 43.6 billion tours, which is minutes to hours of pure arithmetic. Twenty is 6.08 × 10¹⁶, which is not happening. A single delivery round is commonly 80 to 150 stops.
Enumeration is not the best exact method, and the difference is worth knowing. The Held–Karp dynamic program, published independently by Bellman and by Held and Karp in 1962, solves the TSP exactly in O(n² · 2ⁿ) time and O(n · 2ⁿ) memory by tabulating the cheapest path to each stop over each subset of visited stops:
n = 20 time 400 * 1,048,576 = 419,430,400 ops
memory 20 * 1,048,576 = 20,971,520 states
n = 25 time 625 * 33,554,432 = 20,971,520,000 ops
memory 25 * 33,554,432 = 838,860,800 states
n = 30 time 900 * 1,073,741,824 = 966,367,641,600 ops
memory 30 * 1,073,741,824 = 32,212,254,720 states
At 20 stops that is a few hundred million operations — entirely practical. At 30 it is the memory, not the time, that stops you: 32 billion states will not fit anywhere. So the exact frontier for a straightforward dynamic program is somewhere in the low twenties, which is why exact solvers for larger instances use a completely different approach — linear-programming relaxation with cutting planes and branch-and-bound, as in Concorde, which has proven optimality on instances with tens of thousands of points. “NP-hard” describes the worst case, not every instance.
The real problem is not the TSP
No delivery operation is solving a pure TSP, and the extra constraints are what actually make commercial software hard to replace:
- Multiple vehicles with capacity — the capacitated vehicle routing problem. Now you are choosing a partition of the stops and an ordering within each part, which is why good zone design reduces the problem so much: it fixes the partition.
- Time windows. A stop that must be served between 09:00 and 11:00 makes a tour infeasible rather than merely expensive, and feasibility checking is itself work. This is VRPTW, and it is the variant most real systems solve.
- Service time and shift length. The objective is usually total duty time, not distance, and a stop with fifteen minutes of paperwork is not the same as a letterbox drop.
- Time-dependent travel. The cost matrix changes through the day. A solution optimal against an 06:00 matrix can be infeasible against a 17:00 one, and there is no fixed matrix that is correct for both.
- Pickups mixed with deliveries add precedence constraints: you cannot deliver what you have not collected.
Two consequences. Christofides’ 1976 algorithm guarantees a tour within 1.5× the optimum, but only for metric, symmetric TSP — and road networks with one-way streets are asymmetric, so the guarantee does not apply to the problem you have. And with time windows the real difficulty may not be optimising at all: it may be finding any feasible assignment.
What solvers actually do
Production solvers construct a solution quickly, then improve it under a time limit, and stop when the clock runs out rather than when optimality is proven.
- Construct. Nearest-neighbour insertion is the obvious start and is genuinely poor — it strands one distant stop and pays for it at the end. The Clarke–Wright savings algorithm, from 1964, is the standard alternative for vehicle routing: start with one out-and-back trip per stop, then repeatedly merge the pair of trips whose merge saves the most distance, subject to capacity.
- Improve locally. 2-opt as worked above, plus Or-opt, which relocates a run of one to three consecutive stops elsewhere in the tour, plus cross-route exchanges that move stops between vehicles.
- Escape local optima. Pure local search stalls in a solution no single move improves. Guided local search, which is what Google’s OR-Tools uses by default for routing, penalises features of the current solution to push the search elsewhere; Lin–Kernighan-style methods, of which LKH is the best-known implementation, use variable-depth moves instead.
- Stop on a clock. You set a time limit — thirty seconds, five minutes — and take the best found. The number to care about is not the gap to the unknown optimum; it is the gap to the route the depot is running today, which is usually large.
Which is the practical point. A solver that gets within a few per cent of optimal in thirty seconds is worth far more than one that proves optimality overnight, because the travel-time matrix it optimised against was an estimate to begin with.
Top comments (0)