Single minimum method for combinatorial optimization problems and an efficient algorithm of TSP problem
Dan Xu, Itsuo Kumazawa · 2002
The problem of local minima often appears when solving combinatorial optimization problems by conventional methods relying on the minimization of an objective function. A new approach to combinatorial optimization problems, called the single minimum method (SMM) is proposed. An analysis using the analogy of thermodynamics is given. In order to show how the method works, an algorithm based on it is suggested for solving the traveling salesman problem. The simulation results show that, for 10-city problems, the algorithm can find the shortest or near shortest path with a high success rate.>