Finding the Shortest Traveling Salesman Tour

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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 .

[more]

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.

[less]

Contributed by: Stan Wagon (Macalester College) (March 2011)
Open content licensed under CC BY-NC-SA


Snapshots


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.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send