Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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

- 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/
```
Associated Topics:
College Discrete Math
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search