车辆路径问题 英文PDF电子书下载

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