A thorough study of the performance of simulated annealing in the traveling salesman problem under correlated and long tailed spatial scenarios

Roberto da Silva, Eliseu Venites Filho and Alexandre Alves

Physica A: Statistical Mechanics and its Applications, 2021, vol. 577, issue C

Abstract: Metaheuristics, as the simulated annealing used in the optimization of disordered systems, goes beyond physics, and the traveling salesman is a paradigmatic NP-complete problem that allows to infer important theoretical properties of the algorithm in different random environments. Many versions of the algorithm are explored in the literature, but so far the effects of the statistical distribution of the coordinates of the cities on the performance of the algorithm has been neglected. We propose a simple way to explore this aspect by analyzing the performance of a standard version of the simulated annealing (geometric cooling) in correlated systems with a simple and useful method based on a linear combination of independent random variables. Our results suggest that performance depends on the shape of the statistical distribution of the coordinates but not necessarily on its variance corroborated by the cases of uniform and normal distributions. On the other hand, a study with different power laws (different decay exponents) for the coordinates always produces different performances. We show that the performance of the simulated annealing, even in its best version, is not improved when the distribution of the coordinates does not have the first moment. However, surprisingly, we still observe improvements in situations where the second moment is not defined but not where the first one is not defined. Finite size scaling, fits, and universal laws support all of our results. In addition our study show when the cost must be scaled.

Keywords: Simulated annealing; Traveling salesman problem; Correlated spatial scenarios; Long tailed spatial scenarios; Performance; Pedagogical aspects in optimization (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037843712100340X
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:577:y:2021:i:c:s037843712100340x

DOI: 10.1016/j.physa.2021.126067

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().