A survey on hybridizing genetic algorithm with dynamic programming for solving the traveling salesman problem
作者： PHAM Dinh Thanh , HUYNH Thi Thanh Binh , BUI Thu Lam , None
DOI: 10.1109/SOCPAR.2013.7054102
关键词:
摘要: Traveling Salesman Problem (TSP) is a well-known NP-hard problem. Many algorithms were developed to solve this problem and gave the nearly optimal solutions within reasonable time. This paper presents survey about combination Genetic Algorithm (GA) with Dynamic Programming (DP) for solving TSP. We also setup between GA DP experimented on 7 Euclidean instances derived from TSP-lib. Experimental results are reported show efficiency of algorithm comparing genetic algorithm.
mirlabs.net 参考文章(21)
Bernd Freisleben, Peter Merz, New Genetic Local Search Operators for the Traveling Salesman Problem parallel problem solving from nature. pp. 890- 899 ,(1996) , 10.1007/3-540-61723-X_1052
M. Birattari, T. Stutzle, M. Dorigo, Ant Colony Optimization ,(2004)
J.-M. Renders, H. Bersini, Hybridizing genetic algorithms with hill-climbing methods for global optimization: two possible ways world congress on computational intelligence. pp. 312- 317 ,(1994) , 10.1109/ICEC.1994.349948
Wan-Rong Jih, J. Yung-Jen Hsu, Dynamic vehicle routing using hybrid genetic algorithms international conference on robotics and automation. ,vol. 1, pp. 453- 458 ,(1999) , 10.1109/ROBOT.1999.770019
Michael Held, Richard M. Karp, A Dynamic Programming Approach to Sequencing Problems Journal of The Society for Industrial and Applied Mathematics. ,vol. 10, pp. 196- 210 ,(1962) , 10.1137/0110015
L. Adleman, Molecular computation of solutions to combinatorial problems Science. ,vol. 266, pp. 1021- 1024 ,(1994) , 10.1126/SCIENCE.7973651
Lawrence V. Snyder, Mark S. Daskin, A random-key genetic algorithm for the generalized traveling salesman problem European Journal of Operational Research. ,vol. 174, pp. 38- 53 ,(2006) , 10.1016/J.EJOR.2004.09.057
A.G. Chentsov, L.N. Korotayeva, The dynamic programming method in the generalized traveling salesman problem Mathematical and Computer Modelling. ,vol. 25, pp. 93- 105 ,(1997) , 10.1016/S0895-7177(96)00187-2
Matteo Fischetti, Juan José Salazar González, Paolo Toth, A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem Operations Research. ,vol. 45, pp. 378- 394 ,(1997) , 10.1287/OPRE.45.3.378
S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing Science. ,vol. 220, pp. 671- 680 ,(1983) , 10.1126/SCIENCE.220.4598.671