A note on the effect of neighborhood structure in simulated annealing

Kah Mun Cheh, Jeffrey B. Goldberg, Ronald G. Askin

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


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 note we consider a problem specific parameter; the neighborhood structure. We motivate the importance of considering the neighborhood by appealing to results on the convergence rate of simulated annealing and previous empirical results. We 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. Our results suggest that for these problem classes and the particular annealing schedule used, small neighborhoods are better.

Original languageEnglish (US)
Pages (from-to)537-547
Number of pages11
JournalComputers and Operations Research
Issue number6
StatePublished - 1991
Externally publishedYes

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'A note on the effect of neighborhood structure in simulated annealing'. Together they form a unique fingerprint.

Cite this