About Travelling Salesman
A salesman has to visit every town on the map once and get back home. Which order makes the shortest round trip? This app puts the classic ways of answering that side by side on one road map. Each method lays its own coloured thread, and the journey log beside the map enters its mileage and how far it is above the best route known.
Click the map to add a town (up to 100), drag a pin to move it (every route is worked out again as you drag) and click a pin to take it away. The buttons above the map lay out random towns, a circle, a grid or clusters; pressing a random one again gives a new map. Pick a method in the log to see its route, and WATCH IT WORK plays it step by step. YOUR ROUTE lets you try it yourself: click the towns in the order you'd drive them. COPY LINK copies a link to this exact map.
THE STORY
The problem is older than the mathematics. A German handbook for travelling salesmen, published in 1832, gave example tours through Germany and Switzerland and advised covering as many places as possible without visiting any twice, but had no method for finding the best one. In the 1850s William Rowan Hamilton's Icosian game asked for a round trip along the edges of a dodecahedron that visits every corner once; such a loop is still called a Hamiltonian cycle.
Karl Menger raised the "messenger problem" at a mathematics colloquium in Vienna in 1930, and pointed out that always going to the nearest point next does not in general give the shortest route. The name "travelling salesman problem" was going round Princeton in the 1930s; its first known appearance in print is a 1949 RAND report by Julia Robinson. In 1954 George Dantzig, Ray Fulkerson and Selmer Johnson proved the shortest tour through 49 cities in the United States (one in each of the 48 states and Washington, DC), using linear programming. G. A. Croes described the leg-swapping improvement now called 2-opt in 1958, and in 1962 Michael Held and Richard Karp, and separately Richard Bellman, published the dynamic programming method this app uses for the shortest route.
In 1972 Karp listed 21 problems as NP-complete, among them finding a Hamiltonian cycle, a close cousin of this one. Nobody knows a method that is fast on every map, and whether one exists is the P versus NP question, one of the seven Millennium Prize Problems with a million dollars on offer. Even so, very large maps have been solved exactly: in 2006 the team behind the Concorde program proved the shortest tour through 85,900 points of a computer chip layout.
HOW IT WORKS
Distances are straight lines, as the crow flies. The map is 500 by 350 miles.
Nearest neighbour starts at town A (the gold pin) and always drives to the closest town it hasn't been to yet, then goes home. Greedy edge looks at every possible leg, shortest first, and keeps one unless it would give a town three legs or close a loop before every town is in. 2-opt starts from the nearest-neighbour route, finds the pair of legs whose swap saves the most (cut both, join the ends the other way round, which reverses the stretch between them) and repeats until no swap helps. Any two legs that cross can always be swapped to something shorter, so a 2-opt route never crosses itself, and neither does the shortest. The map rings any crossings.
Shortest, up to 18 towns, is Held and Karp's method: for every set of towns and every town to finish at, the shortest path from A through exactly that set, built up from small sets to large ones. It is guaranteed to be shortest, but the work roughly doubles with each extra town, so above 18 towns the log shows the best found instead: many improved routes (2-opt, plus Or-opt, which moves runs of one to three towns elsewhere), each shaken up by cutting it in four and reconnecting it, then improved again, keeping the best. It's usually the shortest or very close, but it isn't proven. "Above best" compares each route with the best one known for the map. With 10 towns or fewer, watching the shortest tries every route in turn (181,440 of them at 10).
How many routes? Starting from A there are n − 1 choices for the first town, then n − 2, and so on: (n − 1)! orders. Each loop is counted twice (once each way round), so there are (n − 1)! ÷ 2 different round trips. That number grows so fast that checking them all stops being possible somewhere in the twenties.
FURTHER WATCHING AND READING