The Traveling Salesman Problem: A Computational Studyby David L. Applegate
This book presents the latest findings on one of the most intensely investigated subjects in computational mathematicsthe traveling salesman problem. It sounds simple enough: given a set of cities and the cost of travel between each pair of them, the problem challenges you to find the cheapest route by which to visit all the cities and return home to… See more details below
This book presents the latest findings on one of the most intensely investigated subjects in computational mathematicsthe traveling salesman problem. It sounds simple enough: given a set of cities and the cost of travel between each pair of them, the problem challenges you to find the cheapest route by which to visit all the cities and return home to where you began. Though seemingly modest, this exercise has inspired studies by mathematicians, chemists, and physicists. Teachers use it in the classroom. It has practical applications in genetics, telecommunications, and neuroscience.
The authors of this book are the same pioneers who for nearly two decades have led the investigation into the traveling salesman problem. They have derived solutions to almost eighty-six thousand cities, yet a general solution to the problem has yet to be discovered. Here they describe the method and computer code they used to solve a broad range of large-scale problems, and along the way they demonstrate the interplay of applied mathematics with increasingly powerful computing platforms. They also give the fascinating history of the problemhow it developed, and why it continues to intrigue us.
Jan Karel Lenstra
It is very well written and clearly structured. Many examples are provided, which help the reader to better understand the presented results. The authors succeed in describing the TSP problem, beginning with its history, and the first approaches, and ending with the state of the art.
"The authors have done a wonderful job of explaining how they developed new techniques in response to the challenges posed by ever larger instances of the Traveling Salesman Problem."MAA Online
"By bringing together the best work from a wide array of researchers, advancing the field where needed, describing their findings in a book, and implementing everything in an extremely well-written computer program, the authors show how research in computational combinatorial optimization should be done."Michael Trick, Operations Research Letters
"The book is certainly a must for every researcher in practical TSP-computation."Ulrich Faigle,Mathematical Reviews
"It is very well written and clearly structured. Many examples are provided, which help the reader to better understand the presented results. The authors succeed in describing the TSP problem, beginning with its history, and the first approaches, and ending with the state of the art."Stefan Nickel, Zentralblatt MATH
"[T]the text read[s] more like a best-seller than a tome of mathematics. . . . The resulting book provides not only a map for understanding TSP computation, but should be the starting point for anyone interested in launching a computational assault on any combinatorial optimization problem."Jan Karel Lenstra, SIAM Review
"By bringing together the best work from a wide array of researchers, advancing the field where needed, describing their findings in a book, and implementing everything in an extremely well-written computer program, the authors show how research in computational combinatorial optimization should be done."Michael Trick, ScienceDirect
"[T]he book provides a comprehensive treatment of the traveling salesman problem and I highly recommend it not only to specialists in the area but to anyone interested in combinatorial optimization."EMS Newsletter
Read an Excerpt
The Traveling Salesman ProblemA Computational Study
By David L. Applegate Robert E. Bixby Vasek Chvátal William J. Cook
Princeton University PressCopyright © 2007 Princeton University Press
All right reserved.
Chapter OneThe Problem
Given a set of cities along with the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all the cities and returning to the starting point. The "way of visiting all the cities" is simply the order in which the cities are visited; the ordering is called a tour or circuit through the cities.
This modest-sounding exercise is in fact one of the most intensely investigated problems in computational mathematics. It has inspired studies by mathematicians, computer scientists, chemists, physicists, psychologists, and a host of nonprofessional researchers. Educators use the TSP to introduce discrete mathematics in elementary, middle, and high schools, as well as in universities and professional schools. The TSP has seen applications in the areas of logistics, genetics, manufacturing, telecommunications, and neuroscience, to name just a few.
The appeal of the TSP has lifted it to one of the few contemporary problems in mathematics to become part of the popular culture. Its snappy name has surely played a role, but the primary reason for the wide interest is the fact that this easily understood model still eludes a general solution. Thesimplicity of the TSP, coupled with its apparent intractability, makes it an ideal platform for developing ideas and techniques to attack computational problems in general.
Our primary concern in this book is to describe a method and computer code that have succeeded in solving a wide range of large-scale instances of the TSP. Along the way we cover the interplay of applied mathematics and increasingly more powerful computing platforms, using the solution of the TSP as a general model in computational science.
A companion to the book is the computer code itself, called Concorde. The theory and algorithms behind Concorde will be described in detail in the book, along with computational tests of the code. The software is freely available at www.tsp.gatech.edu together with supporting documentation. This is jumping ahead in our presentation, however. Before studying Concorde we take a look at the history of the TSP and discuss some of the factors driving the continued interest in solution methods for the problem.
1.1 TRAVELING SALESMAN
The origin of the name "traveling salesman problem" is a bit of a mystery. There does not appear to be any authoritative documentation pointing out the creator of the name, and we have no good guesses as to when it first came into use. One of the most influential early TSP researchers was Merrill Flood of Princeton University and the RAND Corporation. In an interview covering the Princeton mathematics community, Flood  made the following comment.
Developments that started in the 1930s at Princeton have interesting consequences later. For example, Koopmans first became interested in the "48 States Problem" of Hassler Whitney when he was with me in the Princeton Surveys, as I tried to solve the problem in connection with the work of Bob Singleton and me on school bus routing for the State of West Virginia. I don't know who coined the peppier name "Traveling Salesman Problem" for Whitney's problem, but that name certainly caught on, and the problem has turned out to be of very fundamental importance.
This interview of Flood took place in 1984 with Albert Tucker posing the questions. Tucker himself was on the scene of the early TSP work at Princeton, and he made the following comment in a 1983 letter to David Shmoys .
The name of the TSP is clearly colloquial American. It may have been invented by Whitney. I have no alternative suggestion.
Except for small variations in spelling and punctuation, "traveling" versus "travelling," "salesman" versus "salesman's," etc., by the mid-1950s the TSP name was in wide use. The first reference containing the term appears to be the 1949 report by Julia Robinson, "On the Hamiltonian game (a traveling salesman problem)" , but it seems clear from the writing that she was not introducing the name. All we can conclude is that sometime during the 1930s or 1940s, most likely at Princeton, the TSP took on its name, and mathematicians began to study the problem in earnest.
Although we cannot identify the originator of the TSP name, it is easy to make an argument that it is a fitting identifier for the problem of finding the shortest route through cities in a given region. The traveling salesman has long captured our imagination, being a leading figure in stories, books, plays, and songs. A beautiful historical account of the growth and influence of traveling salesmen can be found in Timothy Spears' book 100 Years on the Road: The Traveling Salesman in American Culture . Spears cites an 1883 estimate by Commercial Travelers Magazine of 200,000 traveling salesmen working in the United States and a further estimate of 350,000 by the turn of the century. This number continued to grow through the early 1900s, and at the time of the Princeton research the salesman was a familiar site in most American towns and villages.
The 1832 Handbook by the alten Commis-Voyageur
The numerous salesmen on the road were indeed interested in the planning of economical routes through their customer areas. An important reference in this context is the 1832 German handbook Der Handlungsreisende-wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiss zu sein-Von einem alten Commis-Voyageur, first brought to the attention of the TSP research community in 1983 by Heiner Müller- Merbach . The title page of this small book is shown in Figure 1.1.
The Commis-Voyageur  explicitly described the need for good tours in the following passage, translated from the German original by Linda Cook.
Business leads the traveling salesman here and there, and there is not a good tour for all occurring cases; but through an expedient choice and division of the tour so much time can be won that we feel compelled to give guidelines about this. Everyone should use as much of the advice as he thinks useful for his application. We believe we can ensure as much that it will not be possible to plan the tours through Germany in consideration of the distances and the traveling back and fourth, which deserves the traveler's special attention, with more economy. The main thing to remember is always to visit as many localities as possible without having to touch them twice.
This is an explicit description of the TSP, made by a traveling salesman himself!
The book includes five routes through regions of Germany and Switzerland. Four of these routes include return visits to an earlier city that serves as a base for that part of the trip. The fifth route, however, is indeed a traveling salesman tour, as described in Alexander Schrijver's  book on the field of combinatorial optimization. An illustration of the tour is given in Figure 1.2. The cities, in tour order, are listed in Table 1.1, and a picture locating the tour within Germany is given in Figure 1.3. One can see from the drawings that the tour is of very good quality, and Schrijver  comments that it may in fact be optimal, given the local travel conditions at that time.
The Commis-Voyageur was not alone in considering carefully planned tours. Spears  and Friedman  describe how salesmen in the late 1800s used guidebooks, such as L. P. Brockett's  Commercial Traveller's Guide Book, to map out routes through their regions. The board game Commercial Traveller created by McLoughlin Brothers in 1890 emphasized this point, asking players to build their own tours through an indicated rail system. Historian Pamela Walker Laird kindly provided the photograph of the McLoughlin Brothers' game that is displayed in Figure 1.4.
The mode of travel used by salesmen varied over the years, from horseback and stagecoach to trains and automobiles. In each of these cases, the planning of routes would often take into consideration factors other than simply the distance between the cities, but devising good TSP tours was a regular practice for the salesman on the road.
1.2 OTHER TRAVELERS
Although traveling salesmen are no longer a common sight, the many flavors of the TSP have a good chance of catching some aspect of the everyday experience of most people. The usual errand run around town is a TSP on a small scale, and longer trips taken by bus drivers, delivery vans, and traveling tourists often involve a TSP through modest numbers of locations. For the many non-salesmen of the world, these natural connections to tour finding add to the interest of the TSP as a subject of study.
Spears  makes a strong case for the prominence of the traveling salesman in recent history, but a number of other tour finders could rightly lay claim to the TSP moniker, and we discuss below some of these alternative salesmen. The goal here is to establish a basis to argue that the TSP is a naturally occurring mathematical problem by showing a wide range of originating examples.
In its coverage of the historical usage of the word "circuit," the Oxford English Dictionary  cites examples as far back as the fifteenth century, concerning the formation of judicial districts in the United Kingdom. During this time traveling judges and lawyers served the districts by riding a circuit of the principal population centers, where court was held during specified times of the year. This practice was later adopted in the United States, where regional courts are still referred to as circuit courts, even though traveling is no longer part of their mission.
The best-known circuit-riding lawyer in the history of the United States is the young Abraham Lincoln, who practiced law before becoming the country's sixteenth president. Lincoln worked in the Eighth Judicial Circuit in the state of Illinois, covering 14 county courthouses. His travel is described by Guy Fraker  in the following passage.
Each spring and fall, court was held in consecutive weeks in each of the 14 counties, a week or less in each. The exception was Springfield, the state capital and the seat of Sangamon County. The fall term opened there for a period of two weeks. Then the lawyers traveled the fifty-five miles to Pekin, which replaced Tremont as the Tazewell County seat in 1850. After a week, they traveled the thirty-five miles to Metamora, where they spent three days. The next stop, thirty miles to the southeast, was Bloomington, the second-largest town in the circuit. Because of its size, it would generate more business, so they would probably stay there several days longer. From there they would travel to Mt. Pulaski, seat of Logan County, a distance of thirty-five miles; it had replaced Postville as county seat in 1848 and would soon lose out to the new city of Lincoln, to be named for one of the men in this entourage. The travelers would then continue to another county and then another and another until they had completed the entire circuit, taking a total of eleven weeks and traveling a distance of more than four hundred miles.
Fraker writes that Lincoln was one of the few court officials who regularly rode the entire circuit. A drawing of the route used by Lincoln and company in 1850 is given in Figure 1.5. Although the tour is not a shortest possible one (at least as the crow flies), it is clear that it was constructed with an eye toward minimizing the travel of the court personnel. The quality of Lincoln's tour was pointed out several years ago in a TSP article by Jon Bentley .
Lincoln has drawn much attention to circuit-riding judges and lawyers, but as a group they are rivaled in fame by the circuit-riding Christian preachers of the eighteenth and nineteenth centuries. John Hampson  wrote the following passage in his 1791 biography of John Wesley, the founder of the Methodist church.
Every part of Britain and America is divided into regular portions, called circuits; and each circuit, containing twenty or thirty places, is supplied by a certain number of travelling preachers, from two to three or four, who go around it in a month or six weeks.
The difficult conditions under which these men traveled is part of the folklore in Britain, Canada, and the United States. An illustration by Alfred R. Waud  of a traveling preacher is given in Figure 1.6. This drawing appeared on the cover of Harper's Weekly in 1867; it depicts a scene that appears in many other pictures and sketches from that period.
If mathematicians had begun their study of the TSP some hundred years earlier, it may well have been that circuit-riding lawyers or preachers would be the users that gave the problem its name.
One of the first appearances of tours and circuits in the mathematical literature is in a 1757 paper by the great Leonhard Euler. The Euler Archive  cites an estimate by historian Clifford Truesdell that "in a listing of all of the mathematics, physics, mechanics, astronomy, and navigation work produced during the 18th Century, a full 25% would have been written by Leonhard Euler." The particular paper we mention concerns a solution of the knight's tour problem in chess, that is, the problem of finding a sequence of knight's moves that will take the piece from a starting square on a chessboard, through every other square exactly once and returning to the start. Euler's solution is depicted in Figure 1.7, where the order of moves is indicated by the numbers on the squares.
The chess historian Harold J. Murray  reports that variants of the knight's tour problem were considered as far back as the ninth century in the Arabic literature. Despite the 1,200 years of work, the problem continues to attract attention today. Computer scientist Donald Knuth  is one of the many people who have recently considered touring knights, including the study of generalized knights that can leap x squares up and y squares over, and the design of a font for typesetting tours. An excellent survey of the numerous current attacks on the problem can be found on George Jellis' web page Knight's Tour Notes .
The knight's problem can be formulated as a TSP by specifying the cost of travel between squares that can be reached via a legal knight's move as 0 and the cost of travel between any two other squares as 1. The challenge is then to find a tour of cost 0 through the 64 squares. Through this view the knight's problem can be seen as a precursor to the TSP.
The Grand Tour
Tourists could easily argue for top billing in the TSP; traveling through a region in a limited amount of time has been their specialty for centuries. In the 1700s taking a Grand Tour of Europe was a rite of passage for the British upper class , and Thomas Cook brought touring to the masses with his low- cost excursions in the mid-1800s . The Oxford English Dictionary  defines Cook's tour as "a tour, esp. one in which many places are viewed," and Cook is often credited with the founding of the modern tourism industry.
Mark Twain's The Innocents Abroad  gives an account of the author's passage on a Grand Tour organized by a steamship firm; this collection of stories was Twain's best-selling book during his lifetime. His tour included stops in Paris, Venice, Florence, Athens, Odessa, Smyrna, Jerusalem, and Malta, in a route that appears to minimize the travel time. A rough sketch of Twain's tour is given in Figure 1.8.
In the mathematics literature, it appears that the first mention of the TSP was made by Karl Menger, who described a variant of the problem in notes from a mathematics colloquium held in Vienna on February 5, 1930 . A rough translation of Menger's problem from the German original is the following.
We use the term Botenproblem (because this question is faced in practice by every postman, and by the way also by many travelers) for the task, given a finite number of points with known pairwise distances, to find the shortest path connecting the points.
So the problem is to find only a path through the points, without a return trip to the starting point. This version is easily converted to a TSP by adding an additional point having travel distance 0 to each of the original points.
Bote is the German word for messenger, so with Menger's early proposal a case could be made for the use of the name messenger problem in place of TSP.
Excerpted from The Traveling Salesman Problem by David L. Applegate Robert E. Bixby Vasek Chvátal William J. Cook Copyright © 2007 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
What People are saying about this
Matteo Fischetti, University of Padova
Bert Gerards, Centrum voor Wiskunde en Informatica
and post it to your social network
Most Helpful Customer Reviews
See all customer reviews >