%0 Journal Article %1 Cerny1985Thermodynamical %A Cerný, V. %B Journal of Optimization Theory and Applications %D 1985 %I Kluwer Academic Publishers-Plenum Publishers %J Journal of Optimization Theory and Applications %K classic simulated-annealing %N 1 %P 41--51 %R 10.1007/bf00940812 %T Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm %U http://dx.doi.org/10.1007/bf00940812 %V 45 %X We present a Monte Carlo algorithm to find approximate solutions of the traveling salesman problem. The algorithm generates randomly the permutations of the stations of the traveling 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 can get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples.

@article{Cerny1985Thermodynamical, abstract = {We present a Monte Carlo algorithm to find approximate solutions of the traveling salesman problem. The algorithm generates randomly the permutations of the stations of the traveling 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 can get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples.}, added-at = {2018-12-02T16:09:07.000+0100}, author = {\v{C}ern\'{y}, V.}, biburl = {https://www.bibsonomy.org/bibtex/208600aaa24b2f1fcde1b2aa1e15cef9f/karthikraman}, booktitle = {Journal of Optimization Theory and Applications}, citeulike-article-id = {2634818}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/bf00940812}, citeulike-linkout-1 = {http://www.springerlink.com/content/gt0743622913gg33}, citeulike-linkout-2 = {http://link.springer.com/article/10.1007/BF00940812}, day = 1, doi = {10.1007/bf00940812}, interhash = {4452b2c3242c9b587608f0c6b60e93cf}, intrahash = {08600aaa24b2f1fcde1b2aa1e15cef9f}, issn = {0022-3239}, journal = {Journal of Optimization Theory and Applications}, keywords = {classic simulated-annealing}, month = jan, number = 1, pages = {41--51}, posted-at = {2016-04-20 06:27:35}, priority = {2}, publisher = {Kluwer Academic Publishers-Plenum Publishers}, timestamp = {2018-12-02T16:09:07.000+0100}, title = {Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm}, url = {http://dx.doi.org/10.1007/bf00940812}, volume = 45, year = 1985 }