A Multiple Heuristic Search Algorithm for Solving Traveling Salesman Problem
This research was carried out to solve the Traveling Salesman Problem (TSP) using a multiple heuristic search algorithm. Two main operations of Complete 2-Opt (C2Opt) and Smallest Square (SS) were combined in a Genetic Algorithm (GA) and applied to the TSP. The C2Opt is based on the 2-Opt heuristic search which can remove all crossed edges in the tour if the repeat times are sufficient. The SS selects the shorter edges than the C2Opt. The problem of the SS is that the city orders of the original tour were changed while the SS was applied,hence the crossed edges could not be removed completely.However, a reasonable result is presented by combining the C2Opt and the SS in the GA for the TSP in our experiment.Another two operations the Deletion (DL) and the Best Part Collector (BPC) are discussed. The DL was used for removing the duplicates from the population and the BPC was used for collecting the best part among the individuals to the elite individual.
GA TSP C2Opt SS DL BPC
Peng Gang Ichiro Iimura Shigeru Nakayama
Department of Information and Computer Science, Faculty of Engineering,Kagoshima University, 1-21-40 Korimoto, Kagoshima, 890-0065, Japan
国际会议
成都
英文
779-783
2003-08-27（万方平台首次上网日期，不代表论文的发表时间）