Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance Neural Networks
Abstract
Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights l(e) satisfying the triangle inequality. The vertex set V is partitioned into clusters V1, V2, …, Vk. The clustered traveling salesman problem (CTSP) seeks to compute the shortest Hamiltonian tour that visits all the vertices, in which the vertices of each cluster are visited consecutively. A two-level genetic algorithm (TLGA) was developed for the problem, which favors neither intra-cluster paths nor inter-cluster paths, thus realized integrated evolutionary optimization for both levels of the CTSP. Results show that the algorithm is more effective than known algorithms. A large-scale traveling salesman problem (TSP) can be converted into a CTSP by clustering so that it can then be solved by the algorithm. Test results demonstrate that the clustering TLGA for large TSPs is more effective and efficient than the classical genetic algorithm.
Recommended Citation
D. C. Wunsch and S. A. Mulder, "Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance Neural Networks," Neural Networks, Elsevier Science Ltd., Jul 2003.
Department(s)
Electrical and Computer Engineering
Keywords and Phrases
Hamiltonian Cycle; Clustered Traveling Salesman Problem (CTSP); Genetic Algorithm; Integrated Evolutionary Optimization; Traveling Salesman Problem (TSP)
International Standard Serial Number (ISSN)
0893-6080
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2003 Elsevier Science Ltd., All rights reserved.
Publication Date
01 Jul 2003
