Lawrence Berkeley National Laboratory
An Improved Adaptive Multi-Start Approach to Finding Near-Optimal Solutions to the Euclidean TSP.
- Author(s): Bonachea, Dan
- Ingerman, Eugene
- Levy, Joshua
- McPeak, Scott
- Editor(s): Whitley, L Darrell
- Goldberg, David E
- Cantú-Paz, Erick
- Spector, Lee
- Parmee, Ian C
- Beyer, Hans-Georg
- et al.
Published Web Locationhttps://doi.org/10.25344/S4WC7G
We present an “adaptive multi-start” genetic algorithm for the Euclidean traveling salesman problem that uses a population of tours locally optimized by the Lin-Kernighan algorithm. An all-parent cross-breeding technique, chosen to exploit the structure of the search space, generates better locally optimized tours. Our work generalizes and improves upon the approach of Boese et al. . Experiments show the algorithm is a vast improvement over simple “multi-start,” i.e., repeatedly applying Lin-Kernighan to many random initial tours. Both for random and several standard tsplib  instances, it is able to find nearly optimal (or optimal) tours for problems of several thousand cities in a few minutes on a Pentium Pro workstation. We find these results are competitive both in time and tour length with one of the most successful TSP algorithms, Iterated Lin-Kernighan.