Traveling Salesman Problem

Date: 05/24/2001 at 13:37:28
From: Matt Anderson
Subject: Traveling Salesman Problem

Is there an easy solution to the "Traveling Salesman Problem"?

Date: 05/24/2001 at 15:36:15
From: Doctor Shawn
Subject: Re: Traveling Salesman Problem

Matt,

There are easy solutions to some Traveling Salesman Problems (TSPs). 
In general, however, this is actually very hard. The basic premise 
behind a TSP (as you probably already know) is to minimize the 
distance that a salesman has to travel to get to each of a set of 
cities, visiting each only once. The problem applies to any number of 
cities, so the easy solutions involve only a few nodes. If there are 
two cities, there's only one path. In general, there are (n-1)!/2 
paths that can be taken, assuming symmetry (that is, the distance from 
A to B is the same as the distance from B to A). For an explanation of 
why that is, see:

   The Travelling Salesman Problem - Robert Dakin
   http://www.pcug.org.au/~dakin/tsp.htm   

The number of paths becomes excessively large as n increases. Since 
there isn't a computer fast enough to figure out all the possible 
routes, algorithms have to be developed that will return local minima, 
i.e., solutions that are better than any 'nearby' solutions.  These
will be pretty good, but can't be guaranteed to be OPTIMAL without  
figuring out the lengths of all the paths.

The TSP is one of a special class of problems known as "NP-complete." 
Any NP-complete problem could theoretically be solved by converting it
to another, equivalent NP-complete problem.  So if _any_ NP-complete 
problem can be solved deterministically (that is, without depending on
luck) in polynomial time, then _all_ of them can.  However, no one knows
whether this is the case.  It's an open research question. 

But even if the TSP could be solved in polynomial time, note that 
polynomial time, in terms of computer algorithms, is very, very slow. 
In fact, it's hard to get much worse. (A really good algorithm will 
run in "n log n" time, meaning that for n additional inputs, it takes 
n log n times as long to run. An algorithm that runs in polynomial 
time is just terrible, and will never be implemented if there's any 
other choice at all.) Some of these terms might be a little foreign to 
you; check out

   NP-complete from FOLDOC
   http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?NP-complete   

One way to try to get around this is to use less stupid algorithms 
(brute force lacks elegance). However, as I said earlier, you won't be 
able to guarantee it's the absolute best solution, although it'll be a 
pretty good one. For information about these kinds of algorithms, look 
at:

   Computer Scientist Solves Old Salesman Problem - ScienceDaily
   http://www.sciencedaily.com/releases/2001/01/010116075125.htm   

Research into NP complete problems has gone off on some pretty wild 
tangents in recent years - quantum computers would be optimal in 
solving them, as would biological computation. Many advances in DNA 
computing have been specifically intended to solve this class of 
problem. For some background on that, review:

   DNA Computing - (Dr. Leonard Adleman) - Dr. Karron
   http://www.casi.net/D.BioInformatics1/D.Fall2000ClassPage/DC1/dc.htm   

So in answer to your question, there is an easy answer only when there 
aren't enough cities to make the problem interesting. Understanding 
why the problem is so challenging is half the fun, and there's still 
research being done on it.

Hope that helps. Feel free to write back with any other questions, or 
if you just want to talk about this some more.

- Doctor Shawn, The Math Forum
  http://mathforum.org/dr.math/   

Date: 04/28/2003 at 16:28:21
From: Tony
Subject: Minimizing a route

My sister runs a route though 31 locations (she delivers catalogs).  
She starts from her house and goes through each one of the points, 
finally ending up back at her house at the end.  I do not believe 
the route she runs is the most efficient.  What technique do I use 
to find the most efficient route (fewest miles).

Date: 04/28/2003 at 16:45:28
From: Doctor Mitteldorf
Subject: Re: Minimizing a route

Dear Tony,

This is a famous problem in computer science, called the "traveling
salesman problem." It resists computational methods. It's roughly 
true that no one has yet come up with a solution much better than the
"brute force" technique of trying all different paths. 

Trying lots of different possibilities by hand is not such a bad way 
to go about the problem. Some computer programs take the approach of 
looking for optimized sub-routes around some subset of the points, 
then mixing these together in different combinations.

Here's a site from the Princeton Mathematics Department devoted 
entirely to work on the "TSP":

   Solving Traveling Salesman Problems
   http://www.math.princeton.edu/tsp/

And here's a site that indexes computer programs that you can download
and run that will try to solve the problem.

   TSP solvers - The Stony Brook Algorithm Repository
   http://www.cs.sunysb.edu/~algorith/implement/tsp/implement.shtml

- Doctor Mitteldorf, The Math Forum
  http://mathforum.org/dr.math/