Given that any local search method will stop in one of the many local opt solutions, it may be useful to find a way for the iteration to escape by temporarily allowing the tour length to increase. This leads to the popular method of ``simulated annealing'' [Kirkpatrick:83a].
One starts by constructing a sequence of tours 
, 
, and so
on. At each step of this chain, one does a k-change (moves to a
neighboring tour). If this decreases the tour length, the change is
accepted; if the tour length increases, the change is rejected with
some probability, in which case one simply keeps the old tour at that
step. Such a stochastic construction of a sequence of Ts is called a
Markov chain . It can be viewed as a rather
straightforward extension of the above local search to include
``noisiness'' in the search for shorter tours. Because increases in
the tour length are possible, this chain never reaches a fixed point.
For many such Markov chains, it is possible to show that given enough
time, the chain will visit every possible tour T, and that for very
long chains, the Ts appear with a calculable probability
distribution. Such Markov chains are closely inspired by physical
models where the chain construction procedure is called a Monte
Carlo. The stochastic accept/reject part is
supposed to simulate a random fluctuation due to temperature effects,
and the temperature is a parameter which measures the bias towards
short tours. If one wants to get to the globally optimal tour, one has
to move the temperature down towards zero, corresponding to a strong
bias in favor of short tours. Thus, one makes the temperature vary
with time, and the way this is done is called the annealing schedule,
and the result is simulated annealing.
If the temperature is taken to zero too fast, the effect is essentially the same as setting the temperature to zero exactly, and then the chain just traps at a local opt tour forever. There are theoretical results on how slowly the annealing has to be done to be sure that one reaches the globally optimum solution, but in practice the running times are astronomical. Nevertheless, simulated annealing is a standard and widely used approach for many minimization problems. For the TSP, it is significantly slower than Lin-Kernighan, but it has the advantage that one can run for long times and slowly improve the quality of the solutions. See, for instance, the studies Johnson et al. [Johnson:91a] have done. The advantage is due to the improved sampling of the short length tours: Simulated annealing is able to ignore the tours which are not near the minimum length. An intuitive way to think about it is that for a long run, simulated annealing is able to try to improve an already very good tour, one which probably has many links in common with the exact optimum. The standard Lin-Kernighan algorithm, by contrast, continually restarts from scratch, throwing away possibly useful information.