In the Procter & Gamble contest we can save effort by noting that the distance to travel between Chicago and Wichita is the same as the distance between Wichita and Chicago, and this is true also for every other pair of cities. With such symmetry it does not matter in which direction we travel around a tour, so an ordering
ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567
is the same as its reverse
7654321ZYXWVUTSRQPONMLKJIHGFEDCBA.
We can therefore cut down by half our count of the 33-city tours, leaving only 32!/2 orderings to check. Before you go ahead and get out your Ticonderoga #2 pencil, note that this is
131,565,418,466,846,765,083,609,006,080,000,000
distinct tours that we must examine. These days we would of course employ a computer to run through the list. So let’s choose a big one, the $133,000,000 IBM Roadrunner Cluster of the United States Department of Energy. This 129,600-core machine topped the 2009 ranking of the 500 world’s fastest supercomputers, delivering up to 1,457 trillion arithmetic operations per second. Let’s assume we can arrange the search for tours such that examining each new one requires only a single arithmetic operation. We would then need roughly 28 trillion years to solve the 33-city TSP on the Roadrunner, an uncomfortable amount of time, given that the universe is estimated to be only 14 billion years old. No wonder Menger was unsatisfied with the brute-force solution to the problem.
When considering the implications of this quick analysis, we must keep in mind that Menger writes only that faster rules for solving the salesman problem are unknown, not that such rules are out of the question. John Little and coauthors sum this up nicely in the following comment on the Procter & Gamble contest. “A number of people, perhaps a little over-educated, wrote the company that the problem was impossible—an interesting misinterpretation of the state of the art.” Little et al. went on to describe a breakthrough in TSP solution methods, but they could not push their computer codes far enough to actually solve the 33-city challenge. It appears that no one in the country was able to produce a route that could be guaranteed to be the shortest of all possible tours for Toody and Muldoon.
The 33-city problem was definitely a tough nut to crack, but if we turn back the clock to 1954, then we find a team that almost certainly would be able to deliver the optimal route, together with a written guarantee that their solution is the shortest. The team tackled a larger touring problem through the United States, visiting a city in each of the 48 states, as well as Washington, D.C. This particular challenge had been circulating through the mathematics community since the mid-1930s. Its solution was reported in Newsweek.
Finding the shortest route for a traveling salesman—starting from a given city, visiting each of a series of other cities, and then returning to his original point of departure—is more than an after-dinner teaser. For years it has baffled not only goods- and salesman-routing businessmen but mathematicians as well. If a drummer visits 50 cities, for example, he has 1062 (62 zeros) possible itineraries. No electronic computer in existence could sort out such a large number of routes and find the shortest.
Three Rand Corp. mathematicians, using Rand McNally road-map distances between the District of Columbia and major cities in each of the 48 states, have finally produced a solution. By an ingenious application of linear programming—a mathematical tool recently used to solve production-scheduling problems—it took only a few weeks for the California experts to calculate “by hand” the shortest route to cover the 49 cities: 12,345 miles.
The California experts were George Dantzig, Ray Fulkerson, and Selmer Johnson, part of an exceptionally strong and influential center for the new field of mathematical programming, housed at the RAND Corporation in Santa Monica.
See what we're tweeting about
4 Comments
Add CommentThis book is an overview of the best methods designed to solve TSP. It is recommended to everyone who wants to challenge this problem.
Reply | Report Abuse | Link to thisI wonder why the Authors keep their program (concorde) executable only on UNIX platforms?
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 thisWilliam - 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.
Reply | Report Abuse | Link to thisClaiming 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.
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