Sketch · 2026-07-06
Simulated annealing, on the salesman.
Forty cities scattered in a square. Draw one closed tour that visits each city and returns to the start, and pick the shortest. That is the traveling salesman problem. The exact best route among 40 cities is one of 39!/2 tours, which is about 1046.
The move
Two-opt is the classical local step for TSP. Pick two edges of the current tour, then reconnect the loose ends the only other way. The tour splits into two arcs; one arc gets reversed and the join points swap partners.
The change in tour length is the sum of the two new edge lengths minus the two old ones. Every other edge stays fixed, so evaluating a candidate swap is constant time. Millions per second is easy for forty cities.
The rule
Every iteration picks a random two-opt swap. If the swap shortens the tour, accept it. If it lengthens the tour by Δ, accept it with probability exp(−Δ/T), where T is a temperature that falls over time. This is the Metropolis criterion, borrowed from statistical mechanics.
At high T almost every candidate gets through. The tour rambles and gets worse as often as it gets better. It drifts out of any local basin it happens to fall into. As T drops, the probability of accepting a bad swap collapses. Eventually only strict improvements survive and the tour freezes.
The schedule
Cities sit in the unit square [0,1] × [0,1], so a typical edge has length around 0.1 to 0.4. T starts at 0.3, hot enough that a bad swap of size 0.1 accepts with probability exp(−0.33) ≈ 0.72. Each iteration multiplies T by 0.99995.
After twenty thousand iterations T sits around 0.11. By fifty thousand it is close to 0.025, and by a hundred thousand it is near zero. The Reheat button jumps T back to 0.15 to kick the tour out of whatever local minimum it settled into.
What to watch
The current tour is drawn in amber; the best-so-far is drawn underneath in muted grey. Early on the two are the same and get better together. Once T drops enough, the current tour sometimes wanders off worse than the best, and the grey shows what the run is comparing against.
An optimal tour on random uniform cities in the unit square has length near 0.7124√N, an asymptotic result from Beardwood, Halton and Hammersley in 1959. For N = 40 that gives about 4.51 as a rough target for well-behaved instances.
Sources
Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P., Optimization by Simulated Annealing, Science 220 (1983), 671-680. Lin, S., Computer Solutions of the Traveling Salesman Problem, Bell System Technical Journal 44 (1965), 2245-2269. Beardwood, J., Halton, J.H. and Hammersley, J.M., The Shortest Path Through Many Points, Mathematical Proceedings of the Cambridge Philosophical Society 55 (1959), 299-327.