The Traveling Salesman Problem. A Computational Study

The traveling salesman problem is probably one of the best known problems in combinatorial optimization: given a collection of cities, find the shortest round-trip route that visits each of the cities exactly once. Though simple to state, finding an optimal solution is far from trivial. The authors of the book have led investigations of the problem for almost two decades and this book presents their findings. The main aim of the book is to explain the theory and algorithms utilized in a computer code (called Concorde), which has successfully solved a number of large scale instances of the problem. Having said that, it must be stressed that programming skills are not prerequisites for reading the book and that the book is written in a readable style.

It opens with an overview of the rich history of the problem, complemented with many illustrations. Chapter 2 contains a description of the main applications of the traveling salesman problem. The next two chapters survey development in the 50s on the traveling salesman problem by Dantzig, Fulkerson and Johnson and later by Grötschel and Padberg. Development on the problem was closely bound up with development in linear programming, and the cutting plane method for linear programming is at the core of chapters 3 and 4. In chapters 5-11, the authors describe their own techniques for finding cutting planes for the problem; these techniques form the core of the Concorde code. This part of the book requires a solid background in linear programming but reading it carefully will pay off. The subject of chapters 12 and 13 is how to manage and solve the large linear programs derived by the techniques described in previous chapters. Chapters 14 and 15 deal with enumeration schemes and with heuristics complementing the cutting plane method. Finally, chapter 16 provides results of the computational tests with Concorde and chapter 17 concludes the book with a sketch of possible future research directions. To summarize, the book provides a comprehensive treatment of the travelling salesman problem and I highly recommend it not only to specialists in the area but to anyone interested in combinatorial optimization.

Reviewer: 
pkol
Book details
Categorisation