The traveling salesman problem is one of the hard problems of algorithmic mathematics. The Clay Mathematics Institute includes the general version, P vs NP, as one of the seven problems for the solution of which it offers a $1,000,000 prize. And yet it is easy to state and understand: A salesman wants to find the least expensive route that visits each city once and returns to the starting point. There are so many possible routes that computing the cost of each is impractical unless the number of cities is small.
In this book William J. Cook surveys the traveling salesman problem for the interested lay reader. He does state in the preface that “A primary goal of the book is to stimulate readers to pursue their own ideas for the solution of this mathematical challenge,” however this quite optimistic. Another book The Traveling Salesman Problem: A Computational Study, of which Cook is a coauthor, has much more mathematical content and so would be more appropriate for serious study of the problem.
This book does aim to take the reader on a path to current theory. It includes interesting historical information about the problem, the people that worked on it, and the techniques used. There are a number of color photos and pictures and many figures and diagrams, but (as befitting a survey) no exercises. Chapter 1 sets the scene, describing the challenges. Chapter 2 shows the origins of the problem, including salesman routes developed before mathematics was applied. Mathematical approaches go back to Euler and Hamilton. Chapter 3 discusses applications, including mapping genomes, aiming telescopes, finding planets, customizing computer chips, speeding up video games, and testing microprocessors.
Chapters 4 to 7 form the core of the technical treatment. Finding the optimal route may be impractical but many approaches get close. Chapter 4 treats the nearest neighbor and greedy algorithms, continues with Christofides’ algorithm and then Lin-Kernighan and Lin-Kernighan-Helsgaun. These are put in the larger context of local search and hill climbing, simulated annealing, chained local optimization, genetic algorithms, and ant colony optimization.
The linear programming approach begins in Chapter 5, which includes a simple example of the simplex algorithm with pivoting. It shows how adding control zones and eliminating subtours can improve the solution. For larger problems the cutting planes method in Chapter 6 and the branch-and-bound tools of Chapter 7 enable state-of-the-art solutions. One gets the idea of these methods with diagrams but without mathematical details. The author provides an iPhone and iPad app, Concorde TSP, which provides optimal solutions. For example an optimal tour of 500 random cities takes about four and a half minutes to find.
The remaining chapters add interesting topics. Chapter 8 looks at the records produced by computing. Chapter 9 treats complexity and the $1,000,000 question of the inherent difficulty of the traveling salesman and similar problems. Chapter 10 show what humans without computers have done regarding the problem, while Chapter 11 illustrates the artistic connections of the problem. The book concludes with encouragement to pursue a solution. Readers will get the flavor of and insight into a fascinating problem — even if they don’t win the million dollars.
Art Gittleman (firstname.lastname@example.org) is Professor of Computer Science at California State University Long Beach.