Snapshot 1: an incomplete user-defined tour

Snapshot 2: the tour found by the

Automatic method of

FindShortestTourSnapshot 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.

[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.