The N -City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
Ernesto Bonomi, Jean‐Luc Lutton · SIAM Review · 1984
In any N-city travelling salesman problem there are $(N - 1){! \mathord{\left/ {\vphantom {! 2}} \right. \kern- ulldelimiterspace} 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.