An Adaptive Multi-Start Algorithm for Finding Near-Optimal Solutions to the Euclidean TSP

CS270 Class Project
Spring 1999

Dan Bonachea
Eugene Ingerman
Joshua Levy
Scott McPeak

Abstract:

We present an "adaptive multi-start" algorithm for the Euclidean traveling salesman problem that uses a genetic-style population of good solutions and a multi-parent cross-breeding technique, chosen to exploit the structure of the search space, that repeatedly finds new initial tours to be locally optimized via the Lin-Kernighan algorithm. Our work generalizes and improves upon an approach of Boese et al., who devised the general algorithm and implemented it using weaker 2-opt local optimization.

Experiments show the algorithm is a vast improvement over simple "multi-start", i.e., applying Lin-Kernighan to many random instances. Both for random and several standard TSPLIB instances, it is able to find nearly optimal (or optimal) tours for problems of several thousand nodes in a few minutes on a Pentium-Pro workstation. We find these results competitive both in time and tour length with one of the most succssful known TSP algorithms, iterated Lin-Kernighan.

Paper:

paper.ps (Postscript Format)
paper.pdf (Acrobat Format)

Cool pictures of some TSP instances solved by AMS (click to enlarge):

2392-node graph from TSPLIB (pr2392)	1000-node uniform random graph	1615-node graph of our names  :-)

Source Code for AMS:

Version 1.8 - The version studied in the paper above
Version 2.8 - A new version with parallel capabilities and more diagnostic output options

Authors:

Related Links:

Concorde - a code for solving Traveling Salesman Problems
TSPBIB Home Page
TSPLIB