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.
WOS:A1986D926500003
1986
8
151
164
PRO 86.03
REVIEWED