Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
type: Item
instance of: scholarly article
title: Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
zbMATH Open document ID: 0534.90091
DOI: 10.1007/BF00940812
author: V. Černý
published in: Journal of Optimization Theory and Applications
publication date: 1985-01-01T00:00:00Z
review text: We present a Monte Carlo algorithm to find approximate solutions of the travelling salesman problem. The algorithm generates randomly the permutations of the stations of the travelling 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 cat get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples. We conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 65C05
Mathematics Subject Classification ID: 80A10
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 3849000
zbMATH Keywords: importance sampling
zbMATH Keywords: Monte Carlo algorithm
zbMATH Keywords: approximate solutions
zbMATH Keywords: travelling salesman
zbMATH Keywords: Boltzmann-Gibbs distribution
zbMATH Keywords: analogy with thermodynamics
Wikidata QID: Q55967971
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 3849000