Method to solve the travelling salesman problem using the inverse of diffusion process

Ryuichi Ugajin

Physica A: Statistical Mechanics and its Applications, 2002, vol. 307, issue 1, 260-268

Abstract: The travelling salesman problem, in which the best route between cities to be visited is chosen from a large number of possible routes, is reconsidered using the time reversal of physical dynamics, e.g. an inverse of the diffusion process. Information mediators assigned to every city diffuse as time passes, eventually merging into a single peak. When the time reversal of the dynamics is performed, the single peak splits into two peaks, each of which splits into two peaks, eventually resulting in peaks at all the cities. The hierarchy of the above bifurcations tells us how the distribution of the cities looks as the level of focus changes. This scheme is applied to a travelling salesman problem involving 532 US cities, the result of which is a 17% longer path than the optimal path.

Keywords: Optimization problem; Renormalization group; Time reversal; Diffusion process (search for similar items in EconPapers)
Date: 2002
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437101005714
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:307:y:2002:i:1:p:260-268

DOI: 10.1016/S0378-4371(01)00571-4

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