1 An Overview of Vehicle Routing Problems&P.Toth,D.Vigo 1
1.1 Introduction 1
1.2 Problem Definition and Basic Notation 5
1.2.1 Capacitated and Distance-Constrained VRP 5
1.2.2 VRP with Time Windows 8
1.2.3 VRP with Backhauls 9
1.2.4 VRP with Pickup and Delivery 10
1.3 Basic Models for the VRP 11
1.3.1 Vehicle Flow Models 11
1.3.2 Extensions of Vehicle Flow Models 17
1.3.3 Commodity Flow Models 19
1.3.4 Set-Partitioning Models 21
1.4 Test Instances for the CVRP and Other VRPs 22
Bibliography 23
Ⅰ Capacitated Vehicle Routing Problem 27
2 Branch-and-Bound Algorithms for the Capacitated VRP&P. Toth,D. Vigo 29
2.1 Introduction 29
2.2 Basic Relaxations 30
2.2.1 Bounds Based on Assignment and Matching 30
2.2.2 Bounds Based on Arborescencesand Trees 32
2.2.3 Comparison of the Basic Relaxations 33
2.3 Better Relaxations 35
2.3.1 Additive Bounds for ACVRP 35
2.3.2 Further Lower Bounds for ACVRP 39
2.3.3 Lagrangian Lower Bounds for SCVRP 40
2.3.4 Lower Bounds from a Set-Partitioning Formulation 41
2.3.5 Comparison of the Improved Lower Bounds 42
2.4 Structure of the Branch-and-Bound Algorithms for CVRP 44
2.4.1 Branching Schemes and Search Strategies 44
2.4.2 Reduction,Dominance Rules,and Other Features 46
2.4.3 Performance of the Branch-and-Bound Algorithms 47
2.5 Distance-Constrained VRP 48
Bibliography 49
3 Branch-and-Cut Algorithms for the Capacitated VRP&D. Naddef,G. Rinaldi 53
3.1 Introduction and Two-Index Flow Model 53
3.2 Branch-and-Cut 55
3.3 Polyhedral Studies 58
3.3.1 Capacity Constraints 59
3.3.2 Generalized Capacity Constraints 61
3.3.3 Framed Capacity Constraints 62
3.3.4 Valid Inequalities from STSP 62
3.3.5 Valid Inequalities Combining Bin Packing and STSP 67
3.3.6 Valid Inequalities from the Stable Set Problem 69
3.4 Separation Procedures 71
3.4.1 Exact Separation of Capacity Constraints 71
3.4.2 Heuristies for Capacity and Related Constraints 72
3.4.3 STSP Constraints 75
3.5 Branching Strategies 75
3.6 Computational Results 78
3.7 Conclusions 81
Bibliography 81
4 Set-Covering-Based Algorithms for the Capacitated VRP&J. Bramel,D.Simchi-Levi 85
4.1 Introduction 85
4.2 Solving the Linear Programming Relaxation of P 87
4.3 Set-Covering-Based Solution Methods 89
4.3.1 Branch-and-Bound Algorithm for Problem CG 89
4.3.2 Polyhedral Branch-and-Bound Algorithm 91
4.3.3 Pseudo-Polynomial Lower Bound on ？min 92
4.3.4 Solving PD via Dual-Ascent and Branch-and-Bound 94
4.4 Solving the Set-Covering Integer Program 96
4.4.1 A Cutting Plane Method 97
4.4.2 Branch-and-Price 99
4.4.3 Additional Comments on Computational Approaches 100
4.5 Computational Results 100
4.6 Effectiveness of the Set-Covering Formulation 102
4.6.1 Worst-Case Analysis 103
4.6.2 Average-Case Analysis 103
Bibliography 106
5 Classicai Heuristics for the Capacitated VRP&G. Laporte,F. Semet 109
5.1 Introduction 109
5.2 Constructive Methods 110
5.2.1 Clarke and Wright Savings Algorithm 110
5.2.2 Enhancements of the Clarke and Wright Algorithm 111
5.2.3 Matching-Based Savings Algorithms 113
5.2.4 Sequential Insertion Heuristics 114
5.3 Two-Phase Methods 116
5.3.1 Elementary Clustering Methods 116
5.3.2 Truncated Branch-and-Bound 118
5.3.3 Petal Algorithms 120
5.3.4 Route-First,Cluster-Second Methods 120
5.4 Improvement Heuristics 121
5.4.1 Single-Route Improvements 121
5.4.2 Multiroute Improvements 122
5.5 Conclusions 125
Bibliography 126
6 Metaheuristics for the Capacitated VRP&M. Gendreau,G. Laporte,J.-Y. Potvin 129
6.1 Introduction 129
6.2 Simulated Annealing 130
6.2.1 Two Early Simulated Annealing Algorithms 130
6.2.2 Osman's Simulated Annealing Algorithms 131
6.2.3 Van Breedam's Experiments 133
6.3 Deterministic Annealing 133
6.4 Tabu Search 134
6.4.1 Two Early Tabu Search Algorithms 134
6.4.2 Osman's Tabu Search Algorithm 134
6.4.3 Taburoute 135
6.4.4 Taillard's Algorithm 137
6.4.5 Xu and Kelly's Algorithm 137
6.4.6 Rego and Roucairol's Algorithms 137
6.4.7 Barbarosoglu and Ozgur's Algorithm 138
6.4.8 Adaptive Memory Procedure of Rochat and Taillard 138
6.4.9 Granular Tabu Search of Toth and Vigo 138
6.4.10 Computational Comparison 140
6.5 Genetic Algorithms 140
6.5.1 Simple Genetic Algorithm 140
6.5.2 Application to Sequencing Problems 141
6.5.3 Application to the VRP 142
6.6 Ant Algorithms 144
6.7 Neural Networks 146
6.8 Conclusions 148
Bibliography 149
Ⅱ Important Variants of the Vehicle Routing Problem 155
7 VRP with Time Windows&J.-F. Cordeau,G. Desaulniers,J. Desrosiers,M.M. Solomon,F. Soumis 157
7.1 Introduction 157
7.2 Problem Formulation 158
7.2.1 Formulation 158
7.2.2 Network Lower Bound 159
7.2.3 Linear Programming Lower Bound 159
7.2.4 Algorithms 160
7.3 Upper Bounds:Heuristic Approaches 160
7.3.1 Route Construction 160
7.3.2 Route Improvement 161
7.3.3 Composite Heuristics 161
7.3.4 Metaheuristics 162
7.3.5 Parallel Implementations 165
7.3.6 Optimization-Based Heuristics 165
7.3.7 Asymptotically Optimal Heuristics 165
7.4 Lower Bounds from Decomposition Approaches 166
7.4.1 Lagrangian Relaxation 166
7.4.2 Capacity and Time-Constrained Shortest-Path Problem 167
7.4.3 Variable Splitting 168
7.4.4 Column Generation 169
7.4.5 Set-Partitioning Formulation 169
7.4.6 Lower Bound 170
7.4.7 Commodity Aggregation 171
7.4.8 Hybrid Approach 172
7.5 Integer Solutions 173
7.5.1 Binary Decisions on Arc Flow Variables 173
7.5.2 Integer Decisions on Arc Flow Variables 173
7.5.3 Binary Decisions on Path Flow Variables 174
7.5.4 Subtour Elimination and 2-Path Cuts 175
7.5.5 k-Path Cuts and Parallelism 176
7.5.6 Integer Decisions on(Fractional and Integer)Time Variables 176
7.6 Special Cases 177
7.6.1 Multiple TSP with Time Windows 177
7.6.2 VRP with Backhauls and Time Windows 177
7.7 Extensions 178
7.7.1 Heterogeneous Fleet,Multiple-Depot,and Initial Conditions 178
7.7.2 Fleet Size 179
7.7.3 Multiple Time Windows 179
7.7.4 Soft Time Windows 179
7.7.5 Time-and Load-Dependent Costs 180
7.7.6 Driver Considerations 180
7.8 Computational Results for VRPTW 181
7.9 Conclusions 184
Bibliography 186
8 VRP with Backhauls&P. Toth,D. Vigo 195
8.1 Introduction 195
8.1.1 Benchmark Instances 197
8.2 Integer Linear Programming Models 198
8.2.1 Formulation of Toth and Vigo 198
8.2.2 Formulation of Mingozzi,Giorgi,and Baldacci 200
8.3 Relaxations 201
8.3.1 Relaxation Obtained by Dropping the CCCs 202
8.3.2 Relaxation Based on Projection 202
8.3.3 Lagrangian Relaxation 203
8.3.4 Overall Additive Lower Bound 204
8.3.5 Relaxation Based on the Set-Partitioning Model 204
8.4 Exact Algorithms 208
8.4.1 Algorithm of Toth and Vigo 208
8.4.2 Algorithm of Mingozzi,Giorgi,and Baldacci 209
8.4.3 Computational Results for the Exact Algorithms 210
8.5 Heuristic Algorithms 214
8.5.1 Algorithm of Deifand Bodin 214
8.5.2 Algorithms of Goetschalckx and Jacobs-Blecha 215
8.5.3 Algorithm of Toth and Vigo 216
8.5.4 Computational Results for the Heuristics 217
Bibliography 221
9 VRP with Pickup and Delivery&G. Desaulniers,J. Desrosiers,A. Erdmann,M.M. Solomon,F. Soumis 225
9.1 Introduction 225
9.2 Mathematical Formulation 226
9.2.1 Construction of the Networks 226
9.2.2 Formulation 227
9.2.3 Service Quality 228
9.2.4 Reduction of the Network Size 228
9.3 Heuristics 229
9.3.1 Construction and Improvement 229
9.3.2 Clustering Algorithms 230
9.3.3 Metaheuristics 230
9.3.4 Neural Network Heuristics 231
9.3.5 Theoretical Analysis of Algorithms 231
9.4 Optimization-Based Approaches 232
9.4.1 Single Vehicle Cases 232
9.4.2 Multiple Vehicle Cases 234
9.5 Applications 236
9.6 Computational Results 236
9.7 Conclusions 237
Bibliography 238
Ⅲ Applications and Case Studies 243
10 Routing Vehicles in the Real World:Applications in the Solid Waste,Beverage,Food,Dairy,and Newspaper Industries&B.L. Golden,A.A. Assad,E.A. Wasil 245
10.1 Introduction 245
10.2 Computerized Vehicle Routing in the Solid Waste Industry 247
10.2.1 History 247
10.2.2 Background 247
10.2.3 Commercial Collection 249
10.2.4 Residential Collection 250
10.2.5 Case Studies 250
10.2.6 Roll-on-Roll-off 252
10.2.7 Further Remarks 254
10.3 Vehicle Routing in the Beverage,Food,and Dairy Industries 254
10.3.1 Introduction 254
10.3.2 Beverage Industry 255
10.3.3 Food Industry 259
10.3.4 Dairy Industry 260
10.4 Distribution and Routing in the Newspaper Industry 266
10.4.1 Industry Background 266
10.4.2 Newspaper Distribution Problem 268
10.4.3 Vehicle Routing Algorithms for NDP 271
10.4.4 Three Case Studies 276
10.4.5 Further Remarks 280
10.5 Conclusions 280
Bibliography 281
11 Capacitated Arc Routing Problem with Vehicle-Site Dependencies:The Philadelphia Experience&J. Sniezek,L. Bodin,L. Levy,M. Ball 287
11.1 Introduction 287
11.2 Networks,Assumptions,and Goals of the CARP-VSD 288
11.2.1 Travel Network 288
11.2.2 Service Network 289
11.2.3 Vehicle Classes 290
11.2.4 Travel Network and Service Network for a Vehicle Class 291
11.2.5 Vehicle Preference List 291
11.2.6 Other Assumptions 292
11.2.7 Goals and Constraints of the CARP-VSD 292
11.3 Vehicle Decomposition Algorithm(VDA) 293
11.3.1 Step A. Create and Verify Vehicle Class Networks 293
11.3.2 Step B. Estimate Total Work and Determine Initial Fleet Mix 294
11.3.3 Step C. Partition the Service Network 301
11.3.4 Step D. Determine Travel Path and Balance the Partitions 304
11.3.5 Step E. Revise Estimate of Total Work and Adjust Fleet Mix 305
11.4 Implementation of the VDA in Philadelphia 305
11.5 Enhancements and Extensions 307
Bibliography 308
12 Inventory Routing in Practice&Ann M. Campbell,Lloyd W. Clarke,Martin W.P. Savelsbergh 309
12.1 Introduction 309
12.2 Problem Definition 310
12.3 Literature Review 311
12.4 Solution Approach 313
12.4.1 Phase Ⅰ:Integer Programming Model 313
12.4.2 Phase Ⅰ:Solving the Integer Programming Model 315
12.4.3 Phase Ⅱ:Scheduling 316
12.5 Computational Experience 319
12.5.1 Instances 319
12.5.2 Solution Quality 322
12.5.3 Alternate Heuristic 324
12.5.4 Computational Experiments 324
12.6 Conclusion 327
Bibliography 329
13 Routing Under Uncertainty:An Application in the Scheduling of Field Service Engineers&E. Hadjiconstantinou,D. Roberts 331
13.1 Introduction 331
13.2 VRPSST with Vailable Costs of Recourse 332
13.3 Literature Review 332
13.3.1 VRPST 333
13.3.2 VRPSD 333
13.4 Stochastic Integer VRPSST Formulation 334
13.4.1 First-Stage Problem 334
13.4.2 Second-Stage Problem 335
13.5 Paired Tree Search Algorithm(PTSA) 336
13.5.1 Linked Trees 337
13.5.2 Lower Bounds 337
13.5.3 Computational Implementation 339
13.6 Applied Maintenance Scheduling Problem 339
13.6.1 Maintenance Scheduling System in Practice 340
13.6.2 Stochastic Problem Setting 340
13.7 Modeling the Applied Problem as a VRPSST 341
13.8 Model Input 342
13.8.1 Job Locations and the Road Network 342
13.8.2 Service Times 342
13.9 Model Output:Computational Considerations 343
13.9.1 Framework for the Analysis of Results 343
13.9.2 Reoptimization 344
13.10 Example Scenario 345
13.11 Overall Computational Results 348
13.12 Conclusion 350
Bibliography 350
14 Evolution of Microcomputer-Based Vehicle Routing Software:Case Studies in the United States&E.K. Baker 353
14.1 Introduction 353
14.2 Definition of the VRP 356
14.2.1 Customer Specification 356
14.2.2 Product Specification 357
14.2.3 Vehicle Specification 357
14.3 Algorithms 358
14.4 Future Trends in Vehicle Routing Software 358
14.5 Summary and Conclusions 360
Bibliography 360
Index 363