Probabilistic exchange algorithm and Euclidean traveling: Salesman problems

Many hard combinatorial optimization problems can be approached by what has become known as simulated annealig, i.e. probabilistic exchange algorithms that yield good approximations and under certain conditions converge almost surely to the optimum. In this paper, the role of Gibbs distribution in this context is studied, convergence conditions are reviewed and some new results shown. In the second part, results of extensive empirical studies of the method on various Euclidean traveling salesman problems are given. In particular, several neighborhood structures and annealig schedules are compared an important experimental result being the apparent orthogonaly of these two features. Finally the method is compared with other heuristics and it is shown to be competitive, if not superior to the others.