The Thermodynamics of the Travelling Salesman Problem

Abstract

In this pedagogical work we reviewed the mathematical formalism and the physical interpretation, based on statistical mechanics, of the meta-heuristics called simulated annealing. Moreover, we presented the mathematical formulation of the algorithm and why it is capable to yield the optimal solution or a good approximated solution of a given problem. Furthermore, we described the travelling salesman problem, showing its interpretation as a Markov Chain and how the simulated annealing can be used to optimize it and we did its simulations for two scenarios. Firstly, for 50 cities distributed around a circle and we found the best solution. Finally, we applied the meta-heuristic in a another instance, with 100 nodes random uniformly distributed in a square, and one shows that it allows finding a good solution.

in Portuguese