The Traveling Salesman Problem and Its Variations

Cover
G. Gutin, A.P. Punnen
Springer Science & Business Media, 02.05.2006 - 830 Seiten

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.

 

Inhalt

APPLICATIONS FORMULATIONS AND VARIATIONS
1
Chapter 2 POLYHEDRAL THEORY AND BRANCH ANDCUT ALGORITHMS FOR THE SYMMETRIC TSP
29
Chapter 3 POLYHEDRAL THEORY FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM
117
Chapter 4 EXACT METHODS FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM
169
Chapter 5 APPROXIMATION ALGORITHMS FOR GEOMETRIC TSP
207
Chapter 6 EXPONENTIAL NEIGHBORHOODS AND DOMINATION ANALYSIS FOR THE TSP
222
Chapter 7 PROBABILISTIC ANALYSIS OF THE TSP
257
Chapter 8 LOCAL SEARCH AND METAHEURISTICS
309
Chapter 13 THE GENERALIZED TRAVELING SALESMAN AND ORIENTEERING PROBLEMS
609
Chapter 14 THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM AND ITS APPLICATIONS
663
Chapter 15 THE BOTTLENECK TSP
696
Chapter 16 TSP SOFTWARE
737
A Sets Graphs and Permutations
750
B Computational Complexity
754
References
761
List of Figures
807

Chapter 9 EXPERIMENTAL ANALYSIS OF HEURISTICS FOR THE STSP
369
Chapter 10 EXPERIMENTAL ANALYSIS OF HEURISTICS FOR THE ATSP
444
Chapter 11 POLYNOMIALLY SOLVABLE CASES OF THE TSP
489
Chapter 12 THE MAXIMUM TSP
584
List of Tables
812
Topic Index
817
Urheberrecht

Andere Ausgaben - Alle anzeigen

Häufige Begriffe und Wortgruppen

Bibliografische Informationen