The Traveling Salesman Problem

Abstract

Given a list of cities and the distances between them, find the shortest round trip that visits each city once. The traveling salesman problem (TSP) was described by a working salesman in 1832, posed to mathematicians in Vienna in 1930, and solved for 49 American cities by three RAND mathematicians in 1954, working largely by hand. In 1972 it was proved NP-hard, which means no one expects a fast general method. Solvers kept getting bigger anyway: an optimal tour through 85,900 points was proved in 2006, and one through 81,998 bars in South Korea in 2025. The cutting-plane method invented for the 49-city tour is the basis of modern integer-programming solvers.

The optimal tour through 15,112 German towns, proved in 2001 with Concorde. Image: Prof. William Cook, public domain, via Wikimedia Commons.

A Salesman’s Handbook

The earliest clear statement of the problem comes from the people who had it. In 1832 a German handbook for commercial travelers, Der Handlungsreisende, von einem alten Commis-Voyageur (“by an old commercial traveler”), gave advice on planning trips and printed sample routes through Germany and Switzerland. Its author put the objective in one sentence: “The main thing to remember is always to visit as many localities as possible without having to touch them twice.” The book contained no mathematics. Planning was done with maps, and later, in sales offices, with pins and string.

Mathematicians had studied round trips earlier without the distances. Leonhard Euler analysed the knight’s tour of a chessboard, and in 1857 William Rowan Hamilton invented the Icosian game, a puzzle in which the player finds a closed path along the edges of a dodecahedron through all twenty corners. A path of that kind is still called a Hamiltonian cycle. Finding one is a question of existence; the salesman needs the shortest.

Vienna, Princeton, RAND

On 5 February 1930, at a mathematics colloquium in Vienna, Karl Menger announced what he called the messenger problem, “because this question is faced in practice by every postman, and, by the way, also by many travelers”: given a finite number of points with known pairwise distances, find the shortest path connecting them. He noted that the obvious rule, always going to the nearest unvisited point, does not in general give the shortest route.

The problem reached American mathematicians by a less documented route. Merrill Flood and A. W. Tucker both recalled hearing it in a seminar talk by Hassler Whitney at Princeton in 1934 (Whitney, asked decades later, did not remember), and Flood had worked on near-optimal school-bus routes as early as 1937. In the 1940s Flood did much to spread the problem among colleagues. The earliest known use of the name in print is a 1949 RAND report by Julia Robinson, “On the Hamiltonian game (a traveling salesman problem)”.

Forty-Nine Cities by Hand

The test case circulating at RAND was a tour through one city in each of the 48 states (Alaska and Hawaii were not yet states) plus Washington, D.C., with road distances from a Rand McNally atlas. In 1954 George Dantzig, Ray Fulkerson, and Selmer Johnson published the solution in Operations Research.

Their method was new. They wrote the tour as a linear program, one variable per road between two cities, and solved the relaxation with the simplex method. The answer was usually not a tour: it contained fractional roads, or several small loops instead of one big one. Each time, they found a linear inequality that every real tour satisfies and the current fractional answer violates, added it to the program, and solved again. When the answer became a single tour, the linear program itself proved that no shorter tour existed. The inequalities are now called cutting planes.

They also cut the work down. Seven cities on the east coast, from Baltimore to Providence, lie on the shortest road between Washington and Boston, so they removed those seven, solved the remaining 42-city problem, and found that the optimal tour used the Washington to Boston edge; putting the seven cities back along that edge gave the 49-city optimum. Newsweek reported that “it took only a few weeks for the California experts to calculate ‘by hand’ the shortest route to cover the 49 cities: 12,345 miles.” The authors themselves were modest about what they had: “what we shall do is outline a way of approaching the problem that sometimes, at least, enables one to find an optimal path and prove it so.”

Car 54

In spring 1962 Procter & Gamble ran a newspaper contest with a $10,000 first prize. Contestants had to plan the shortest drive for Toody and Muldoon, the policemen of the TV comedy Car 54, Where Are You?, through 33 cities, starting and ending in Chicago. Nobody in 1962 could prove which route was shortest, but several contestants sent in the same one, which later computation confirmed as optimal. Among those tied for first were two mathematicians from the Carnegie Institute of Technology, Robert Karg and Gerald Thompson, who had found it with a trial-and-error heuristic. The tie was broken by a short essay on the virtues of a Procter & Gamble product, and Thompson’s essay on soaps won a grand prize.

Hard, Formally

The same year, Michael Held and Richard Karp at IBM, and independently Richard Bellman, published an exact algorithm by dynamic programming. It takes time proportional to n² · 2ⁿ for n cities, far better than checking all (n−1)!/2 tours, and still exponential.

Pessimism about doing much better had been voiced early. Flood wrote in 1956 that “there may well be no general method for treating the problem”. In 1967 Jack Edmonds, who had defined a “good” algorithm as one that runs in polynomial time, stated: “I conjecture that there is no good algorithm for the traveling salesman problem.” In 1972 Karp proved the Hamiltonian cycle problem NP-complete, and the TSP’s hardness followed at once (see P vs NP and Complexity Theory). A polynomial-time algorithm for the TSP would settle P vs NP.

Theory then turned to approximation. In 1976 Nicos Christofides, and independently Anatoliy Serdyukov in the Soviet Union, gave an algorithm that, whenever distances obey the triangle inequality, returns a tour at most 1.5 times as long as the optimum. For 44 years nobody improved the factor 1.5. In 2020 Anna Karlin, Nathan Klein, and Shayan Oveis Gharan proved that a randomized algorithm achieves 1.5 − ε for some ε greater than 10⁻³⁶. The improvement is too small to matter to anyone routing a truck; its interest is that the barrier fell at all.

Good Enough Tours

Practice mostly ignored the worst case. In 1973 Shen Lin and Brian Kernighan at Bell Labs published a local-search heuristic that repeatedly swaps groups of edges in a tour while the tour gets shorter. Lin-Kernighan, and Keld Helsgaun’s later implementation LKH, routinely find tours within a fraction of a percent of optimal on very large instances. Delivery routing, circuit-board drilling, and genome mapping run on descendants of these methods, usually with extra constraints such as time windows and vehicle capacities.

From 49 to 85,900

The 49-city record stood for seventeen years, until Held and Karp solved 64 random points in 1971. The larger records returned to the RAND idea. Martin Grötschel proved an optimal 120-city tour through Germany in his 1977 doctoral thesis; Manfred Padberg and Giovanni Rinaldi reached 2,392 points in 1987, combining cutting planes with branching, the approach now called branch and cut.

In the 1990s David Applegate, Robert Bixby, Vašek Chvátal, and William Cook wrote Concorde, a TSP solver whose code they made freely available for academic use. It solved 13,509 US cities in 1998 and 15,112 German towns in 2001, the second on a network of 110 processors in computing time equivalent to 22.6 years on one. Sweden’s 24,978 towns followed in 2004. In 2006 the team, now including Helsgaun, Daniel Espinoza, and Marcos Goycoolea, solved an 85,900-point instance from a chip-layout application, using more than 136 CPU-years. It remains the largest instance in the standard TSPLIB benchmark set to be solved.

The records now come from maps. Between December 2024 and March 2025 Cook, Espinoza, Goycoolea, and Helsgaun computed a walking tour through 81,998 bars in South Korea and proved it the shortest possible under the walking times of the OpenStreetMap routing engine OSRM. The round trip takes 178 days, 1 hour, 56 minutes, and 17 seconds.

⚠️ Dead End: The Neural Network Shortcut

In 1985 John Hopfield and David Tank published “‘Neural’ computation of decisions in optimization problems” in Biological Cybernetics. They encoded a tour as the stable state of an analog network of artificial neurons, one neuron for each pair of city and position in the tour, with connection weights that penalized invalid tours and long ones. Simulations on 10 and 30 cities produced good tours, and because the network could be built as an analog circuit, the idea promised dedicated hardware for optimization. The paper was widely cited.

It did not survive replication. In 1988 G. V. Wilson and G. S. Pawley reran the method, tried to scale it to useful sizes, and reported: “Our simulations indicate that Hopfield and Tank were very fortunate in the limited number of TSP simulations they attempted.” Many runs did not produce a valid tour at all. A NASA Ames study the same year found that with corrected parameters the network gave a valid tour in 78 percent of 10-city trials and 72 percent of 15-city trials, and that the valid tours were often no better than the nearest-city rule that Menger had dismissed in 1930. Nobody found a way to scale the method, and conventional heuristics were already better.

The idea returned with deep learning after 2015, as networks trained to output tours. A systematic comparison published in 2022 concluded that “the solvers learned by NCO approaches, in general, still fall short of traditional solvers in nearly all these aspects,” with an advantage only on small instances similar to their training data. The problem that defeated the analog networks of 1985 is still solved best by the linear programs of 1954 and the edge swaps of 1973.