Travelling salesman problem
A classic NP-hard problem in combinatorial optimization.
The travelling salesman problem (TSP) is a foundational problem in combinatorial optimization and theoretical computer science. It asks for the shortest possible route that visits each city exactly once and returns to the origin city, given a list of cities and distances between each pair. The problem is NP-hard, meaning that no efficient algorithm is known to solve all instances optimally, and it serves as a benchmark for optimization methods.
- field
- Computational complexity, combinatorial optimization, operations research
- known_for
- NP-hard problem; decision version is NP-complete; benchmark for optimization methods; applications in logistics, microchip manufacturing, DNA sequencing, astronomy
Lore & Background
The origins of the travelling salesman problem are unclear. The TSP was mathematically formulated in the 19th century by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman. Hamilton's icosian game was a recreational puzzle based on finding a Hamiltonian cycle. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger, who defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic. It was first considered mathematically in the 1930s by Merrill M. Flood, who was looking to solve a school bus routing problem. Hassler Whitney at Princeton University generated interest in the problem, which he called the '48 states problem'.
Reader's Guide
The travelling salesman problem is significant because it is one of the most intensively studied problems in optimization and is used as a benchmark for many optimization methods. Its NP-hardness, implied by Richard M. Despite this difficulty, many heuristics and exact algorithms are known, allowing some instances with tens of thousands of cities to be solved completely, and problems with millions of cities to be approximated within a small fraction of 1%. The problem has applications in planning, logistics, microchip manufacturing, warehouse operations, DNA sequencing, and astronomy. Notable contributions include the cutting plane method developed by George Dantzig, Delbert Ray Fulkerson, and Selmer M. Johnson, who solved a 49-city instance to optimality; the Beardwood–Halton–Hammersley theorem providing an asymptotic formula; the Christofides–Serdyukov algorithm, which yields a solution at most 1.5 times longer than optimal; and the Concorde program developed by Applegate, Bixby, Chvátal, and Cook, used for many record solutions.
Did You Know?
- The decision version of the TSP belongs to the class of NP-complete problems.
- The Christofides–Serdyukov algorithm yields a solution that, in the worst case, is at most 1.5 times longer than the optimal solution.
Frequently Asked Questions
What is the Travelling Salesman Problem?
TSP is a staple puzzle in combinatorial optimization: given a set of cities and pairwise distances, find the shortest closed loop that visits every city exactly once and returns to the start. It lives at the intersection of theoretical computer science, operations research, and applied mathematics.
What are TSP's 'powers' or role in complexity theory?
Its defining trait is NP-hardness—no algorithm is known that guarantees the optimal tour for every input in polynomial time. That difficulty has made it the de facto yardstick against which researchers benchmark new heuristics, metaheuristics, and approximation schemes.
How does TSP's 'story' end?
It doesn't, at least not yet: a general polynomial-time solver remains undiscovered, and most theorists suspect one cannot exist unless P equals NP. So the ongoing narrative is one of ever-improving approximations, branch-and-bound tricks, and clever heuristics rather than a single closed-form answer.
Why is TSP important beyond pure theory?
The same routing logic underpins real-world logistics and delivery planning, the path a laser drill takes when etching a microchip, the ordering of fragments in DNA sequencing, and the scheduling of telescope observation windows. Its sheer ubiquity across industries is why it became a canonical test case for optimization research.
What is TSP's connection to NP-complete problems?
The decision version—'does a tour of length at most L exist?'—is NP-complete, placing it among the hardest problems verifiable in polynomial time. A breakthrough on that decision variant would therefore cascade into solutions for a vast family of related combinatorial questions.
More in Complexity Theory 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record