| Preface | p. xi |
| Contributing Authors | p. xv |
| The Traveling Salesman Problem: Applications, Formulations and Variations | p. 1 |
| Introduction | p. 1 |
| Simple Variations of the TSP | p. 7 |
| Applications of TSP | p. 9 |
| Alternative representations of the TSP | p. 15 |
| Matrix Transformations | p. 23 |
| More Variations of the TSP | p. 24 |
| Polyhedral Theory and Branch-and-Cut Algorithms for the Symmetric TSP | p. 29 |
| Introduction | p. 29 |
| Integer linear programming models | p. 30 |
| STSP polytope and relaxations | p. 35 |
| The graphical relaxation Framework | p. 44 |
| The Comb inequalities | p. 58 |
| The Star and Path inequalities | p. 62 |
| The Clique Tree and Bipartition inequalities | p. 67 |
| The Ladder inequalities | p. 71 |
| A general approach to some TSP valid inequalities | p. 73 |
| A unifying family of inequalities | p. 77 |
| Domino inequalities | p. 78 |
| Other inequalities | p. 81 |
| The separation problem | p. 82 |
| Greedy heuristic for minimum cut | p. 84 |
| Graph associated to a vector x [isin] R[superscript E] | p. 85 |
| Heuristics for Comb Separation | p. 86 |
| Separation of multi-handle inequalities | p. 94 |
| Separation outside the template paradigm | p. 100 |
| Branch-and-Cut implementation of the STSP | p. 105 |
| Computational results | p. 113 |
| Conclusion | p. 114 |
| Polyhedral Theory for the Asymmetric Traveling Salesman Problem | p. 117 |
| Introduction | p. 117 |
| Basic ATS inequalities | p. 120 |
| The monotone ATS polytope | p. 128 |
| Facet-lifting procedures | p. 133 |
| Equivalence of inequalities and canonical forms | p. 142 |
| Odd closed alternating trail inequalities | p. 145 |
| Source-destination inequalities | p. 150 |
| Lifted cycle inequalities | p. 155 |
| Exact Methods for the Asymmetric Traveling Salesman Problem | p. 169 |
| Introduction | p. 169 |
| AP-Based Branch-and-Bound Methods | p. 172 |
| An Additive Branch-and-Bound Method | p. 176 |
| A Branch-and-Cut Approach | p. 181 |
| Computational Experiments | p. 194 |
| Approximation Algorithms for Geometric TSP | p. 207 |
| Background on Approximation | p. 208 |
| Introduction to the Algorithm | p. 209 |
| Simpler Algorithm | p. 214 |
| Better Algorithm | p. 215 |
| Faster Algorithm | p. 219 |
| Generalizations to other Problems | p. 220 |
| Exponential Neighborhoods and Domination Analysis for the TSP | p. 223 |
| Introduction, Terminology and Notation | p. 223 |
| Exponential Neighborhoods | p. 228 |
| Upper Bounds for Neighborhood Size | p. 237 |
| Diameters of Neighborhood Structure Digraphs | p. 240 |
| Domination Analysis | p. 244 |
| Further Research | p. 254 |
| Probabilistic Analysis of the TSP | p. 257 |
| Introduction | p. 257 |
| Hamiltonian Cycles in Random Graphs | p. 259 |
| Traveling Salesman Problem: Independent Model | p. 274 |
| Euclidean Traveling Salesman Problem | p. 282 |
| Local Search and Metaheuristics | p. 309 |
| Background on Heuristic Methods | p. 309 |
| Improvement Methods | p. 313 |
| Tabu Search | p. 345 |
| Recent Unconventional Evolutionary Methods | p. 355 |
| Conclusions and Research Opportunities | p. 367 |
| Experimental Analysis of Heuristics for the STSP | p. 369 |
| Introduction | p. 369 |
| DIMACS STSP Implementation Challenge | p. 371 |
| Heuristics and Results | p. 381 |
| Conclusions and Further Research | p. 438 |
| Experimental Analysis of Heuristics for the ATSP | p. 445 |
| Introduction | p. 446 |
| Methodology | p. 447 |
| Heuristics | p. 457 |
| Results | p. 463 |
| Conclusions and Further Research | p. 486 |
| Polynomially Solvable Cases of the TSP | p. 489 |
| Introduction | p. 489 |
| Constant TSP and its generalizations | p. 489 |
| The Gilmore-Gomory TSP (GG-TSP) | p. 494 |
| GG Scheme: a generalization of Gilmore-Gomory scheme for GG-TSP | p. 506 |
| Minimum cost connected directed pseudograph problem with node deficiency requirements (MCNDP) | p. 539 |
| Solvable cases of geometric TSP | p. 547 |
| Generalized graphical TSP | p. 560 |
| Solvable classes of TSP on specially structured graphs | p. 564 |
| Classes of TSP with known compact polyhedral representation | p. 566 |
| Other solvable cases and related results | p. 576 |
| The Maximum TSP | p. 585 |
| Introduction | p. 585 |
| Hardness Results | p. 588 |
| Preliminaries: Factors and Matchings | p. 589 |
| MAX TSP with General Non-Negative Weights | p. 590 |
| The Symmetric MAX TSP | p. 591 |
| The Semimetric MAX TSP | p. 595 |
| The Metric MAX TSP | p. 597 |
| TSP with Warehouses | p. 598 |
| MAX TSP in a Space with a Polyhedral Norm | p. 600 |
| MAX TSP in a Normed Space | p. 602 |
| Probabilistic Analysis of Heuristics | p. 605 |
| The Generalized Traveling Salesman and Orienteering Problems | p. 609 |
| Introduction | p. 609 |
| The Generalized Traveling Salesman Problem | p. 617 |
| The Orienteering Problem | p. 642 |
| The Prize Collecting Traveling Salesman Problem and Its Applications | p. 663 |
| Introduction | p. 663 |
| An Application | p. 664 |
| Polyhedral Considerations | p. 667 |
| Lifting the Facets of the ATS Polytope | p. 668 |
| Primitive Inequalities from the ATSP | p. 671 |
| Cloning and Clique Lifting for the PCTSP | p. 680 |
| A Projection: The Cycle Polytope | p. 686 |
| The Bottleneck TSP | p. 697 |
| Introduction | p. 697 |
| Exact Algorithms | p. 699 |
| Approximation Algorithms | p. 705 |
| Polynomially Solvable Cases of BTSP | p. 714 |
| Variations of the Bottleneck TSP | p. 734 |
| TSP Software | p. 737 |
| Introduction | p. 737 |
| Exact algorithms for TSP | p. 739 |
| Approximation Algorithms for TSP | p. 741 |
| Java Applets | p. 745 |
| Variations of the TSP | p. 745 |
| Other Related Problems and General-Purpose Codes | p. 747 |
| Sets, Graphs and Permutations | p. 750 |
| Sets | p. 750 |
| Graphs | p. 750 |
| Permutations | p. 753 |
| Computational Complexity | p. 754 |
| Introduction | p. 754 |
| Basic Complexity Results | p. 756 |
| Complexity and Approximation | p. 758 |
| References | p. 761 |
| List of Figures | p. 807 |
| List of Tables | p. 813 |
| Index | p. 817 |
| Table of Contents provided by Ingram. All Rights Reserved. |
