A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem

E.H.L. Aarts, J.H.M. Korst, P.J.M. Laarhoven, van

    Research output: Contribution to journalArticleAcademicpeer-review

    77 Citations (Scopus)

    Abstract

    A quantitative study is presented of the typical behavior of the simulated annealing algorithm based on a cooling schedule presented previously by the authors. The study is based on the analysis of numerical results obtained by systematically applying the algorithm to a 100-city traveling salesman problem. The expectation and the variance of the cost are analyzed as a function of the control parameter of the cooling schedule. A semiempirical average-case performance analysis is presented from which estimates are obtained on the expectation of the average final result obtained by the simulated annealing algorithm as a function of the distance parameter, which determines the decrement of the control parameter.
    Original languageEnglish
    Pages (from-to)187-206
    Number of pages20
    JournalJournal of Statistical Physics
    Volume50
    Issue number1-2
    DOIs
    Publication statusPublished - 1988

    Fingerprint Dive into the research topics of 'A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem'. Together they form a unique fingerprint.

  • Cite this