An evolutionary algorithm for large traveling salesman problems

Huai Kuang Tsai*, Jinn-Moon Yang, Yuan Fang Tsai, Cheng Yan Kao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

112 Scopus citations

Abstract

This work proposes an evolutionary algorithm, called the heterogeneous selection evolutionary algorithm (HeSEA), for solving large traveling salesman problems (TSP). The strengths and limitations of numerous well-known genetic operators are first analyzed, along with local search methods for TSPs from their solution qualities and mechanisms for preserving and adding edges. Based on this analysis, a new approach, HeSEA is proposed which integrates edge assembly crossover (EAX) and Lin-Kernighan (LK) local search, through family competition and heterogeneous pairing selection. This study demonstrates experimentally that EAX and LK can compensate for each other's disadvantages. Family competition and heterogeneous pairing selections are used to maintain the diversity of the population, which is especially useful for evolutionary algorithms in solving large TSPs. The proposed method was evaluated on 16 well-known TSPs in which the numbers of cities range from 318 to 13509. Experimental results indicate that HeSEA performs well and is very competitive with other approaches. The proposed method can determine the optimum path when the number of cities is under 10 000 and the mean solution quality is within 0.0074% above the optimum for each test problem. These findings imply that the proposed method can find tours robustly with a fixed small population and a limited family competition length in reasonable time, when used to solve large TSPs.

Original languageEnglish
Pages (from-to)1718-1729
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume34
Issue number4
DOIs
StatePublished - Aug 2004

Fingerprint

Dive into the research topics of 'An evolutionary algorithm for large traveling salesman problems'. Together they form a unique fingerprint.

Cite this