Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm. (English) Zbl 0534.90091

We present a Monte Carlo algorithm to find approximate solutions of the travelling salesman problem. The algorithm generates randomly the permutations of the stations of the travelling salesman trip, with probability depending on the length of the corresponding route. Reasoning by analogy with statistical thermodynamics, we use the probability given by the Boltzmann-Gibbs distribution. Surprisingly enough, using this simple algorithm, one cat get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples.
We conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.


90C35 Programming involving graphs or networks
65C05 Monte Carlo methods
80A10 Classical and relativistic thermodynamics
90C10 Integer programming
Full Text: DOI


[1] Kittel, C.,Thermal Physics, John Wiley and Sons, New York, New York, 1969.
[2] Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., andTeller, E.,Equation of State Calculations by Fast Computing Machines, Journal of Chemical Physics, Vol. 21, pp. 1087–1092, 1953. · doi:10.1063/1.1699114
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.