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

• Climatewire | 2 hours ago | 1

### European Coastal Defenses May Reduce Destruction from Epic Storm

• Scientific American Magazine | 4 hours ago | 6

### The Internet Has Become the External Hard Drive for Our Memories

• Scientific American Magazine | 4 hours ago | 4

### Protecting Your Data on The Cloud

• Scientific American Mind | 5 hours ago | 3

### Figurative Speech Sways Decisions

• Scientific American Magazine | 5 hours ago | 2

More »

## Latest from SA Blog Network

• ### Oh the Horror! Best of the Blogs for November...

Video of the Week | 28 minutes ago
• ### Best of the Blogs for November: Oh the Horror!!

PsiVid | 31 minutes ago
• ### 4 Billion Years of Martian History in 2 Minutes

Life, Unbounded | 1 hour ago
• ### My Story Collider Story - Working Twice as Hard

The Urban Scientist | 2 hours ago
• ### Mathematics+Fatherhood: an Interview with Darren Glass

Roots of Unity | 6 hours ago

## Science Jobs of the Week

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

X

Give a 1 year subscription as low as \$14.99

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