Computational intelligence and the traveling salesman
Donald C. Wunsch, Samuel A. Mulder · 2004
The Traveling Salesman Problem (TSP) is one of the most widely studied problems in the computer science literature. As a member of the class of NP-complete problems, practical approaches to the TSP require heuristics and approximation techniques. Computational Intelligence approaches have traditionally performed very poorly on combinatorial optimization problems such as the TSP, when compared to results in Operations Research. This dissertation explores two different Computational Intelligence techniques and combines them with the latest Operations Research local search heuristics to develop new heuristics that expand the capabilities of existing techniques. The first approach combines an Adaptive Resonance Theory (ART) neural network with the iterated Lin-Kernighan algorithm to divide and conquer extremely large TSPs. This new algorithm provides significant advantages in scaling and memory usage. The second approach uses an Evolutionary Algorithm to parallelize the iterated Lin-Kernighan algorithm and explore the search space more thoroughly. This hybrid approach converges more slowly on the standard randomly distributed problems, but improves the search capability as compared to the standard approach on “hard” TSP instances from the TSPLIB. Overall, these two new heuristics demonstrate that Computational intelligence does have something to add to the field of combinatorial optimization and provide direction for future research. In addition, a library of TSP algorithms was developed. Availability of these algorithms in an easy to modify form should open the door to future TSP research. Current versions will be made available at www.traveling-salesman.org.* *This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation).