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.