The Travelling Salesman Problem

The travelling salesman problem asks a simple question: given a list of cities and the distances between them, what is the shortest route that visits every city exactly once and returns to the start? Stating it takes one sentence. Solving it efficiently, for every possible input, has defeated computer science for nearly a century.

From parlour game to military think tank

The idea is older than the computer. In 1857 the Irish mathematician William Rowan Hamilton invented the icosian game, a wooden puzzle that challenged players to trace a route around the twenty corners of a dodecahedron, visiting each exactly once. Hamilton sold the rights to a London game maker. It was not a commercial hit, but the underlying object, a cycle through every vertex of a graph, still carries his name.

The modern problem took shape in the 1930s. Karl Menger discussed what he called the messenger problem at his mathematics colloquium in Vienna, and noted something that turned out to be prophetic: the obvious approach of always walking to the nearest unvisited point does not generally give the shortest route. Around the same time the phrase “travelling salesman problem” began circulating at Princeton.

Serious computational work started in 1954 at the RAND Corporation, where George Dantzig, Ray Fulkerson and Selmer Johnson solved a 49-city instance, one city in each US state plus Washington, DC. Their method, cutting planes bolted onto linear programming, settled a question about American road distances and then outgrew it: the technique became a foundation of combinatorial optimisation, and its descendants still power the best exact solvers today.

Why brute force collapses

The obvious algorithm is to try every route. For n cities there are (n-1)!/2 distinct tours, and that factorial is the whole story. With 10 cities there are 181,440 possibilities, which a laptop dispatches without noticing. With 20 cities there are roughly 60 quadrillion, about 6 × 10^16. A machine checking a billion tours per second would need around two years. By 60 cities the count is near 7 × 10^79, in the same territory as the estimated number of atoms in the observable universe. You can watch this explosion happen in the demo above: the route counter climbs politely for the first few cities, then runs away.

Cleverness helps less than you might hope. The best exact method with a proven worst-case bound, the Held-Karp dynamic programming algorithm from 1962, cuts the factorial down to roughly 2^n steps. That is an enormous improvement and still hopeless: 2^n passes a trillion before n reaches 41.

The frustrating part is how easy the neighbouring problems are. Finding the shortest path between two fixed cities is a solved problem; Edsger Dijkstra’s algorithm from 1959 handles it in polynomial time and runs inside satnavs. Ask for one route between two points and the answer comes back instantly. Ask for one route through all the points and the difficulty changes category entirely.

What Karp proved

For decades nobody could say precisely why the problem resisted attack. The language arrived in the early 1970s, in the same burst of work that produced the P versus NP question. Stephen Cook showed in 1971 that Boolean satisfiability is NP-complete. A year later Richard Karp published “Reducibility Among Combinatorial Problems”, showing that 21 famous problems, the Hamiltonian cycle and the travelling salesman decision problem among them, are all NP-complete too.

NP-completeness is a statement about equivalence. Every problem in the class can be translated into every other with only polynomial overhead, so they stand or fall together. A polynomial-time algorithm for the travelling salesman problem would immediately yield one for satisfiability, scheduling, protein folding and thousands of catalogued cousins, and would prove P = NP. The consensus expectation is that no such algorithm exists, but after five decades there is still no proof either way. The intellectual roots of this framework go back to the 1930s work on computability covered in our foundations era page.

How the world copes anyway

Parcels still get delivered, which tells you something. In practice the problem is managed with heuristics: procedures that find good tours fast without promising the best one.

The simplest is nearest neighbour, Menger’s “walk to the closest unvisited city” rule. It is quick and usually mediocre, commonly landing 25% or so above the optimum, occasionally far worse. A standard follow-up is 2-opt, which looks for two edges of the tour that cross, uncrosses them, and repeats until no improving swap remains. The demo above animates both. On 15 cities, a size with over 43 billion possible tours, the pair typically produces a respectable route in a few milliseconds.

Guarantees are harder to come by. In 1976 Nicos Christofides published an algorithm (found independently by Anatoliy Serdyukov) that always returns a tour at most 1.5 times the optimum when distances obey the triangle inequality. That ratio then sat unimproved for 44 years. In 2020, Anna Karlin, Nathan Klein and Shayan Oveis Gharan finally beat it, with a randomised algorithm achieving 3/2 minus epsilon, for an epsilon greater than 10^-36. The margin is comically small. The point is that the barrier moved at all.

Exact solving has its own champion: Concorde, the code developed by William Cook and colleagues, which has set every record for provably optimal tours since 1992. Its high-water mark is pla85900, an 85,900-point instance arising from a chip-design application, solved in 2006 after a computation totalling about 136 CPU-years. Solved here means proven: the tour comes with a mathematical certificate that nothing shorter exists, no exhaustive check required.

Why anyone funds this

The salesman framing undersells the applications. Any task of the form “visit all of these once, cheaply” is this problem wearing different clothes. Delivery firms solve large instances daily when sequencing stops for their vans. Manufacturers solve it when a drill must visit thousands of hole positions on a circuit board, or a laser must move between features on a chip, since wasted head movement is wasted money. Geneticists have used TSP formulations to order markers on genome maps. Astronomers use it to schedule telescope observations. Cook’s group once computed a tour of more than 49,000 British pubs, mostly to prove a point about scale.

None of these users wait for the theoretical question to be settled. They use heuristics with known track records, accept tours a fraction of a percent above optimal, and get on with it.

The part that stays unsolved

Notice what the demo cannot do. It finds a short tour quickly, and after 2-opt has finished the route usually looks convincing. But looking convincing is not a proof. Confirming that no shorter tour exists among the billions of alternatives is the expensive half of the problem, and that half is where the mystery lives.

A polynomial-time exact algorithm would collapse the gap and collect the Clay Mathematics Institute’s million-dollar prize for resolving P versus NP in the affirmative. It would also have consequences well beyond logistics, since the security assumptions behind modern cryptography lean on certain problems staying hard, a theme we cover in breaking Bitcoin. A proof in the other direction, that no fast algorithm can exist, would be just as celebrated and looks just as far away.

Until one arrives, the travelling salesman problem remains what it was in Menger’s Vienna colloquium: a one-sentence question that nobody can close.