New Method of Solving the Traveling Salesman Problem Based on Real Space Renormalization Theory
Yoshiyuki Usami, Kano Yoshiki · Physical Review Letters · 1995
We propose a new method of solving the traveling salesman problem in this Letter. A new technique, whose concept comes from real space renormalization theory, is introduced to solve the combinatorial problem of operation research. Examples of the calculation applied from the 48-cities to the 532-cities problem and a theoretical estimate of the computational effort are presented. It was found that the present method belongs to the group of the fastest computing algorithm of the traveling salesman problem. Throughout this work we show an interesting cross of operation research and statistical physics.