Solving Hard Traveling Salesman Problems

Create your tour:

1. click consecutive cities to find a good tour

2. beat the tour given by FindShortestTour (FST)

3. find the optimal tour

number of citiesand seed forrandom numbers

{7,491}

go back in your tour

clear your tour

length of the tourgiven by FST

tour given by FST

method of FST

Automatic

length of theoptimal tour

optimal tour


lengths

your tour	0
the tour given by FST	24.7211
the optimal tour	24.7211

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.