Traveling Salesperson Lab

Watch nearest neighbour, greedy edge, 2-opt, Or-opt, simulated annealing and the exact Held-Karp solver on a map you can edit.

Switch to 3D

Presets

Playback

Map

Number of cities and map seed. Click the map to add, shift-click to remove, drag to move.

Run settings

Speed of the animation and the annealing schedule.

Layers

Model checks

The science

The problem

Given N cities, find the shortest closed route that visits each exactly once. There are (N-1)!/2 distinct tours (10^155 for 100 cities), and no known algorithm solves every instance in polynomial time: the decision version is NP-complete.

Heuristics shown

Nearest neighbour always walks to the closest unvisited city (typically 20-25 % above optimal). Greedy edge adds the shortest remaining edge that keeps every city at degree two and creates no early cycle (about 14-20 % above). 2-opt repeatedly removes two edges and reconnects the tour the other way when that is shorter; it ends in a local optimum where no such move helps (about 5 % above). Or-opt moves segments of one to three cities. Simulated annealing accepts a worsening 2-opt move with probability exp(-dL / T) while the temperature T falls geometrically, which lets it escape local optima.

Exact solution and bounds

The Held-Karp dynamic programme computes the optimum in O(N^2 2^N) time by building the best path over every subset of cities ending in each city; it is practical here up to N = 13. A lower bound comes from the 1-tree: the minimum spanning tree of all cities except one, plus that city's two shortest edges. Any tour contains such a structure, so 1-tree <= optimum. Doubling the minimum spanning tree gives the classic upper bound optimum <= 2 MST (a 2-approximation).

Random maps

For N uniform random points in a unit square the optimal tour length approaches 0.7124 sqrt(N A) (Beardwood-Halton-Hammersley), with A the area. The page uses that scale only as an intuition; small maps deviate noticeably from the limit.

Honest simplifications

Euclidean distances on a flat map, symmetric costs, all cities visited, one salesperson. The search steps shown are the algorithm's accepted moves, not CPU time. The 1-tree bound used here tries up to 12 choices of the excluded city and is not the stronger Held-Karp ascent bound used by real solvers such as Concorde.

What to try
  • Run Nearest neighbour, then 2-opt, then Or-opt on the same map and compare the bars in the second graph.
  • "Exact: 11 cities" lets Held-Karp show the true optimum (blue dashed line in graph one); see how far each heuristic is from it.
  • Drag a city or click to add one: every bound and optimum is recomputed.
  • Look at the third graph to see why brute force dies near 15 cities while Held-Karp lasts to about 25.
Tour length versus improvement steps
Final length of each algorithm relative to optimal (or the bound)
Why exact search explodes: brute force vs Held-Karp
Edge-length histogram of the current tour