An Improved Adaptive Multi-Start Approach to Finding Near-Optimal Solutions to the Euclidean TSP
Skip to main content
eScholarship
Open Access Publications from the University of California

An Improved Adaptive Multi-Start Approach to Finding Near-Optimal Solutions to the Euclidean TSP

  • Author(s): Bonachea, D
  • Ingerman, E
  • Levy, J
  • McPeak, S
  • Editor(s): Whitley, LD
  • Goldberg, DE
  • Cantú-Paz, E
  • Spector, L
  • Parmee, IC
  • Beyer, H-G
  • et al.

Published Web Location

https://doi.org/10.25344/S4WC7G
Abstract

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. [2]. 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 [5] 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.

Main Content
Current View