See Inside

# In Pursuit of the Traveling Salesman [Excerpt]

A classic problem in computation illustrates how simple problems can quickly become impossible

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.

Already a Digital subscriber? Sign-in Now

View
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?

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?

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.

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

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• Information Culture | 6 hours ago

• TechMediaNetwork | 7 hours ago | 4

### Why the Internet Sucks You in Like a Black Hole

• TechMediaNetwork | 7 hours ago

### Minor Lunar Eclipse Tonight: How to Watch It Online

• Overthinking It | 8 hours ago

### Scour: Why Most Bridges Fail

• Scientific American Magazine | 8 hours ago

More »

## Latest from SA Blog Network

• ### Barack Obama Should Call for End of All War, Not Just War on Terror

Cross-Check | 2 hours ago
• ### Dear Guardian: You've Been Played

Cocktail Party Physics | 5 hours ago

Information Culture | 6 hours ago
• ### Anti-Psychiatry Prejudice? A response to Dr. Lieberman

Molecules to Medicine | 6 hours ago
• ### Scour: Why Most Bridges Fail

Overthinking It | 8 hours ago

## Science Jobs of the Week

In Pursuit of the Traveling Salesman [Excerpt]: Scientific American Magazine

X

### Subscribe Today

Save 66% off the cover price and get a free gift!

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X