New Monitoring Parameter for the Traveling Salesman Problem
Flavio Marín · Physical Review Letters · 1996
We introduce a new parameter, which is related to the well known traveling salesman problem (TSP), by making an analogy with a classical particle traveling around a closed trajectory of the TSP. In order to exhibit the broken symmetry associated with the rotation invariance of the TSP set of cities around any space axis, the parameter behavior, as a function of the temperature, is found along a simulated annealing process. As expected, this behavior resembles the order parameter evolution, in temperature, of some physical systems. The discussion includes a set of a few cities up to a set of 500 cities.