From: "Jos A. Horsmeier" <jos@and.nl>
Newsgroups: sci.math
Subject: Re: Travelling Salesman Problem
Date: Fri, 16 Jan 1998 10:03:14 +0100

Ben Bright wrote:

>     I need to find the optimal drilling sequence for the list of holes such
> that the machine drills all of the holes while travelling the shortest
> distance possible(thus making the drilling process as fast as possible).
> I have done some Web searching, but I have not found a clear explanation of
> an algorithm (if there is one).  Any help is greatly appreciated.  This
> would be a nice 'finishing touch' to the project.

If your TSP is undirected, i.e. the cost A --> B is equal to the cost B
--> A,
there's a neat heuristic available; have a look at Papadimitriou and
Steiglitz, 
"Combinatorial Optimization" (Prentice-Hall, 1982, ISBN 0-13-152462-3)
and
check out the Lin-Kernighan algorithm (don't get confused if someone
mentions
the Kernighan-Lin algorithm too; that one deals with graph partitioning
which
is quite a different cup of tea).

You might take a peek at one of the following too:

Lin and Kernighan, "Operations Research 21", 498--516 (1973). 

Fredman, Johnson, McGeoch, Ostheimer, "Data Structures for Traveling
Salesman", 4th Annual ACM-SIAM Symposium on Discrete Algorithms,
145--154 (1993).

Bentley, "Fast algorithms for geometric traveling salesman problems",
ORSA Journal on Computing 4, 387--411 (1992).

The following web page is a nice starting point for some more
literature:

http://www.npac.syr.edu/copywrite/pcw/node260.html

kind regards,

Jos aka jos@and.nl