Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!hsdndev!cmcl2!adm!lhc!chrisk
From: chrisk@nlm.nih.gov (Christopher Y. Kim)
Newsgroups: comp.ai.neural-nets
Subject: Re: Travelling Salesman problem
Summary: TSP
Message-ID: <1991Apr16.180551.4961@nlm.nih.gov>
Date: 16 Apr 91 18:05:51 GMT
References: <1991Apr12.162922.4749@nlm.nih.gov>
Organization: National Library of Medicine
Lines: 60

Thank you for all the responses.  Obviously, I have a lot of reading to do,
but it seems that the neural net approach is generally slower than conventional
heuristic algorithms.  I will summarize what has been mailed to me so far for
the convenience of those who wanted me to forward the e-mail replies.  I will
abbreviate the "Travelling Salesman Problem" as TSP below.

The "classic" papers plus a book:

(1) Lin S, Kernighan BW. An Effective Heuristic Algorithm for the TSP.
        Operations Research 21:2, 498-516 (1973).
(2) Hopfield JJ, Tank, DW. "Neural" computation of decisions in optimization
	problems. Biological Cybernetics 52, 141-152 (1985).
(3) Lawler EL, et al (eds.). The TSP.  New York: Wiley, 1985.
        (book - reportedly comprehensive)

One VERY recent article that is a good place to start:

    Xu X, Tsai WT. Effective Neural Algorithms for the TSP. Neural Networks
	4:2, 193-206 (1991).

Elastic net method

(1) Durbin R, Willshaw DJ. An analogue approach to the TSP using an elastic
	net method. Nature 326, 689-691 (1987).
(2) Durbin R, Szeliski R, Yuille, A. An Analysis of the Elstic Net Approach
	to the TSP. Neural Computation 1, 348-358 (1989).

Kohonen's Self-Organizationap

(1) Angeniol B, Vaubois G, Texier J. Self-organizing feature maps and the
	TSP. Neural Networks 1, 289-293 (1988).
(2) Fort JC. Solving a Combinatorial Problem via a Self-Organizing Process:
	An Application of the Kohonen Algorithm to the TSP. Biological
	Cybernetics 59, 33-40 (1988).

Genetic Algorithms

(1) Grefenstette J, Gopal R, Rosmaita B, Van Gucht D. Genetic Algorithms
	for TSP. Proceedings of the Int'l Conf on Genetic Alogorithms
	and their Applications, 1985.
(2) Oliver IM, Smith DJ, Holand JRC. A study of permutation crossover
	operators on the TSP. Proceedings of the Int'l Conf on Genetic
	Algorithms and their Applicatons, 1987.

Other sources also mentioned -

(1) Kirkpatrick, Gellati, Vecchi. [title?]. Science 220, 671-680 (1983).
	[Simulated annealing re: Lin & Kernighan, 1973]
(2) Yuille A. Generalized Deformable Models, Staistical Physics and Matching
	Problems. Neural Computation 2, 1-24 (1990).

I apologize for any typos, especially as I have only looked up five of these
sources so far.

Thanks to luox@copper.ucs.indiana.edu, muttiah@ecn.purdue.edu, srikanth@
    rex.cs.tulane.edu, kcj@goanna.cs.rmit.oz.au, siemon@anja.informatik.
    uni-dortmund.de, lesher@ncifcrf.gov, and smagt@fwi.uva.nl
for their contributions to this list.

Chris Kim :-)