The idea: build a tour fast, then improve it
The Travelling Salesman Problem (TSP) asks for the shortest closed tour that visits every city once and returns to the start. With n cities there are (n−1)!/2 different tours: 12 cities already give almost 20 million. The best exact method that works on any input, Held–Karp dynamic programming, takes O(n²·2ⁿ) time, so for real problems people use heuristics: build a reasonable tour quickly (a construction heuristic), then change it bit by bit while it gets shorter (an improvement heuristic, a kind of local search).
The page uses the classic pair: nearest neighbour to build, 2-opt to improve. Map 1 has 12 cities A–L on a 100 × 100 grid; distances are straight lines. Held–Karp gives the true optimum, 286.5, drawn as the green line on the chart, so you can see how far each tour is from it.
Nearest neighbour
Start at a city. Again and again, go to the closest city not visited yet. When none are left, go back to the start. Each step looks at the remaining cities once, so the whole tour takes O(n²) time. The page shows each choice in two steps: the orange candidate edge with its length, then the edge joining the tour.
The trouble is the end. The early choices are cheap, but they leave scattered cities behind, and the last edges, including the forced edge home, can be long and cross earlier ones. (Demo 1: nearest-neighbour tour from G: G, K, C, D, B, J, E, L, F, A, H, I, then the edge I–G of 75.3 back home. Length 341.6, 19.3% above the optimum, with 3 pairs of crossing edges.)
2-opt: swap two edges
A 2-opt move takes two edges of the tour, a–b and c–d, removes them, and reconnects the two pieces as a–c and b–d. That is the only other way to close the tour, and it reverses the path from b to c. The move shortens the tour by the gain
gain = d(a,b) + d(c,d) − d(a,c) − d(b,d)
and is worth taking when the gain is above 0. The page uses best improvement: it checks all n(n−3)/2 = 54 pairs of non-adjacent edges and applies the one with the largest gain, then repeats. It stops when no pair has a positive gain. That tour is a 2-opt local optimum.
tour = nearest_neighbour(start)
loop:
best = the pair (a–b, c–d) with the largest gain
if gain(best) <= 0: return tour # 2-opt local optimum
reverse the path b … c # a–b, c–d become a–c, b–d
The first move from the G tour removes C–D (19.7) and I–G (75.3), adds C–I (60.1) and D–G (15.3), and saves 19.6. Five moves later the tour is 286.5, the optimum, and the chart shows every drop: 341.6, 322.0, 308.2, 297.1, 290.1, 286.5 (Demo 2: 2-opt untangles the crossings).
| Heuristic | What one step does | Time |
|---|---|---|
| Nearest neighbour | adds the closest unvisited city | O(n²) for the tour |
| 2-opt step | checks every pair of edges, applies the best swap | O(n²) per move |
| Held–Karp (exact) | best path for every subset of cities and end city | O(n²·2ⁿ) |
Why crossings always go
If two edges a–b and c–d cross at a point X, the triangle inequality gives d(a,c) < d(a,X) + d(X,c) and d(b,d) < d(b,X) + d(X,d). The four parts add up to d(a,b) + d(c,d), so the uncrossed pair is shorter and the 2-opt move has a positive gain. A 2-opt local optimum therefore never has crossing edges, and the stats panel always reads 0 crossings at the end.
The reverse is not true. A tour with no crossings can still be improved: nearest neighbour from F gives 297.1 with 0 crossings, and 2-opt still finds two moves down to 286.5 (Demo 3: start at F: no crossings, still too long).
A local optimum is not the optimum
From A, nearest neighbour gives 313.7. One 2-opt move brings it to 302.6, and then no pair of edges helps: 2-opt stops 5.6% above the optimum (Demo 4: start at A: 2-opt stops above the optimum). A random tour of 602.9 needs 10 moves and ends on the same 302.6 tour (Demo 5: 2-opt from a random tour).
The optimal tour (Demo 6: the optimal tour (Held–Karp)) differs in three edges, so it is one 3-opt move away (here an Or-opt move: take one city out and put it in elsewhere), but more than one 2-opt move away, and each single 2-opt move on the way would first make the tour longer.
On map 1, nearest neighbour plus 2-opt reaches the optimum from 10 of the 12 start cities (A and I end on 302.6). Map 2 is harder: 7 of 12 starts reach its optimum of 280.3. That suggests the usual fix: run the heuristic from many starts, or from many random tours, and keep the best result.
How good are these heuristics?
On large random city sets, nearest-neighbour tours are typically about 25% longer than the optimum, and 2-opt brings that down to about 5%. 3-opt reaches about 3%, and the Lin–Kernighan heuristic, which chains variable-depth moves, about 2%. Nearest neighbour has no fixed guarantee: there are inputs where it is a factor of order log n worse than optimal. 2-opt can also take very many moves on bad inputs, though on real data it settles quickly when it starts from a good tour, as here: 5 moves from the G tour against 10 from a random one.
See also Simulated Annealing (local search that sometimes accepts a worse move, the usual way to escape a 2-opt local optimum), Genetic Algorithm (a population of solutions instead of one tour), Prim's algorithm (the minimum spanning tree behind the 2-approximation for metric TSP), and Convex Hull (in an optimal tour the hull cities appear in hull order, the idea behind hull-insertion construction).
What the page leaves out
Other construction heuristics (cheapest and farthest insertion, the greedy edge heuristic, space-filling curves), approximation algorithms with guarantees (the MST double-tree 2-approximation and Christofides' 1.5-approximation), first-improvement 2-opt, neighbour lists and don't-look bits that make 2-opt fast on 100 000 cities, 3-opt, Or-opt and Lin–Kernighan, and exact solvers such as Concorde (branch and cut with linear programming), which solve instances with tens of thousands of cities. Real road networks are also not straight-line distances, and may be asymmetric (one-way streets).