More than fifteen years ago, I was faced with the following problem in an assignment for a class in computer science. A brewery had to deliver beer to five stores, and the task was to write a computer program for determining the shortest route for the truck driver to visit all stores and return to the brewery. All my attemps to find a reasonable algorithm failed, I could not help enumerating all possible routes and then select the best one.

Frustrated at that point, I learnt later that there was no fast algorithm for solving this problem. Moreover, I found that this problem was well known as the traveling salesman problem and that there existed a host of published work on finding solutions. Though no efficient algorithm was developed, there was a tremendous progress in designing fast approximate solutions and even in solving ever larger problem instances to optimality. I started some work on the traveling salesman problem several years ago, first just writing demos for student classes, but then trying to find good and better solutions more effectively. I experienced the fascination of problem solving that, I think, everyone studying the traveling salesman problem will experience. In addition, I found that the problem has relevance in practice and that there is need for fast algorithms.

The present monograph documents my experiments with algorithms for finding good approximate solutions to practical traveling salesman problems. The work presented here profited from discussions and meetings with several people, among them Thomas Christof, Meinrad Funke, Martin Gr¨otschel, Michael J¨unger, Manfred Padberg, Giovanni Rinaldi, and Stefan Thienel, not naming dozens of further international researchers.

It is the aim of this text to serve as a guide for practitioners, but also to show that the work on the traveling salesman problem is not at all finished. The TSP will stimulate further efforts and continue to serve as the classical benchmark problem for algorithmic ideas.