9464

The Traveling Salesman Problem 1: Optimal Paths

A salesman, starting from his home city, needs to visit every city on his route exactly once and finally return home. As there are only a finite number of possibilities, it is plausible for him to select the visiting order so that the total distance traveled in his tour is as small as possible. All the data he needs is to know for each pair of cities the distance from one to the other.
Because of its wealth of applications, this problem, called the traveling salesman problem (TSP), has received much attention since 1931. It has turned out to be not at all simple to use the data to get an answer, and so this problem has gained a reputation for being one of the most important unsolved problems of our time. The search for efficient methods to solve it (since it was shown to be NP-hard, which roughly means that the solution time by any method we apply to it exceeds any practical bounds) now concentrates mainly in heuristic approximation methods.
In this Demonstration, a straightforward approach is applied to the solving of TSP. A number of points are generated randomly, in the order shown by their labels. The complete graph on these points is shown in gray. We then exhaustively check every permutation (path) for optimality. The case already presents a noticeable delay and case 9 shows that practical cases of even dozens of vertices cannot be tackled by this approach. This Demonstration can be used to obtain (through using the Paste Snapshot option) examples of optimal paths useful in an academic setting.

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Reference
[1] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, New York: John Wiley & Sons, 1985.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+