- Tour
- Shortest found
- Start
| Method | Length | Above shortest | Steps |
|---|---|---|---|
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - |
Traveling salesman problem
A salesman has to visit every city once and return home. Which order makes the trip shortest? The question is easy to ask and, as the number of cities grows, hopeless to answer by trying every order: 30 cities already allow about 4.4 × 10³⁰ round trips. Scatter cities on a map or click your own, then watch quick rules of thumb, clever improvements and one exact method build their tours step by step, and see how close the fast ones get. Choose how the cities are laid out and how many there are, pick a method and press Solve to watch it build a round trip step by step, or Step to go one move at a time. Click the map to add a city, or click a city to remove it. Compare all runs every method on the same cities and shows how far each one is from the shortest tour found. The red city is where the trip starts.
How it works
- Choose a layout and the number of cities, or click the map to place your own and click a city to remove it.
- Pick a method and press Solve to watch it step by step, or Step to go one move at a time.
- Press Compare all to run every method on the same cities and read how far each tour is above the shortest one found.
Why it is hard
With n cities there are (n − 1)! / 2 different round trips, because it does not matter where you start or which way round you go. That is 12 for 5 cities, 181,440 for 10 and about 6 × 10¹⁶ for 20. No method is known that finds the shortest trip for every map in a time that grows only like a power of n; the problem is NP-hard. The best exact method in this app, Held–Karp dynamic programming from 1962, still needs about n² · 2ⁿ steps, so it is limited to 12 cities here.
Good tours fast
In practice, nearly shortest tours are found quickly. Nearest neighbour always drives to the closest unvisited city and typically ends about 25% above the best tour. Cheapest insertion grows a loop and adds whichever city stretches it least. 2-opt takes any tour and keeps replacing two edges with two shorter ones, which removes every crossing and usually gets within about 5%. Simulated annealing makes random 2-opt moves and, while it is still "hot", accepts some that make the tour longer, so it can climb out of dead ends before it settles.
Frequently asked questions
Is there a formula for the shortest route?
No. The shortest tour depends on the exact positions of all the cities, and no known method finds it for every map without, in the worst case, an amount of work that grows exponentially. For a few hundred or thousand cities, specialised exact solvers such as Concorde still prove optimal tours by combining linear programming with clever pruning, and the largest instance solved exactly so far has 85,900 points.
Why does 2-opt remove every crossing?
If two edges of a tour cross, the four cities they join form a quadrilateral whose diagonals are the two edges. Swapping them for two opposite sides of the quadrilateral is always shorter, by the triangle inequality, and reverses the stretch of tour in between. 2-opt keeps making such swaps until none helps, so its final tour never crosses itself.
What is the temperature in simulated annealing?
It controls how willing the method is to accept a move that makes the tour longer. A move that adds d to the length is accepted with probability e^(−d/T). At a high temperature T almost anything goes, which lets the tour escape a poor arrangement; as T falls the method becomes greedy and settles. The name comes from cooling metal slowly so its atoms find a low-energy arrangement.
Why is the exact method limited to 12 cities?
Held–Karp stores the shortest path for every subset of cities and every possible last city, which is about n · 2ⁿ numbers, and fills each in with n comparisons. For 12 cities that is a few hundred thousand steps; for 25 cities it would be billions. It is still enormously faster than trying all (n − 1)! / 2 tours: for 12 cities that would be almost 20 million.
Is anything sent to a server?
No. The cities and all five methods run in your browser. The cities you click in stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor