G. Gutin – The Traveling Salesman Problem and Its Variations

Автор: G. Gutin
Название книги: The Traveling Salesman Problem and Its Variations
Формат: PDF
Жанр: Математика
Страницы: 850
Качество: Изначально компьютерное, E-book

A brilliant treatment of a knotty problem in computing. This volume contains chapters written by reputable researchers and provides the state of the art in theory and algorithms for the traveling salesman problem (TSP). The book covers all important areas of study on TSP, including polyhedral theory for symmetric and asymmetric TSP, branch and bound, and branch and cut algorithms, probabilistic aspects of TSP, and includes a thorough computational analysis of heuristic and metaheuristic algorithms.

The traveling salesman problem (TSP) is perhaps the most well known
combinatorial optimization problem. The book “The Traveling Salesman
Problem: A guided tour of combinatorial optimization” edited by
Lawler, Lenstra, Rinooy Kan and Shmoys provides the state of the art
description of the topic up to 1985. Since then, several significant developments
have taken place in the area of combinatorial optimization in
general and the traveling salesman problem in particular. This warrants
the need for an updated book. We discussed this matter with many
distinguished colleagues. These consultations culminated in the project
of compiling a new book on the TSP. Enthusiastic support from the research
community provided us with the courage and motivation to take
up this challenging task.
The pattern and style of this new book closely resemble those of its
predecessor [548]. In addition to standard and more traditional topics,
we also cover domination analysis of approximation algorithms and some
important variations of the TSP. The purpose of the book is to serve
as a self-contained reference source which updates the book by Lawler
et. al [548]. We believe that the book can also be used for specialized
graduate and senior undergraduate courses and research projects.
Roughly speaking, the traveling salesman problem is to find a shortest
route of a traveling salesperson that starts at a home city, visits a
prescribed set of other cities and returns to the starting city. The distance
travelled in such a tour obviously depends on the order in which
the cities are visited and, thus, the problem is to find an ‘optimal’ ordering
of the cities. There are several applications of the TSP that extend
beyond the route planning of a traveling salesman. Chapter 1 describes
several formulations, applications, and variations of the problem.
As one can see, it does not take much mathematical sophistication
to understand many of the formulations of the TSP. However, TSP is a
typical ‘hard’ optimization problem and solving very large instances of
it is very difficult if not impossible. Nevertheless, recent developments in
polyhedral theory and branch-and-cut algorithms have significantly in creased the size of instances which can be solved to optimality. Chapters
2–4 provides a thorough description of polyhedral theory, and implementation
and testing of exact algorithms. Chapter 2 discusses polyhedral
theory and experimental results of branch-and-cut algorithms for the
symmetric TSP. Chapter 3 deals with polyhedral results for the asymmetric
TSP developed mostly in last 15 years. Chapter 4 deals with
implementation and testing of branch-and-bound and branch-and-cut
algorithms for the asymmetric version of the TSP.
Despite the fact that significant progress have been made in our ability
to solve TSP by exact algorithms, still there are several instances of the
problem to be solved to optimality, that are hard for exact algorithms.
Moreover, even when an instance is solvable by an exact algorithm, the
running time may become prohibitively large for certain applications. In
some cases, the problem data of the instance in hand may not be exact,
for various reasons, and thus solving such an instance to optimality may
not be viable, especially when it takes a significant amount of computational
time. Therefore, researchers have investigated a large number
of heuristic algorithms, some of which normally produce near optimal
solutions. Chapters 5–10 are devoted to various aspects of heuristic
algorithms for the TSP.
Chapter 5 presents a compact account on recent developments on approximation
algorithms for the geometric TSP in general and Euclidean
TSP in particular. Chapter 6 discusses very large, exponential, size
neighborhoods for the TSP and domination analysis, a new tool to compare
the quality of heuristics. Probabilistic approaches to the TSP are
studied in Chapter 7. Probabilistic approaches try to elucidate the properties
of typical rather than worst-case instances. Chapter 8 describes
well-established and new heuristic approaches to the symmetric TSP.
Chapter 9 provides results of extensive computational experiments with
numerous heuristic algorithms for the Symmetric TSP. Computational
experience with heuristics for the less well-studied Asymmetric TSP is
described in Chapter 10.
Chapter 11 is an extensive survey on polynomial time solvable cases of
the TSP. Chapters 12–15 are devoted to variations and generalizations of
the TSP. Interesting differences between the TSP and its maximization
version are described in Chapter 12, where several approximation algorithms
for the maximum TSP are presented. Chapter 13 deals with the
Generalized TSP and Orienteering Problem. Polyhedral results as well
as implementation of exact algorithms, are discussed in detail. The Prize
Collecting TSP, where the traveling salesperson needs to visit only part
of the prescribed set of cities as long as he/she collected enough “prize items, is the topic of Chapter 14. Chapter 15 considers the Bottleneck
TSP, where the largest inter-city distance along the route is minimized.
A summary of available TSP software is discussed in Chapter 16. This
chapter will be of particular interest to the readers looking for a “quick”
way to solve their TSP instances without getting deeply involved with
algorithmic ideas and coding techniques. The book has two appendices.
Appendix A is a short overview on graphs, sets and permutations for the
benefit of readers who want to refresh their knowledge on these topics.
Appendix B discusses complexity issues.
Our foremost thanks go to all authors for their enthusiasm and hard
work without which this book would not have been completed. Every
chapter of this book was read by several researchers who provided comments
and suggestions. We would like to thank, among others, Norbert
Ascheuer, Rafi Hassin, Gilbert Laporte. Adam Letchford, Francois Margot,
Pablo Moscato, K.G. Murty, K.P.K. Nair, Prabha Sharma, Mike
Steele, Stefan Voss, and Klaus Wenger for their valuable comments and
suggestions. Some of the authors, in particular, Matteo Fischetti, Alan
Frieze, Fred Glover, David Johnson, Santosh Kabadi, Andrea Lodi, Denis
Naddef, Cesar Rego, Paolo Toth, Anders Yeo and Alexei Zverovitch
also participated actively in refereeing chapters and our gratitude goes
to each one of them. We highly appreciate the help and support from our
publisher especially Gary Folven and Ramesh Sharda. Special thanks
are due to John Martindale, for persuading us to publish the book with
Kluwer and retaining his patience and optimism as one deadline after
another did not materialize.