The RAND team’s guarantee involves some pretty mathematics that we take up later in the book. For now it is best to think of the guarantee as a proof, like those we learned in geometry class. The Dantzig et al. proof establishes that no tour through the 49 cities can have length less than 12,345 miles. Matching the proof with their tour of precisely this length shows that this particular instance of the TSP has been settled, once and for all.

Dantzig and company missed out on the $10,000 contest, but we can report that a computer implementation of their ideas makes easy work of the 33-city TSP. A shortest route for Toody and Muldoon is depicted in Figure 1.3. Although no one in 1962 knew for certain that this was the shortest possible tour, a number of contestants did find and report this same ordering. Among the people tied for first place in the contest were mathematicians Robert Karg and Gerald Thompson, who created a hit- or-miss heuristic strategy that produced the winning solution.6 And the story has a happy ending, at least for the mathematics community. As a tiebreaker, contestants were asked to write a short essay on the virtues of one of Procter & Gamble’s products. Thompson’s prose on soaps took a grand prize.

Figure 1.3: The shortest possible route for the Car 54 contest.

4 Comments

1. 1. matrus 12:16 PM 8/17/12

   This book is an overview of the best methods designed to solve TSP. It is recommended to everyone who wants to challenge this problem.
   I wonder why the Authors keep their program (concorde) executable only on UNIX platforms?

   Reply | Report Abuse | Link to this

2. 2. Zuarrie 02:51 PM 8/24/12

   This was a great article, but the map that was used to show the shortest route is obviously incorrect or incorrectly displayed. (Where is this image from?) You can prove this by making a small change in the Four-Corners region of the US on the map shown. In that region there are three points that are very close together, but only two are connected. By connecting these and making a straight route across the north you make a shorter distance for the trip. It's obvious and can be shown with simple software. So, why is this image used?

   Reply | Report Abuse | Link to this

3. 3. ramaus 08:27 PM 8/24/12

   William - Using the given scale ( comparative distances between points) I see at least three regions where the route can be altered to shorten the distance. 1) The Four Corners region, 2) The San Francisco region, 3) The Idaho region. I can't figure out how to label or draw a map in this comment field so I can't easily prove or show you what I mean. If you published a map with the points each labeled with a letter I could easily explain.
   Claiming the shortest route is shown is not credible. Does not compute.
   I agree with Zuarrie, but instead of software I would show the shorter solutions with ruler & compass.

   Reply | Report Abuse | Link to this

4. 4. wjcook in reply to Zuarrie 02:15 PM 8/25/12

   The travel distances for the 33-city problem were taken from a Rand McNally atlas. They correspond to driving distances along the road network in the early 1960s. The image shows the shortest possible tour using these driving distances, rather than a tour based on straight-line distances as you describe. Thanks for the comment! Bill

   Reply | Report Abuse | Link to this