Solving traveling salesman problems by combining global and local search mechanisms

Huai Kuang Tsai, Jinn-Moon Yang, Cheng Yan Kao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

32 Scopus citations

Abstract

In this paper an evolutionary algorithm for the traveling salesman problem is proposed. The key idea is to enhance the ability of exploration and exploitation by incorporating global search with local search. A new local search, called the neighbor-join (NJ) operator, is proposed to improve the solution quality of the edge assembly crossover (EAX) considered as a global search mechanism in this paper. Our method is applied to 15 well-known traveling salesman problems with numbers of cities ranging from 101 to 3038 cities. The experimental results indicate that the neighbor-join operator is very competitive with related operators surveyed in this paper. Incorporating the NJ into the EAX significantly outperforms the method incorporating 2-opt into the EAX for some hard problems. For each test instance the average value of solution quality stays within 0.03% from the optimum. For the notorious hard problem att532, it is able to find the optimum solution 23 times in 30 independent runs.

Original languageEnglish
Title of host publicationProceedings of the 2002 Congress on Evolutionary Computation, CEC 2002
PublisherIEEE Computer Society
Pages1290-1295
Number of pages6
ISBN (Print)0780372824, 9780780372825
DOIs
StatePublished - 1 Jan 2002
Event2002 Congress on Evolutionary Computation, CEC 2002 - Honolulu, HI, United States
Duration: 12 May 200217 May 2002

Publication series

NameProceedings of the 2002 Congress on Evolutionary Computation, CEC 2002
Volume2

Conference

Conference2002 Congress on Evolutionary Computation, CEC 2002
CountryUnited States
CityHonolulu, HI
Period12/05/0217/05/02

Fingerprint Dive into the research topics of 'Solving traveling salesman problems by combining global and local search mechanisms'. Together they form a unique fingerprint.

  • Cite this

    Tsai, H. K., Yang, J-M., & Kao, C. Y. (2002). Solving traveling salesman problems by combining global and local search mechanisms. In Proceedings of the 2002 Congress on Evolutionary Computation, CEC 2002 (pp. 1290-1295). [1004429] (Proceedings of the 2002 Congress on Evolutionary Computation, CEC 2002; Vol. 2). IEEE Computer Society. https://doi.org/10.1109/CEC.2002.1004429