Optimized annealing of traveling salesman problem from the nth-nearest-neighbor distribution

Yong Chen and Pan Zhang

Physica A: Statistical Mechanics and its Applications, 2006, vol. 371, issue 2, 627-632

Abstract: We report a new statistical general property in traveling salesman problem, that the nth-nearest-neighbor distribution of optimal tours verifies with very high accuracy an exponential decay as a function of the order of neighbor n. Defining the energy function as deviation λ from this exponential decay, which is different to the tour length d in normal annealing processes, we propose a distinct highly optimized annealing scheme which is performed in λ-space and d-space by turns. The simulation results of some standard traveling salesman problems in TSPLIB95 are presented. It is shown that our annealing recipe is superior to the canonical simulated annealing.

Keywords: Optimization; Simulated annealing; Traveling salesman problem (TSP); NP-complete (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437106004717
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:371:y:2006:i:2:p:627-632

DOI: 10.1016/j.physa.2006.04.052

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 ().