10176

# Solving Hard Traveling Salesman Problems

The task in a traveling salesman problem is to find the shortest tour through a given set of cities by visiting each city once and only once and then returning to the beginning. With this Demonstration, you can try to create a good tour, see the tour that Mathematica's built-in function FindShortestTour gives, and also see the optimal tour given by dynamic programming. The sets of cities in the Demonstration are special: The resulting traveling salesman problems are hard, so that the default method of FindShortestTour only gives a suboptimal solution.

### DETAILS

Snapshot 1: an incomplete user-defined tour
Snapshot 2: the tour found by the Automatic method of FindShortestTour
Snapshot 3: the optimal tour found by dynamic programming
The predefined sets of cities in this Demonstration are very special: they result in hard traveling salesman problems for which the Automatic method of FindShortestTour only gives a suboptimal tour. Indeed, these sets of cities were obtained by generating random cities in the square for seeds 1, 2, …, and selecting the first 10 cities for which FindShortestTour does not give the optimal solution. In these cases where we only get a suboptimal solution, the length of the tour found is often only slightly longer than the optimal tour, and thus the tour that FindShortestTour finds is often excellent.
If we consider random cities in a square, FindShortestTour with the Automatic method seems to find the optimal solution to all problems with at most six cities. With more cities, the percentage of the problems that FindShortestTour solves optimally decreases, so that, for example, the percentage is about 95, 90, 85, and 80 with about 12, 15, 17, or 19 cities, respectively.
The SimulatedAnnealing method of FindShortestTour finds the optimal solution to approximately two thirds of the hard problems considered in this Demonstration but the computing time is larger than with the Automatic method. For different values of the number of cities, the following seeds for random numbers are the hardest ones, in that even SimulatedAnnealing does not give the optimal solution to the resulting problems:
7 cities: 3536, 4257
8 cities: 437, 491, 644, 851
9 cities: 29, 125, 160
10 cities: 125, 137, 160, 337
11 cities: 122, 160, 284, 291
12 cities: 54, 81, 93, 122, 160
13 cities: 2, 26, 54, 72, 107
14 cities: 26, 54, 55, 85, 88, 107
As to the computation times (using an iMac with a 2.93 GHz Intel Core 2 Duo processor and 4 GBs of RAM):
• The computation time that FindShortestTour needs with the Automatic method is negligible when the number of cities is between 7 and 14.
• The SimulatedAnnealing method of FindShortestTour needs about one second if with 7 to 11 cities and approximately 2 seconds with 12, 13, or 14 cities.
• Dynamic programming gives the optimal solution almost immediately with at most 11 cities. For 12, 13, and 14 cities, the computation times are approximately 1, 2, and 4 seconds, respectively. Thus, when using the Demonstration, be patient and wait for the optimal tour for 13 or 14 cities.
It may be interesting to know that with 15, 16, 17, 18, 19, 20, or 21 cities, dynamic programming needs approximately 9 s, 20 s, 45 s, 2 min, 4 min, 9 min, and 25 min, respectively. (A problem with 21 cities is the largest traveling salesman problem that I have been able to solve with dynamic programming.) As can be seen, the computation time approximately doubles when the number of cities grows by one.
For 20 cities, dynamic programming has to calculate approximately 5 million values for function f (the cost function, see the program) and also approximately 5 million values for the function p that gives optimal movements. These figures are high, but dynamic programming nevertheless offers an enormous saving in computation if the alternative would be the checking of all possible tours. For 20 cities we have 19!/2 = 60 822 550 204 416 000 different tours!
Dynamic programming is one possibility to find the optimal solution to small traveling salesman problems (see [2], p. 1039), where small means a problem having at most, say, 20 cities. In general, Mathematica is well suited to solve optimization problems with dynamic programming. This is due to Mathematica's ability to calculate with recursive formulas. Indeed, to solve an optimization problem with dynamic programming we only need to write down the recursive formulas and then ask for the solution! Mathematica does all the very lengthy recursive calculations for us. Solving traveling salesman and other optimization problems with dynamic programming is considered in Ruskeepää ([1], p. 780).
Bruce Torrence has written a Demonstration called Traveling Salesman Game. In that Demonstration, we can visually study traveling salesman problems and show the tour that FindShortestTour gives. The implementation of our Demonstration is similar, but we only consider hard problems and have added the possibility of showing the optimal solution.
References:
[1] H. Ruskeepää, Mathematica Navigator: Mathematics, Statistics, and Graphics, 3rd ed., San Diego, CA: Elsevier Academic Press, 2009.
[2] W. L. Winston, Operations Research: Applications and Algorithms, 3rd ed., Belmont, CA: Duxbury Press, 1994.

### PERMANENT CITATION

Contributed by: Heikki Ruskeepää
Based on a program by: Bruce Torrence
 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 » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.