Finding the Shortest Traveling Salesman Tour
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]
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.
Permanent Citation