The traveling salesman problem (TSP) is to find the least expensive way to visit a collection of cities and return to the beginning. This simply stated problem combined with its seeming intractable solution has, over the past century, made the TSP the defining problem for computational optimization and even for computational science in general. While the TSP is now well-known in popular culture as well as in OR/MS, its history, the applications beyond the routing of itinerant vendors, and the variety of solution methodologies had not been assembled until now. Applegate, Bixby, Chvatal and Cook's book The Traveling Salesman Problem: A Computational Study combines the history, the applications and the most advanced methods for solution in a definitive treatment of this definitive problem.
In presenting solution methods, the book describes in clear and instructive terms how to build efficient procedures for the basic optimization mechanisms of linear programming, branch-and-bound, cutting planes, and iterative improvement. The authors then show how to combine these myriad processes into a powerful optimization machine capable of solving to optimality problems with tens of thousands of cities. They also provide challenges for improvements and sources for new directions to the TSP and other large combinatorial problems. To allow future researchers the chance to examine and build on their work directly, the authors have made publicly available their entire computer code.
Besides providing a comprehensive view of all that is involved in solving the TSP, the book's flowing narrative blends the pieces together in a steady progression that captivates the reader. In describing the latest applications, such as gene sequencing, data mining and X-ray crystallography, the book also shows the reach of OR/MS into multiple new domains. In all respects, The Traveling Salesman Problem: A Computational Study represents the best of OR/MS history, present, and future.
