See Inside

# In Pursuit of the Traveling Salesman [Excerpt]

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

Image: Princeton University Press

Excerpted from IN PURSUIT OF THE TRAVELING SALESMAN by William J. Cook. Copyright © 2012 by Princeton University Press. Reprinted by permission.

It grew out of the trio’s efforts to find solutions for a classic mathematical problem—the “Traveling Salesman” problem—which has long defied solution by man, or by the fastest computers he uses.

—IBM Press Release, 1964.

An advertising campaign by Procter & Gamble caused a stir among applied mathematicians in the spring of 1962. The campaign featured a contest with a \$10,000 prize. Enough to purchase a house at the time. From the official rules:

Imagine that Toody and Muldoon want to drive around the country and visit each of the 33 locations represented by dots on the contest map, and that in doing so, they want to travel the shortest possible route. You should plan a route for them from location to location which will result in the shortest total mileage from Chicago, Illinois back to Chicago, Illinois.

Police officers Toody and Muldoon navigated Car 54 in a popular American television series. Their 33-city task is an instance of the traveling salesman problem, or TSP for short. In its general form, we are given a collection of cities and the distance to travel between each pair of them. The problem is to find the shortest route to visit each city and to return to the starting point.

Is the general problem easy, hard, or impossible? The short answer is that no one really knows. This is both the mystery and attraction of this famous challenge in computational mathematics. And much more than a struggling salesman is at stake. The TSP is the focal point of a larger debate on the nature of complexity and possible limits to human knowledge. If you are ready for action, then a sharp pencil and a clean piece of paper are all you may need to give a helping hand to the salesman and possibly to make a quantum leap in our understanding of the world in which he or she travels.

Tour of the United States

Despite its nasty reputation, the TSP is an easy enough task from one perspective: there are only finitely many possible routes through a given set of cities. So a 1962-era mathematician could have checked each possible Toody-Muldoon tour, recorded the shortest, sent the solution to Procter & Gamble, and waited for the \$10,000 check to arrive in the mail. A simple and flawless strategy. With one possible catch. The number of distinct tours is exceedingly large to consider checking one by one.

This difficulty was noticed in 1930 by the Austrian mathematician and economist Karl Menger, who first brought the challenge of the TSP to the attention of the mathematics community. “This problem is of course solvable by finitely many trials. Rules that give a number of trials below the number of permutations of the given points are not known.” A tour can be specified by announcing the order in which the cities are to be visited. For example, if we label the 33 destinations of Toody and Muldoon as A through Z and 1 though 7, that is, A for Chicago, B for Wichita, etc., then we can record a possible tour as

ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567

or any other arrangement of the 33 symbols. Each such arrangement is a permutation of the symbols. The ordering implied by the arrangement is circular, in that we travel from the last city back to the first. So we can record the same tour in 33 ways, depending on which city we put in the first position. To avoid such overcounting, we may as well always start with city A. This leaves 32 choices for the second city, 31 choices for the third city, and so on. Altogether, we have 32×31×30×···×3×2×1 tours to consider. This is the total number of permutations of 32 objects. It is written as 32! and spoken as 32 factorial.

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

• 30 Under 30 | 6 hours ago

### 30 under 30: Investigating Molecular Messengers and Human Health

• Talking back | 6 hours ago

### Motorola/Google s Tech Development Strategy Starts to Emerge

• Reuters | 7 hours ago

### Singapore's Air Turns 'Hazardous' as Indonesian Fires Rage

• Expeditions | 7 hours ago

### Okinawa and the U.S. military, post 1945

• Features | 8 hours ago

## Scientific American Editors

Tweets could not be retrieved at this time

## Latest from SA Blog Network

• ### Canopy Meg: Fancy Title, But Does She Still Have Authority?

Context and Variation | 4 hours ago
• ### Weird Frog Discovered by Charles Darwin May be Extinct

Extinction Countdown | 4 hours ago
• ### A look at the Rube Goldberg contraptions that sort our recyclables

Plugged In | 5 hours ago
• ### Addicts as Parents, Part I: Pregnant, Now What?

MIND
The White Noise | 5 hours ago
• ### Banana-Peel Plastic, Wastewater Fuel Cell, Body-Heat Flashlight: Meet the Science in Action Finalists, Part I

STAFF
@ScientificAmerican | 6 hours ago

## Science Jobs of the Week

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

X

Get Both Print & Tablet Editions for one low price!

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