A note on the effect of neighborhood structure in simulated annealing

The simulated annealing method is a neighborhood search algorithm that can be used as a heuristic for many combinatorial problems. Recent research has concentrated on the viability of the approach and the appropriate algorithm parameter settings to use in implementation. In this node the authors consider a problem specific parameter; the neighborhood structure. They motivate the importance of considering the neighborhood by appealing to results on the convergence rate of simulated annealing and previous empirical results. The authors test several neighborhood structures on four different problems: the traveling salesman problem, the quadratic assignment problem, the quadratic selection problem and the stochastic quadratic selection problem. The present results suggest that for these problem classes and the particular annealing schedule used, small neighborhoods are better.