Solving traveling salesman problems by combining global and local search mechanisms

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

研究成果: Conference contribution同行評審

32 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Proceedings of the 2002 Congress on Evolutionary Computation, CEC 2002
發行者IEEE Computer Society
頁面1290-1295
頁數6
ISBN(列印)0780372824, 9780780372825
DOIs
出版狀態Published - 1 一月 2002
事件2002 Congress on Evolutionary Computation, CEC 2002 - Honolulu, HI, United States
持續時間: 12 五月 200217 五月 2002

出版系列

名字Proceedings of the 2002 Congress on Evolutionary Computation, CEC 2002
2

Conference

Conference2002 Congress on Evolutionary Computation, CEC 2002
國家United States
城市Honolulu, HI
期間12/05/0217/05/02

指紋 深入研究「Solving traveling salesman problems by combining global and local search mechanisms」主題。共同形成了獨特的指紋。

引用此