The Traveling Salesman Problem is one of those deceptively simple questions. Give a salesman a list of cities. He needs to visit each one exactly once and return home. What's the shortest route? That's it. Yet despite nearly a century of effort, nobody knows how to solve it efficiently for the general case, and most researchers doubt they ever will.
The Problem
Formally: given N cities with pairwise distances, find the shortest Hamiltonian cycle, a closed path that visits each city exactly once. For a tour $$\pi$$ over cities $$1, 2, \ldots, N$$, the total distance is:
\[L(\pi) = \sum_{i=1}^{N} d\!\left(\pi(i),\; \pi\!\left((i \bmod N) + 1\right)\right)\]The goal is $$\pi^* = \arg\min_\pi L(\pi)$$.
TSP appears in many practical contexts: delivery routing, drilling holes in circuit boards, scheduling telescope observations, even gene sequencing. It's a clean model for any problem where you need to find an efficient ordering over a fixed set of items.
How Hard Is It?
For symmetric TSP (where the distance from A to B equals B to A), there are $$(N-1)!/2$$ distinct tours. For just 20 cities, that's around 60 trillion possibilities.
| Cities (N) | Distinct tours |
|---|---|
| 10 | 181,440 |
| 15 | ~43 billion |
| 20 | ~60 trillion |
| 30 | ~4.4 × 1030 |
| 50 | ~1.5 × 1062 |
TSP is NP-hard. The decision version, "does a tour shorter than K exist?", is NP-complete. A polynomial-time algorithm for TSP would prove P=NP, one of the biggest open problems in mathematics. Most experts consider this unlikely.
The best known exact algorithm is Held-Karp dynamic programming (1962), which runs in $$O(2^N \cdot N^2)$$ time. Exponential, but far better than brute force. It's practical up to roughly 20–25 cities. Beyond that, exact methods become too slow for general instances.
The best practical solvers today, like the Concorde TSP solver, can handle instances with tens of thousands of cities to proven optimality. But they rely on deep problem-specific structure and decades of algorithmic refinement. The general problem is genuinely hard.
Simulated Annealing
Since exact methods don't scale, we turn to heuristics. Simulated annealing is one of the oldest and most intuitive.
The name comes from metallurgy. Heat a metal to high temperature and cool it slowly, and the atoms settle into a low-energy crystal structure. Cool it too fast and you get an amorphous solid: atoms frozen in a locally stable but globally suboptimal arrangement. The slow, controlled cooling allows the system to escape local minima.
The algorithm works as follows:
- Start with a random tour.
- Propose a random modification (a "move").
- If the new tour is shorter, accept it.
- If it's longer by $$\Delta L$$, accept it anyway with probability $$e^{-\Delta L / T}$$.
- Decrease the temperature $$T$$ and repeat.
Step 4 is what sets SA apart from simple hill climbing. At high $$T$$, the acceptance probability $$e^{-\Delta L / T}$$ is close to 1 for moderate $$\Delta L$$, so the algorithm freely accepts worse solutions. This lets it explore broadly and escape local optima. As $$T$$ drops, the probability falls toward zero for worsening moves, and the algorithm gradually commits to the best region it has found.
The 2-opt move
For TSP, a natural neighborhood move is the 2-opt swap: pick two edges in the current tour, remove them, and reconnect the resulting segments in the only other possible way. This is equivalent to reversing the order of cities between the two cut points.
The change in tour length from a 2-opt move only requires four pairwise distances, so it takes O(1) to evaluate. If we remove edges $$(i, i{+}1)$$ and $$(j, j{+}1)$$ and add edges $$(i, j)$$ and $$(i{+}1, j{+}1)$$:
\[\Delta L = d(i,\,j) + d(i{+}1,\,j{+}1) - d(i,\,i{+}1) - d(j,\,j{+}1)\]If $$\Delta L < 0$$, the move improves the tour and is always accepted. Otherwise, we apply the Metropolis criterion from step 4.
The Cooling Schedule
The most common approach is geometric cooling: multiply $$T$$ by a fixed factor $$\alpha \in (0, 1)$$ at each step.
\[T_{k+1} = \alpha \cdot T_k\]With $$\alpha = 0.995$$, the temperature halves every ~138 steps. With $$\alpha = 0.9999$$, it takes ~6,930 steps. Slower cooling gives more exploration at each temperature and generally produces better solutions, but takes longer to converge.
The starting temperature $$T_0$$ matters too. Set it too low and you get greedy descent: only improvements are accepted and the algorithm gets stuck in the first local optimum it finds. Too high and the early iterations are a random walk. A reasonable rule of thumb is to set $$T_0$$ so that a typical worsening move has roughly a 50% acceptance probability at the start.
Try It Yourself
The simulation below runs simulated annealing on a set of randomly placed cities. Hit Run to start and Pause to stop. Reset generates a new layout using the current N. Changes to N and $$T_0$$ take effect on the next reset; $$\alpha$$ and Speed apply immediately.
A few things to try:
- Watch the tour at high temperature: it often gets longer before improving, as the algorithm explores.
- Lower $$\alpha$$ toward 0.990 (faster cooling) and see if the final tour quality suffers.
- Set N to 8–10 and run several times. The algorithm consistently finds near-optimal tours at small scale.
- Raise $$T_0$$ to 5000 and watch how long the tour wanders before settling into a good solution.