The Traveling Salesman Problem: Optimization's Most Famous Puzzle

Just 20 Cities Generate 60 Quadrillion Possible Routes

The Traveling Salesman Problem (TSP) asks: given a list of cities and the distances between every pair, what is the shortest possible route that visits each city exactly once and returns to the starting point? With 10 cities, there are approximately 181,000 possible routes. With 20 cities, that number exceeds 60 quadrillion. With 50 cities, the number of possible routes exceeds the estimated number of atoms in the observable universe. No algorithm is known that can guarantee the optimal solution without, in the worst case, examining an exponential number of possibilities. The TSP is not merely an abstract puzzle — it is the organizing problem of combinatorial optimization with direct applications to logistics, manufacturing, genome sequencing, and circuit board drilling.

Formal Definition

The Traveling Salesman Problem exists in two variants:

The TSP is an NP-hard problem — it is at least as hard as any problem in the NP complexity class. No polynomial-time algorithm is known, and the P vs. NP problem (whether such algorithms must exist) remains unsolved. The TSP is also NP-complete in its decision form: "Is there a tour of length ≤ k?" — answering yes-or-no questions about tours is itself intractable in general.

Exact Algorithms: When They're Feasible

For small instances (roughly up to 15–20 cities), exact algorithms can find the optimal solution in reasonable time.

• Brute force: Enumerate all (n−1)!/2 possible tours. Optimal but runtime is O(n!). Infeasible above ~15 cities.
• Held-Karp Dynamic Programming Algorithm (1962): Reduces complexity to O(2ⁿ × n²). Proposed independently by Held and Karp in 1962, it solves instances up to ~30 cities practically. Still exponential, but far better than brute force.
• Branch and Bound: Explores the solution space systematically, pruning branches that cannot improve on the best solution found so far. State-of-the-art solvers like Concorde TSP Solver use this approach with sophisticated lower bounds.

The Concorde TSP Solver, developed at Georgia Tech and Princeton by Applegate, Bixby, Chvátal, and Cook, solved a 85,900-city instance (a tour visiting every city in the US with population over a certain threshold) in 2006. This remains one of the largest TSP instances solved to provable optimality.

Approximation Algorithms: Close Enough, Fast

For large instances where exact solutions are impractical, approximation algorithms guarantee solutions within a known factor of the optimal.

In 2020, Anna Karlin, Nathan Klein, and Shayan Oveis Gharan published a breakthrough at the University of Washington: an algorithm achieving a 3/2 − ε approximation guarantee — slightly better than Christofides for metric TSP. This was the first theoretical improvement over Christofides in 44 years, though the improvement is a tiny ε that has no practical significance for computation.

Real-World Applications

The TSP is embedded in problems across many domains that do not obviously resemble a salesman's route.

• Logistics: UPS's ORION routing software, deployed in 2012, optimizes delivery routes using TSP-related algorithms. The company estimated it saves 100 million miles of driving per year, reducing fuel costs by roughly $300–$400 million annually.
• Circuit board manufacturing: CNC drilling machines must drill thousands of holes in a printed circuit board. The order in which holes are drilled is a TSP instance — minimizing the drill's total travel distance reduces manufacturing time directly.
• Genome sequencing: Reconstructing a DNA sequence from overlapping fragments involves ordering the fragments to minimize inconsistencies — a problem with the same mathematical structure as TSP.
• Telescope scheduling: Space telescopes must observe targets in an efficient sequence. The slew time between observations follows TSP dynamics.

The TSP and the P vs. NP Problem

If P = NP (if every problem whose solution can be verified quickly can also be solved quickly), then TSP would have a polynomial-time exact algorithm. The Clay Mathematics Institute has offered $1 million for a proof or disproof. Most computer scientists believe P ≠ NP — that TSP and other NP-hard problems have no polynomial-time solution — but this has never been proved. The TSP thus sits at the intersection of a practical engineering problem and one of the deepest open questions in mathematics.