The traveling salesman problem explained

Give a salesman a list of cities and ask for the shortest trip that visits each of them once and returns home. Anyone can check a proposed route, and anyone can improve a bad one by eye, yet nobody knows a fast method that always finds the best. The traveling salesman problem has become the standard example of a hard problem, and the methods invented to attack it now plan deliveries, drill circuit boards and assemble genomes.

A map of cities joined by a closed tour, with the starting city marked and a faint shorter tour underneath
A map of cities joined by a closed tour, with the starting city marked and a faint shorter tour underneath

The problem

A tour visits every city exactly once and ends where it started; its length is the sum of the distances along the way. The task is to find the shortest tour. In the version here the distances are straight lines on a map, so going from A to C is never longer than going through B: this is the metric traveling salesman problem. The puzzle was discussed by the mathematician Karl Menger around 1930, and the name became common in the following decades, when mathematicians at the RAND Corporation took it up.

Karl Menger in 1970. He discussed the traveling salesman problem around 1930.
Karl Menger in 1970. He discussed the traveling salesman problem around 1930.

The explosion of routes

Fix the starting city. There are n − 1 choices for the next city, n − 2 for the one after, and so on, and every tour can be driven in two directions, so there are (n − 1)! / 2 tours. For 10 cities that is 181,440, easy for a computer. For 20 it is about 6 × 10¹⁶, and for 70 it exceeds the number of atoms in the observable universe. Faster computers do not help much: every extra city multiplies the work by about n.

NP-hard

In 1972 Richard Karp showed that the question of whether a graph has a round trip through every vertex, a Hamiltonian cycle, belongs to a family of NP-complete problems that are all equally hard. The traveling salesman problem contains it, so it is NP-hard. A fast method for it would give fast methods for thousands of other problems in scheduling, logistics and cryptography. Whether such a method exists is the P versus NP question, one of the Millennium Prize Problems.

An exact method: Held–Karp

In 1962 Michael Held and Richard Karp, and independently Richard Bellman, used dynamic programming. For every set S of cities and every city j in S, compute the shortest path that starts at the home city, visits exactly the cities of S and ends at j. Each value follows from the values for S without j, so the table is filled from small sets to large ones, and the shortest tour comes out at the end. It needs about n² · 2ⁿ steps instead of n!, which is the difference between minutes and the age of the universe for 30 cities, but it still grows exponentially.

Richard Bellman in 1962, photographed by Alfred Eisenstaedt. He named dynamic programming in the early 1950s while working at the RAND Corporation.
Richard Bellman in 1962, photographed by Alfred Eisenstaedt. He named dynamic programming in the early 1950s while working at the RAND Corporation.

Quick construction rules

Nearest neighbour always travels to the closest city not yet visited. It is simple and fast, but it tends to strand a few cities that must be collected with long detours at the end, so its tours are typically about 25% longer than the best. Insertion methods instead keep a closed loop and add the remaining cities one at a time where they cost least. In 1976 Nicos Christofides found a construction that is guaranteed to be at most 1.5 times the optimum on any metric map, a bound that stood almost unbeaten for over forty years.

Improving a tour: 2-opt

Local search starts from any tour and keeps making small changes that shorten it. The classic move, 2-opt, removes two edges and reconnects the two pieces the other way, which reverses the stretch between them. Whenever two edges cross, this move uncrosses them and saves length, so a tour that 2-opt cannot improve never crosses itself. On random maps 2-opt tours are typically about 5% above the optimum. Stronger moves that swap three edges, or the variable-depth method of Lin and Kernighan from 1973, get closer still.

Simulated annealing

Local search can get stuck in a tour where every single move makes it worse, even though a much better tour exists. Simulated annealing, applied to this problem by Scott Kirkpatrick, Daniel Gelatt and Mario Vecchi in 1983, borrows from metallurgy: it accepts a worse move with a probability that depends on a temperature, high at first and slowly lowered. Early on the tour wanders freely; at the end only improvements are accepted. With slow enough cooling it reliably finds very good tours.

Explore it

Open the traveling salesman demo to place up to 200 cities at random, on a circle, in clusters, on a grid or wherever you click. Watch nearest neighbour strand its last cities, see 2-opt untangle every crossing, follow the temperature of simulated annealing as it cools, and let Held–Karp prove the shortest tour for up to 12 cities. Compare all runs every method on the same map and shows how far each tour is above the shortest one found.

Frequently asked questions

Where is the traveling salesman problem used?

Wherever something has to visit many places in an efficient order: delivery and collection routes, the path of a drill or laser over a circuit board, the order in which a telescope observes stars, picking orders in a warehouse, and, with different distances, the order of fragments when assembling a DNA sequence.

What is the largest problem ever solved exactly?

In 1954 George Dantzig, Ray Fulkerson and Selmer Johnson proved the shortest tour through 49 cities in the United States. In 2006 the Concorde solver of David Applegate, Robert Bixby, Vašek Chvátal and William Cook proved the optimal tour through 85,900 points from a chip design, after years of computer time.

Is the shortest tour always free of crossings?

Yes, on a flat map with straight-line distances. If two edges crossed, swapping them for two sides of the quadrilateral they form would shorten the tour, so a crossing tour cannot be the shortest.

Do the heuristics give the same tour every time?

Nearest neighbour, cheapest insertion and 2-opt as used here are deterministic: on the same cities they give the same tour. Simulated annealing starts from a random tour and makes random moves, so two runs can end with different tours, usually of almost the same length.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Open the traveling salesman demo