×

The traveling salesman problem and its variations. (English) Zbl 0996.00026

Combinatorial Optimization. 12. Dordrecht: Kluwer Academic Publishers. xviii, 830 p. (2002).

Show indexed articles as search result.

Table of contents: Contents: Abraham P. Punnen, The traveling salesman problem: applications, formulations and variations (1–28); Denis Naddef, Polyhedral theory and branch-and-cut-algorithms for the symmetric TSP (29–116); Egon Balas and Matteo Fischetti, Polyhedral theory for the asymmetric traveling salesman problem (117–168); Matteo Fischetti, Andrea Lodi and Paolo Toth, Exact methods for the asymmetric traveling salesman problem (169–205); Sanjeev Arora, Approximation algorithms for geometric TSP (207–221); Gregory Gutin, Anders Yeo and Alexei Zverovitch, Exponential neighborhoods and domination analysis for the TSP (223–256); A. M. Frieze and J. E. Yukich, Probabilistic analysis of the TSP (257–307); César Rego and Fred Glover, Local search and metaheuristics (309–368); David S. Johnson and Lyle A. McGeoch, Experimental analysis of heuristics for the STSP (369–443); David S. Johnson, Gregory Gutin, Lyle A. McGeoch, Anders Yeo, Weixiong Zhang and Alexei Zverovitch, Experimental analysis of heuristics for the ATSP (445–487); Santosh N. Kabadi, Polynomially solvable cases of the TSP (489–583); Alexander Barvinok, Edward Kh. Gimadi and Anatoliy I. Serdyukov, The maximum TSP (585–607); Matteo Fischetti, Juan-José Salazar-González and Paolo Toth, The generalized traveling salesman and orienteering problems (609–662); Egon Balas, The prize collecting traveling salesman problem and its applications (663–695); Santosh N. Kabadi and Abraham P. Punnen, The bottleneck TSP (697–735); Andrea Lodi and Abraham P. Punnen, TSP software (737–749); Gregory Gutin, Appendix: A. Sets, graphs and permutations (750–753); Abraham P. Punnen, Appendix: B. Computational complexity (754–760); References (761–806); List of figures; List of tables; Index.
From the preface: The traveling salesman problem (TSP) is perhaps one of the best known among the so-called NP-complete problems in combinatorial optimization. It is easy to explain to ”the man in the street” and yet typical for a large class of computational problems that are currently not quite well understood.
The TSP is quite easy to solve reasonably well for all practical purposes. The computational challenge lies in the determination of the exact optimum. For some time, it was suggested that special structural insights into the computational structure of the TSP might directly yield similar computational procedures for other NP-complete problems as well. This turned out to be not quite the case: the computational equivalence of NP-completeness appears to be more of theoretical than practical nature and, with respect to the design of exact algorithms, each NP-complete problem seems to ask for its own structural analysis.
Nevertheless a fundamental canon of computational techniques for NP-complete problems has developed: Try to find an (at least partial) description of the polytope generated by the feasible solutions in terms of cutting planes and use linear programming. Combine this approach with heuristics, branch-and-bound strategies and relaxation techniques. So the book Lawler, E.L.(ed.) et al., ‘The traveling salesman problem. A guided tour of combinatorial optimization. [Chichester: Wiley (1985; Zbl 0562.00014)] became quickly well known as it collected separate chapters on the state-of-the-art of the TSP into a general introduction to fundamental techniques of discrete optimization, exemplified with the TSP.
The fundamental techniques have, to a large extent, stayed the same during the last two decades. However, many new special results have been added to the literature. The present book presents a current state-of-the-art on the TSP in 16 individual chapters. The approach is basically the same as that of [op. cit]. The list of topics, however, is considerably expanded.
With respect to the classical TSP, one now finds a chapter on approximation algorithms and an extensive probabilistic analysis of the TSP. The list of polynomially solvable special subclasses of the TSP has grown. The volume also includes more discussions of closely related combinatorial optimization problems (e.g., the acyclic TSP, generalized TSP, prize collection TSP) and special types of objective functions (maximum TSP, bottleneck TSP). Furthermore, the currently relevant TSP software is described.
In summary, the book offers a comprehensive (and very readable) introduction to the TSP and leads the reader to the current state-of-the-art on that problem. I would consider it a must for every researcher who is planning to engage him/herself in this special field of research. As an introduction to discrete optimization in general, however, the volume appears so clearly focussed on the TSP that one might want to complement it by more general literature.
The articles of this volume will not be indexed individually.

MSC:

90C27 Combinatorial optimization
00B15 Collections of articles of miscellaneous specific interest
90-06 Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming
90Cxx Mathematical programming

Citations:

Zbl 0562.00014

Software:

TSP software
PDFBibTeX XMLCite