Simulated Annealing for the TSP

The traveling salesman problem (TSP) asks for the shortest closed route visiting each of $N$ cities exactly once. A route is a Hamiltonian cycle $\sigma$, i.e. a cyclic ordering of the cities, and its cost is the total length

$$ C(\sigma) = \sum_{i=1}^{N} d\left(\sigma_i, \sigma_{i+1}\right), \qquad \sigma_{N+1} \equiv \sigma_1. $$

There are $(N-1)!/2$ distinct cycles, and the problem is NP-hard: no known algorithm finds the optimum in polynomial time. Simulated annealing is a heuristic borrowed from statistical physics [1, 2]. It treats the cost as an energy $H = C$ and samples cycles from the Gibbs measure $\pi_T(\sigma) \propto e^{-C(\sigma)/T}$ at a slowly decreasing temperature $T$, the way a slowly cooled metal settles into a low-energy crystal.

Metropolis sampling

Sampling uses a Markov chain. At each iteration a move proposes a neighboring cycle $\sigma^{\prime}$, and the Metropolis prescription [3] accepts it with probability

$$ A(\sigma \to \sigma^{\prime}) = \min\left(1,\; e^{-\left(C(\sigma^{\prime}) - C(\sigma)\right)/T}\right). $$

Downhill moves are always taken. Uphill moves are taken with a probability that shrinks with $T$, which lets the chain climb out of local minima while $T$ is still high, unlike a greedy local search.

Geometric cooling

The annealing loop samples $n_{\text{iter}}$ iterations at each temperature and then cools:

$$ T_{t+1} = \alpha\, T_t \quad\Longrightarrow\quad T_t = \alpha^t\, T_0, \qquad \alpha \in (0, 1), $$

until the final temperature $T_f$ is reached after $n_{\text{steps}} = 1 + \log(T_f/T_0)/\log\alpha$ steps, for a total of $n_{\text{steps}} \times n_{\text{iter}}$ iterations. Logarithmic schedules $T_t \propto 1/\log(t+1)$ provably reach the global minimum, but only in infinite time [4]. The geometric schedule has no such guarantee, yet in practice it gives very good cycles in reasonable time [5].

Moves

Both moves replace two edges of the cycle, so the cost difference $\Delta C$ of a candidate costs $O(1)$ to compute and no cycle ever has to be summed from scratch. Writing $h$ and $k$ for the cities just before and just after the affected stretch $i \dots j$,

$$ \Delta C = d(h, j) + d(i, k) - d(h, i) - d(j, k). $$

• Swap exchanges two cities adjacent in the cycle ($j = i + 1$). The moves are tiny, so many of them are needed to change the cycle’s shape.
• 2-opt [6] reverses the whole stretch between $i$ and $j$: it cuts two edges and reconnects the two resulting paths the other way around. One move can undo a crossing of two edges of any length, which is why 2-opt reaches far cheaper cycles than swap, and the gap grows with $N$.

Domains

Cities are drawn at random from one of the following two-dimensional domains:

• Uniform: uniform in the unit square $[0, 1]^2$.
• Correlated: coordinates with correlation $\rho$ [7, 8], mixed from two independent variables $z_1, z_2$ (uniform on $[-\tfrac12, \tfrac12]$ or normal with the same variance $\tfrac{1}{12}$):

$$ x = z_1 \sin\varphi + z_2 \cos\varphi, \qquad y = z_1 \cos\varphi + z_2 \sin\varphi, \qquad \varphi = \tfrac12 \arcsin\rho. $$

The mixing keeps the mean and variance of each coordinate, so $\rho$ is the only thing that changes. At $\rho \to 1$ the cities collapse onto the diagonal and the TSP turns into sorting points on a line, which is easy. Tuning $\rho$ moves the instance from a hard problem to one in P.

• Power law: each coordinate independently drawn from the two-tailed power law

$$ p(x) = \frac{\gamma - 1}{2 x_0^{1-\gamma}} \, |x|^{-\gamma}, \qquad |x| \geq x_0, $$

with $x_0 = 0.1$ fixed here. For $\gamma \leq 3$ the variance is infinite and a few far outliers dominate the picture. The bulk of the cities then gets squeezed into the middle of the view, which is an honest rendering of the domain rather than a glitch. Note also that $T$ has units of distance: a power-law domain has a different scale than the unit square, so the same $T$ means something different on it.

Performance

The measure of performance is the ratio $C/\langle C_0\rangle$ between the cost reached and the expected cost of a uniformly random cycle on the same cities, which is $N$ times the mean distance between two cities:

$$ \langle C_0 \rangle = \frac{2}{N - 1} \sum_{i < j} d(i, j). $$

For the unit square this is known in closed form, $\langle C_0\rangle = \frac{N}{15}\left(2 + \sqrt2 + 5\ln(1 + \sqrt2)\right) \approx 0.52\\,N$. The shortest cycle only grows like $\sqrt N$, so good final ratios shrink as $N$ grows.

This is a live version of the simulations in my M.Sc. dissertation [8], whose research code is at eliseuv/tsp-sa. Every control acts on the running simulation. The schedule runs on its own, but you can grab the current $T$ at any time to reheat or quench the cycle, or hold it fixed to watch the chain at equilibrium.