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.