Probabilistic exchange algorithms and Euclidean traveling salesman problems (Q1079126)

The authors introduce the reader to methods of simulated annealing, i.e. probabilistic exchange algorithms that yield good approximations and - sometimes - converge almost surely to the optimum. The embedding of the configuration space of the problem into an irreducible, aperiodic Markov chain is demonstrated in detail and some alternatives of annealing schedules (sequences of external parameters which govern the convergence process) are analysed. To solve the Euclidean traveling salesman problem, different but very obvious neighborhoods (of a permutation \(\sigma)\) are introduced and analysed, a simple transition matrix is deduced and some annealing schedules are tested. The experimental results are very encouraging, the lack of theoretical insight is in general obvious.