9873

Finding the Shortest Traveling Salesman Tour

For sets of points that are not too large one can solve the traveling salesman problem—find the shortest cycle that visits all the points—by using integer linear programming (ILP), available in Mathematica via the Minimize function. Given points, introduce a variable for each possible edge, , the idea being that means that one goes from to in the tour. Then create the equations that force and that each vertex has degree exactly 2, and use the objective function that sums the product of the distances between points with .
Using ILP guarantees that the solutions are integers (and therefore are either 0 or 1). The optimal solution to this linear programming problem will likely be a set of disjoint cycles, as opposed to a single cycle. The total length of that set provides a lower bound on the optimal tour length. One can then add equations that destroy the cycles and run the minimizer again in the hope that, after not too many iterations of this process, the result will be a single cycle. That must then be the optimal TSP solution for the given points. For sets of up to 200 points this method works well, in that not too many iterations are needed. It is a bit slow for more than 50 points, as can be seen in the logarithmic timing chart; thus for this Demonstration the cycles for each step have been precomputed.
The points in these examples are defined by a slight perturbation of the Gaussian primes.

SNAPSHOTS

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

DETAILS

The snapshots show the three iterations required to find the optimal solution in the case of 60 points; that requires only three seconds.
The equations used to set the degrees are: for each . The inequality used to break a cycle is: . The objective function that is minimized is: , where is the point.
For more details, see Chapter 13 of S. Wagon, Mathematica in Action, 3rd ed., New York, Springer, 2010.
    • 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.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
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+