Solving traveling salesman problems by combining global and local search mechanisms
Resource
Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on
Journal
Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on
Pages
-
Date Issued
2002-05
Date
2002-05
Author(s)
Tsai, Huai-Kuang
Yang, Jinn-Moon
Kao, Cheng-Yan
DOI
N/A
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.
SDGs
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
01004429.pdf
Size
636.86 KB
Format
Adobe PDF
Checksum
(MD5):4b16eff32abd7208acfcfbd7a7cb5903