A survey on hybridizing genetic algorithm with dynamic programming for solving the traveling salesman problem

Author

Pham Dinh Thanh ; Huynh Thi Thanh Binh ; Bui Thu Lam

Author_Institution

Fac. of Math. - Phys. - Informatic, Tay Bac Univ., SonLa, Vietnam

fYear

2013

fDate

15-18 Dec. 2013

Firstpage

66

Lastpage

71

Abstract

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 a survey about the combination Genetic Algorithm (GA) with Dynamic Programming (DP) for solving TSP. We also setup a combination between GA and DP for this problem and experimented on 7 Euclidean instances derived from TSP-lib. Experimental results are reported to show the efficiency of the experimented algorithm comparing to the genetic algorithm.

Keywords

dynamic programming; genetic algorithms; travelling salesman problems; DP; GA; NP-hard problem; TSP; dynamic programming; genetic algorithm; traveling salesman problem; Cities and towns; Dynamic programming; Genetic algorithms; Genetics; Heuristic algorithms; Sociology; Statistics; Brand & Bound algorithm; Dynamic Programming; Genetic Algorithm; Traveling Salesman Problem;

fLanguage

English

Publisher

ieee

Conference_Titel

Soft Computing and Pattern Recognition (SoCPaR), 2013 International Conference of

Conference_Location

Hanoi

Print_ISBN

978-1-4799-3399-0

Type

conf

DOI

10.1109/SOCPAR.2013.7054102

Filename

7054102