The Traveling Salesman Problem and Its VariationsG. 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
1 | |
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 |
817 | |
Andere Ausgaben - Alle anzeigen
The Traveling Salesman Problem and Its Variations G. Gutin,A.P. Punnen Eingeschränkte Leseprobe - 2002 |
The Traveling Salesman Problem and Its Variations G. Gutin,A.P. Punnen Keine Leseprobe verfügbar - 2002 |
The Traveling Salesman Problem and Its Variations G. Gutin,A.P. Punnen Keine Leseprobe verfügbar - 2002 |
Häufige Begriffe und Wortgruppen
algorithm arcs ATSP branch-and-cut BTSP Chapter cities classes clique tree closed walk Clustered coefficient comb inequalities complete graph computed consider constraints construction contains convex hull corresponding cost matrix defines a facet denote density matrix digraph domination number ejection chain Euclidean exists facet defining facet inducing Figure GG scheme given graph G Greedy Hamiltonian cycle Hamiltonian path Helsgaun hence heuristic implementation insertion integer iterations K-d trees Lemma lifting Lin-Kernighan linear local search lower bound method minimum neighborhood node set O(n² obtained optimal solution optimal tour partition patching path permutation polynomial polytope procedure programming proof pseudograph random satisfies Section sequence solvable solved spanning tree STSP STSPP(n subgraph subset subtour elimination symmetric tabu search Theorem tour length tour quality traveling salesman problem triangle inequality TSP(C TSPLIB instances undirected graph valid variables vector vertex vertices violated weight