GANGOLLI@SUSHI.STANFORD.EDU (Anil R. Gangolli) (10/03/87)
Office Phone: (415) 723-3605
Message-ID: <12339367659.44.GANGOLLI@Sushi.Stanford.EDU>
ReSent-date: Mon 5 Oct 87 10:39:35-PDT
ReSent-from: Ken Laws <LAWS@IU.AI.SRI.COM>
ReSent-to: ailist@SRI.COM
ReSent-Date: Sun 11 Oct 87 22:37:05-PDT
ReSent-From: Ken Laws <Laws@KL.SRI.Com>
ReSent-To: post-ailist@UCBVAX.Berkeley.EDU
ReSent-Message-ID: <12341800883.16.LAWS@KL.SRI.Com>
15-October-87: David Johnson (AT&T Bell Labs)
Near-Optimal Solutions to
Very Large Traveling Salesman Problems
Most experimental studies of algorithms for the Travel-
ing Salesman Problem (TSP) have concentrated on relatively
small test cases, instances with 100 cities or less. In
practice, however, much larger instances are frequently
encountered, both in engineering and scientific applica-
tions. This talk begins by surveying complexity results
about the TSP and the status of algorithms for finding
optimal solutions to small instances. It then goes on to
report the results of experiments with standard TSP heuris-
tics on large instances, from 500 cities to 100,000, examin-
ing the trade-offs obtainable between running time and qual-
ity of solution. Most of the standard heuristics will be
compared, including such new approaches as ``simulated
annealing,'' but particular emphasis will be placed on the
acknowledged ``champion,'' the sophisticated Lin-Kernighan
algorithm. Using various programming tricks, we have imple-
mented a version of this heuristic for the Euclidean case
that remains feasible even for 10,000 city instances (8
hours on a minicomputer), and continues to find tours that
are within 2% of optimal. For 20,000 or more cities, we
could still obtain tours that were within 5% of optimal
using Lin-Kernighan as a subroutine in a partitioning scheme
suggested by Karp. If one is willing to settle for slightly
worse tours, an approximate version of the Christofides
heuristic seems to stay within 20% of optimal and has quite
acceptable running times even for 100,000 cities.