Abstract
The Traveling Salesman Problem (TSP) is a very hard optimization problem in the field of operations research. It has been shown to be NP-complete and is an often-used benchmark for new optimization techniques. One of the main challenges with this problem is that standard, non-AI heuristic approaches such as the Lin-Kernighan algorithm (LK) and the chained LK variant are currently very effective and in wide use for the common fully connected, Euclidean variant that is considered here. This paper presents an algorithm that uses adaptive resonance theory (ART) in combination with a variation of the Lin-Kernighan local optimization algorithm to solve very large instances of the TSP. the primary advantage of this algorithm over traditional LK and chained-LK approaches is the increased scalability and parallelism allowed by the divide-and-conquer clustering paradigm. Tours obtained by the algorithm are lower quality, but scaling is much better and there is a high potential for increasing performance using parallel hardware. © 2003 Elsevier Science Ltd. All rights reserved.
Recommended Citation
S. A. Mulder and D. C. Wunsch, "Million City Traveling Salesman Problem Solution by Divide and Conquer Clustering with Adaptive Resonance Neural Networks," Neural Networks, vol. 16, no. 5 thru 6, pp. 827 - 832, Elsevier, Jan 2003.
The definitive version is available at https://doi.org/10.1016/S0893-6080(03)00130-8
Department(s)
Electrical and Computer Engineering
Second Department
Computer Science
Keywords and Phrases
Adaptive resonance theory; Lin-Kernighan algorithm; Traveling salesman problem
International Standard Serial Number (ISSN)
0893-6080
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2024 Elsevier, All rights reserved.
Publication Date
01 Jan 2003
PubMed ID
12850040
Comments
National Science Foundation, Grant None