The Traveling Salesman Problem: The Hardest Easy Problem

Imagine you're a salesperson with 20 cities to visit. You need to find the shortest route that hits every city exactly once and brings you home at the end. Simple enough, right? You could try every possible route and pick the shortest.

Here's the catch: with 20 cities, there are roughly 60 billion possible routes. With 25 cities, over 310 trillion. With 30 cities, more routes than atoms in the observable universe. Even at a trillion routes checked per second, you wouldn't finish before the universe ends.

This is the Traveling Salesman Problem — arguably the most famous unsolved optimization problem in mathematics. It's trivial to explain to a child, yet has resisted exact efficient solution for nearly a century. It's not just a puzzle; it's a window into the deepest open question in all of computer science.

The Concept

The Traveling Salesman Problem (TSP) asks: given a list of cities and the distances between every pair of them, what is the shortest possible route that visits each city exactly once and returns to the starting point?

Mathematically, you're looking for the shortest Hamiltonian cycle in a complete weighted graph — a closed loop that touches every node exactly once with minimum total edge weight. The problem is deceptively compact. You can write it down in one sentence. You can explain it to anyone who's ever planned a road trip.

The brute-force approach — checking every possible route — collapses catastrophically as cities are added. The number of distinct tours grows as (n−1)!/2, a factorial function that explodes beyond any reasonable computation. Adding just one more city to a 20-city instance multiplies the search space by 20. This is what mathematicians mean when they say a problem is combinatorially explosive.

What makes TSP philosophically interesting is the gap between verification and solution. If someone hands you a proposed route, you can verify in seconds whether it's shorter than another by adding up distances. But finding the best route from scratch? Apparently infinitely harder — and that gap is at the heart of one of mathematics' greatest open questions.

Why It Matters

The Austrian mathematician Karl Menger first studied TSP formally in Vienna in the 1930s, calling it the Botenproblem — the "messenger problem." He immediately recognized that the obvious greedy strategy (always travel to the nearest unvisited city) doesn't work: it often produces tours far from optimal, sometimes dramatically so. Menger spotted this weakness before anyone had computers to test it.

The name "traveling salesman problem" entered the literature around 1948–1949, popularized by Merrill Flood at the RAND Corporation. In 1954, George Dantzig, Ray Fulkerson, and Selmer Johnson made the first landmark breakthrough: they solved the 49-city problem (one city per US state plus Washington D.C.) using a newly invented technique called the cutting-plane method. For the first time, a large TSP instance had been solved to proven optimality — not just a good route, but the best possible route, with a mathematical proof that nothing shorter existed.

Then in 1972, Richard Karp — who would later win the Turing Award — proved that TSP belongs to a class of problems called NP-hard. This was the theoretical earthquake that reframed everything. Karp showed that TSP is at least as hard as every problem in the class NP (nondeterministic polynomial time), meaning that if you could solve TSP efficiently, you could solve hundreds of other major problems efficiently too. TSP didn't just become an interesting puzzle — it became a lens for understanding the limits of computation itself.

The real-world stakes are enormous. The logistics industry spends billions optimizing delivery routes. UPS's ORION system (On-Road Integrated Optimization and Navigation) routes roughly 55,000 drivers daily using TSP-related algorithms. Circuit board manufacturing requires a drill to visit thousands of hole positions; minimizing that drill path saves significant production time. DNA sequencing tools use TSP-like algorithms to reassemble genome fragments from overlapping short reads — the "shortest superstring problem" of reassembly is mathematically equivalent to TSP. Even telescope scheduling — deciding how to point the Hubble Space Telescope at a list of targets while minimizing repositioning time between them — is a TSP instance.

TSP is everywhere. Any time you're asking "what's the most efficient order to do these things?", you're solving a version of it.

The Details

The P vs NP Connection

TSP's NP-hardness ties it directly to the most important open question in computer science: does P equal NP?

The class P contains problems solvable efficiently — in polynomial time (time that grows as n², n³, etc., rather than 2ⁿ or n!). The class NP contains problems where proposed solutions can be verified efficiently, even if finding them is hard. The question is whether these classes are actually the same — whether every problem whose answer you can quickly check can also be quickly solved.

The overwhelming consensus is that P ≠ NP. But no one has proved it. TSP is NP-hard, meaning: if someone found a polynomial-time algorithm to solve TSP exactly, they would simultaneously prove P = NP and claim the $1,000,000 Millennium Prize. Conversely, proving that TSP cannot be solved in polynomial time would prove P ≠ NP and win the same prize. TSP is, in a very real sense, a million-dollar problem — and has been since 2000 when the Millennium Prizes were established.

The Christofides–Serdyukov Algorithm

Since exact solution is likely impossible for large instances, mathematicians turned to approximation algorithms — approaches that can't guarantee the optimal tour but can guarantee a tour within some fixed factor of optimal.

In 1976, Nicos Christofides at Carnegie Mellon published a landmark result: an algorithm that, for any instance where distances satisfy the triangle inequality (essentially, that going directly is always at least as good as going via a detour), guarantees a tour no worse than 3/2 times the optimal length. The algorithm builds a minimum spanning tree of the cities, identifies cities with an odd number of connections, patches those with a minimum-weight matching, and shortcuts the result into a valid tour.

What's remarkable is that this 3/2 guarantee stood unimproved for 44 years.

Less remarked upon: Soviet mathematician Anatoliy Serdyukov independently discovered the same algorithm and submitted his paper in January 1976 — likely before Christofides' undated technical report. But Serdyukov published in a Russian-language journal in 1978, and the Cold War-era information gap meant his name was absent from Western textbooks for decades. The algorithm is increasingly called the Christofides–Serdyukov algorithm — a belated but deserved correction.

In 2021, Anna Karlin, Nathan Klein, and Shayan Oveis Gharan won the Best Paper Award at STOC (the premier theory of computing conference) for an algorithm that does fractionally better than 3/2. Their improvement is approximately 3/2 − 10⁻³⁶. The margin is so astronomically small it would never affect any real computation — you'd need a problem instance of cosmological scale before the difference materialized. But theoretically, the significance is enormous: it proves the 3/2 barrier is not a fundamental ceiling, that progress is still possible after nearly half a century.

The Scale of What's Been Solved

The Concorde solver, developed by David Applegate, Robert Bixby, Vašek Chvátal, and William Cook, is the gold standard for exact TSP computation. Its milestones read like an explorer's logbook:

1954: 49 cities (one per US state + D.C.) — proven optimal by Dantzig, Fulkerson, and Johnson
1998: All 13,509 US cities with population ≥ 500, solved to proven optimality by the Concorde team
2001: 15,112 German towns — required 585,936,700 CPU-seconds of computation
2004: 24,978 Swedish towns — optimal tour of approximately 72,500 km, proved exactly minimal
2006: 85,900 cities — the current world record for 2D Euclidean TSP, requiring over 136 CPU-years

That last number is arresting: 136 CPU-years. Modern computers, running for longer than a human career, to prove that one particular arrangement of 85,900 cities is the shortest possible closed loop through all of them. The Concorde team has solved all 110 standard benchmark instances from the TSPLIB problem library to proven optimality.

Why Crossing Paths Are Never Optimal

Here's one of TSP's beautiful geometric insights: in Euclidean space, the optimal tour never crosses itself.

The proof is elegant. Suppose your tour has two edges that cross — say, city A to city B, and city C to city D, where these line segments intersect. You can "uncross" them by re-routing: go from A to C, then from B to D. By the triangle inequality, the uncrossed version is strictly shorter. Therefore, any tour with crossings can be improved — so the optimal tour has none.

The optimal Euclidean tour is topologically a simple closed curve: it traces a loop with no self-intersections. You can use this visually: whenever you see a route that doubles back with crossing edges, you know immediately it's not optimal. It's a rare case where a deep mathematical fact translates into an immediately visible geometric rule of thumb.

The Art of Approximation

For practical purposes, the theoretical hardness rarely bites. The Lin-Kernighan heuristic (a sophisticated local-search algorithm) routinely finds solutions within 1% of optimal for instances with millions of cities. The basic idea — "2-opt" improvement — is to start with any route, then repeatedly swap pairs of edges to shorten the tour until no swap helps. This converges quickly and produces visually clean, non-crossing tours.

The gap between theory and practice is one of TSP's most fascinating aspects. The theoretical worst case is uncomputable in human lifetimes. The practical average case is handled by a laptop in seconds, reliably finding near-perfect solutions.

TSP has even inspired art. Mathematician Robert Bosch at Oberlin College creates stippled portraits by solving TSP instances — the optimal tour through thousands of carefully placed dots traces out recognizable human faces in a single unbroken line. Mathematics and portraiture, unified by the hardest easy problem.

Takeaways

TSP asks for the shortest closed route through a set of cities — trivial to state, catastrophically hard to solve exactly as cities scale.
Brute-force fails fast: 30 cities have more possible routes than atoms in the observable universe; even 20 cities require 60 billion checks.
TSP is NP-hard: a polynomial-time exact solution would simultaneously solve hundreds of other major problems and prove P = NP — worth a $1,000,000 Millennium Prize.
The Christofides–Serdyukov algorithm (1976) guarantees solutions within 3/2 of optimal; this bound stood unimproved for 44 years until a 2021 result breached it by a theoretically profound but practically negligible margin.
In practice, TSP is nearly tamed: heuristics routinely find near-optimal tours for millions of cities, powering logistics systems, circuit board manufacturing, DNA sequencing, and telescope scheduling worldwide.