The Traveling Salesman Problem: A Computational Study available in Hardcover, eBook
The Traveling Salesman Problem: A Computational Study
- ISBN-10:
- 0691129932
- ISBN-13:
- 9780691129938
- Pub. Date:
- 02/04/2007
- Publisher:
- Princeton University Press
- ISBN-10:
- 0691129932
- ISBN-13:
- 9780691129938
- Pub. Date:
- 02/04/2007
- Publisher:
- Princeton University Press
The Traveling Salesman Problem: A Computational Study
Buy New
$105.00Buy Used
-
-
SHIP THIS ITEM
Temporarily Out of Stock Online
Please check back later for updated availability.
-
Overview
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 problem—how it developed, and why it continues to intrigue us.
Product Details
| ISBN-13: | 9780691129938 |
|---|---|
| Publisher: | Princeton University Press |
| Publication date: | 02/04/2007 |
| Series: | Princeton Series in Applied Mathematics , #17 |
| Edition description: | New Edition |
| Pages: | 608 |
| Product dimensions: | 6.00(w) x 9.25(h) x (d) |
| Age Range: | 18 Years |
About the Author
Read an Excerpt
The Traveling Salesman Problem
A Computational StudyBy David L. Applegate Robert E. Bixby Vasek Chvátal William J. Cook
Princeton University Press
Copyright © 2007 Princeton University PressAll right reserved.
Chapter One
The 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 [183] 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 [527].
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)" [483], 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 [506]. 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 [410]. The title page of this small book is shown in Figure 1.1.
The Commis-Voyageur [132] 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 [495] 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 [495] 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 [506] and Friedman [196] describe how salesmen in the late 1800s used guidebooks, such as L. P. Brockett's [95] 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 [506] 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.
Circuit Riders
In its coverage of the historical usage of the word "circuit," the Oxford English Dictionary [443] 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 [194] 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 [57].
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 [248] 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 [550] 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.
Knight's Tour
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 [169] 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 [413] 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 [319] 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 [285].
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 [262], and Thomas Cook brought touring to the masses with his low- cost excursions in the mid-1800s [464]. The Oxford English Dictionary [443] 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 [528] 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.
Messengers
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 [389]. 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.
(Continues...)
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.
Table of Contents
Preface xi
Chapter 1: The Problem 11.1 Traveling Salesman 11.2 Other Travelers 51.3 Geometry 151.4 Human Solution of the TSP 311.5 Engine of Discovery 401.6 Is the TSP Hard? 441.7 Milestones in TSP Computation 501.8 Outline of the Book 56
Chapter 2: Applications 592.1 Logistics 592.2 Genome Sequencing 632.3 Scan Chains 672.4 Drilling Problems 692.5 Aiming Telescopes and X-Rays 752.6 Data Clustering 772.7 Various Applications 78
Chapter 3: Dantzig, Fulkerson, and Johnson 813.1 The 49-City Problem 813.2 The Cutting-Plane Method 893.3 Primal Approach 91
Chapter 4: History of TSP Computation 934.1 Branch-and-Bound Method 944.2 Dynamic Programming 1014.3 Gomory Cuts 1024.4 The Lin-Kernighan Heuristic 1034.5 TSP Cuts 1064.6 Branch-and-Cut Method 1174.7 Notes 125
Chapter 5: LP Bounds and Cutting Planes 1295.1 Graphs and Vectors 1295.2 Linear Programming 1315.3 Outline of the Cutting-Plane Method 1375.4 Valid LP Bounds 1395.5 Facet-Inducing Inequalities 1425.6 The Template Paradigm for Finding Cuts 1455.7 Branch-and-Cut Method 1485.8 Hypergraph Inequalities 1515.9 Safe Shrinking 1535.10 Alternative Calls to Separation Routines 156
Chapter 6: Subtour Cuts and PQ-Trees 1596.1 Parametric Connectivity 1596.2 Shrinking Heuristic 1646.3 Subtour Cuts from Tour Intervals 1646.4 Padberg-Rinaldi Exact Separation Procedure 1706.5 Storing Tight Sets in PQ-trees 173
Chapter 7: Cuts from Blossoms and Blocks 1857.1 Fast Blossoms 1857.2 Blocks of G1/2 1877.3 Exact Separation of Blossoms 1917.4 Shrinking 194
Chapter 8: Combs from Consecutive Ones 1998.1 Implementation of Phase 2 2028.2 Proof of the Consecutive Ones Theorem 210
Chapter 9: Combs from Dominoes 2219.1 Pulling Teeth from PQ-trees 2239.2 Nonrepresentable Solutions also Yield Cuts 2299.3 Domino-Parity Inequalities 231
Chapter 10: Cut Metamorphoses 24110.1 Tighten 24310.2 Teething 24810.3 Naddef-Thienel Separation Algorithms 25610.4 Gluing 261
Chapter 11: Local Cuts 27111.1 An Overview 27111.2 Making Choices of V and σ 27211.3 Revisionist Policies 27411.4 Does φ(χ*) Lie Outside the Convex Hull of T? 27511.5 Separating φ(χ*) from T : The Three Phases 28911.6 PHASE 1: From T* to T" 29111.7 PHASE 2: From T" to T' 31511.8 Implementing ORACLE 32611.9 PHASE 3: From T' to T 32911.10 Generalizations 339
Chapter 12: Managing the Linear Programming Problems 34512.1 The Core LP 34512.2 Cut Storage 35412.3 Edge Pricing 36212.4 The Mechanics 367
Chapter 13: The Linear Programming Solver 37313.1 History 37313.2 The Primal Simplex Algorithm 37813.3 The Dual Simplex Algorithm 38413.4 Computational Results: The LP Test Sets 39013.5 Pricing 404
Chapter 14: Branching 41114.1 Previous Work 41114.2 Implementing Branch and Cut 41314.3 Strong Branching 41514.4 Tentative Branching 417
Chapter 15: Tour Finding 42515.1 Lin-Kernighan 42515.2 Flipper Routines 43615.3 Engineering Lin-Kernighan 44915.4 Chained Lin-Kernighan on TSPLIB Instances 45815.5 Helsgaun's LKH Algorithm 46615.6 Tour Merging 469
Chapter 16: Computation 48916.1 The Concorde Code 48916.2 Random Euclidean Instances 49316.3 The TSPLIB 50016.4 Very Large Instances 50616.5 The World TSP 524
Chapter 17: The Road Goes On 53117.1 Cutting Planes 53117.2 Tour Heuristics 53417.3 Decomposition Methods 539
Bibliography 541Index 583
What People are Saying About This
This book addresses one of the most famous and important combinatorial-optimization problems—the traveling salesman problem. It is very well written, with a vivid style that captures the reader's attention. Many examples are provided that are very useful to motivate and help the reader to better understand the results presented in the book.
— Matteo Fischetti, University of Padova
"This book addresses one of the most famous and important combinatorial-optimization problems—the traveling salesman problem. It is very well written, with a vivid style that captures the reader's attention. Many examples are provided that are very useful to motivate and help the reader to better understand the results presented in the book."—Matteo Fischetti, University of Padova"This is a fantastic book. Ever since the early days of discrete optimization, the traveling salesman problem has served as the model for computationally hard problems. The authors are main players in this area who forged a team in 1988 to push the frontiers on how good we are in solving hard and large traveling salesman problems. Now they lay out their views, experience, and findings in this book."—Bert Gerards, Centrum voor Wiskunde en Informatica
This is a fantastic book. Ever since the early days of discrete optimization, the traveling salesman problem has served as the model for computationally hard problems. The authors are main players in this area who forged a team in 1988 to push the frontiers on how good we are in solving hard and large traveling salesman problems. Now they lay out their views, experience, and findings in this book.
— Bert Gerards, Centrum voor Wiskunde en Informatica