Research on Traveling Salesman Problem Algorithm

Abstract:

The traveling salesman problem (TSP) has been an important problem in the field of distribution and logistics and it is clearly NP-hard combinatorial optimization problem and difficult to solve. This paper gives a review of achievements of different types of Algorithms for the traveling sales man problem and outlines these advantages and limitation for these algorithms, including dynamic program, brand and bound, genetic algorithm and estimation of distribution algorithms. In addition, some of the most powerful efficiency enhancement techniques applied to TSP is discussed and quite a few common conditions of different methods for TSP are summarized. Finally, some future research direction and content are proposed.

• Periodical: Advanced Materials Research (Volumes 694-697)
• Pages: 2901-2904
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.694-697.2901
• Online since: May 2013
• Authors: Xiao Yan Yun
• Keywords: Brand and Bound, Dynamic Program, Estimation of Distribution Algorithms, Genetic Algorithm (GA), Traveling Salesman Problem (TSP)

References

[1] Bellman R. E., Dreyfus S. E.Applied Dynamic Programming.Princeton,New Jersey: Prince ton University Press(1962 )

[2] Lawler E. L., Wood D. E. Branch-and-Bound Methods:A Survey. Operations Research(1966)

[3] Holland J H.Adaptation in Nattural and Artificial systems .The University of Michigan Press, (1975)

[4] Hopfield J J. "Neural" Computation of Decisions in Optimization Problems. Biological Cybernetics(1985) 52(1) :141— 152．

DOI: 10.1007/bf00339943

[5] Kirkpatrick S, Gelatt Jr C. D., Vecchi M. P. Optimization by Simulated Annealing. Science, (1983) 220(4598):671 — 680 ．

DOI: 10.1126/science.220.4598.671

[6] Larrinaga P., Lozano J. A.Eatimation of Distribution Algorithms. A New Tool for Evolutionary Computation. Boston: Kluwer Academic Pubishers(2002)