The N-city travelling salesman problem: Statistical mechanics and the Metropolis algorithm. (English) Zbl 0551.90095

Bonomi, Ernesto; Lutton, Jean-Luc

SIAM Rev. 26, 551-568 (1984).

In any N-city travelling salesman problem there are (N-1)!/2 possible tours. We use the Metropolis algorithm to generate a sequence of such tours. This sequence may be viewed as the random evolution of a physical system in contact with a heat-bath. As the temperature is lowered, the tours generated approach the optimal tour. It appears that for large N one arrives within a few percent of the optimal solution in better than quadratic time.

MSC:

90C35	Programming involving graphs or networks
90C10	Integer programming
65K05	Numerical mathematical programming methods
60K35	Interacting random processes; statistical mechanics type models; percolation theory

Keywords:

statistical mechanics; N-city travelling salesman; Metropolis algorithm; random evolution; physical system; heat-bath