车辆路径问题 英文PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 An Overview of Vehicle Routing Problems&P.Toth,D.Vigo1

1.1 Introduction1

1.2 Problem Definition and Basic Notation5

1.2.1 Capacitated and Distance-Constrained VRP5

1.2.2 VRP with Time Windows8

1.2.3 VRP with Backhauls9

1.2.4 VRP with Pickup and Delivery10

1.3 Basic Models for the VRP11

1.3.1 Vehicle Flow Models11

1.3.2 Extensions of Vehicle Flow Models17

1.3.3 Commodity Flow Models19

1.3.4 Set-Partitioning Models21

1.4 Test Instances for the CVRP and Other VRPs22

Bibliography23

Ⅰ Capacitated Vehicle Routing Problem27

2 Branch-and-Bound Algorithms for the Capacitated VRP&P. Toth,D. Vigo29

2.1 Introduction29

2.2 Basic Relaxations30

2.2.1 Bounds Based on Assignment and Matching30

2.2.2 Bounds Based on Arborescencesand Trees32

2.2.3 Comparison of the Basic Relaxations33

2.3 Better Relaxations35

2.3.1 Additive Bounds for ACVRP35

2.3.2 Further Lower Bounds for ACVRP39

2.3.3 Lagrangian Lower Bounds for SCVRP40

2.3.4 Lower Bounds from a Set-Partitioning Formulation41

2.3.5 Comparison of the Improved Lower Bounds42

2.4 Structure of the Branch-and-Bound Algorithms for CVRP44

2.4.1 Branching Schemes and Search Strategies44

2.4.2 Reduction,Dominance Rules,and Other Features46

2.4.3 Performance of the Branch-and-Bound Algorithms47

2.5 Distance-Constrained VRP48

Bibliography49

3 Branch-and-Cut Algorithms for the Capacitated VRP&D. Naddef,G. Rinaldi53

3.1 Introduction and Two-Index Flow Model53

3.2 Branch-and-Cut55

3.3 Polyhedral Studies58

3.3.1 Capacity Constraints59

3.3.2 Generalized Capacity Constraints61

3.3.3 Framed Capacity Constraints62

3.3.4 Valid Inequalities from STSP62

3.3.5 Valid Inequalities Combining Bin Packing and STSP67

3.3.6 Valid Inequalities from the Stable Set Problem69

3.4 Separation Procedures71

3.4.1 Exact Separation of Capacity Constraints71

3.4.2 Heuristies for Capacity and Related Constraints72

3.4.3 STSP Constraints75

3.5 Branching Strategies75

3.6 Computational Results78

3.7 Conclusions81

Bibliography81

4 Set-Covering-Based Algorithms for the Capacitated VRP&J. Bramel,D.Simchi-Levi85

4.1 Introduction85

4.2 Solving the Linear Programming Relaxation of P87

4.3 Set-Covering-Based Solution Methods89

4.3.1 Branch-and-Bound Algorithm for Problem CG89

4.3.2 Polyhedral Branch-and-Bound Algorithm91

4.3.3 Pseudo-Polynomial Lower Bound on ？min92

4.3.4 Solving PD via Dual-Ascent and Branch-and-Bound94

4.4 Solving the Set-Covering Integer Program96

4.4.1 A Cutting Plane Method97

4.4.2 Branch-and-Price99

4.4.3 Additional Comments on Computational Approaches100

4.5 Computational Results100

4.6 Effectiveness of the Set-Covering Formulation102

4.6.1 Worst-Case Analysis103

4.6.2 Average-Case Analysis103

Bibliography106

5 Classicai Heuristics for the Capacitated VRP&G. Laporte,F. Semet109

5.1 Introduction109

5.2 Constructive Methods110

5.2.1 Clarke and Wright Savings Algorithm110

5.2.2 Enhancements of the Clarke and Wright Algorithm111

5.2.3 Matching-Based Savings Algorithms113

5.2.4 Sequential Insertion Heuristics114

5.3 Two-Phase Methods116

5.3.1 Elementary Clustering Methods116

5.3.2 Truncated Branch-and-Bound118

5.3.3 Petal Algorithms120

5.3.4 Route-First,Cluster-Second Methods120

5.4 Improvement Heuristics121

5.4.1 Single-Route Improvements121

5.4.2 Multiroute Improvements122

5.5 Conclusions125

Bibliography126

6 Metaheuristics for the Capacitated VRP&M. Gendreau,G. Laporte,J.-Y. Potvin129

6.1 Introduction129

6.2 Simulated Annealing130

6.2.1 Two Early Simulated Annealing Algorithms130

6.2.2 Osman's Simulated Annealing Algorithms131

6.2.3 Van Breedam's Experiments133

6.3 Deterministic Annealing133

6.4 Tabu Search134

6.4.1 Two Early Tabu Search Algorithms134

6.4.2 Osman's Tabu Search Algorithm134

6.4.3 Taburoute135

6.4.4 Taillard's Algorithm137

6.4.5 Xu and Kelly's Algorithm137

6.4.6 Rego and Roucairol's Algorithms137

6.4.7 Barbarosoglu and Ozgur's Algorithm138

6.4.8 Adaptive Memory Procedure of Rochat and Taillard138

6.4.9 Granular Tabu Search of Toth and Vigo138

6.4.10 Computational Comparison140

6.5 Genetic Algorithms140

6.5.1 Simple Genetic Algorithm140

6.5.2 Application to Sequencing Problems141

6.5.3 Application to the VRP142

6.6 Ant Algorithms144

6.7 Neural Networks146

6.8 Conclusions148

Bibliography149

Ⅱ Important Variants of the Vehicle Routing Problem155

7 VRP with Time Windows&J.-F. Cordeau,G. Desaulniers,J. Desrosiers,M.M. Solomon,F. Soumis157

7.1 Introduction157

7.2 Problem Formulation158

7.2.1 Formulation158

7.2.2 Network Lower Bound159

7.2.3 Linear Programming Lower Bound159

7.2.4 Algorithms160

7.3 Upper Bounds:Heuristic Approaches160

7.3.1 Route Construction160

7.3.2 Route Improvement161

7.3.3 Composite Heuristics161

7.3.4 Metaheuristics162

7.3.5 Parallel Implementations165

7.3.6 Optimization-Based Heuristics165

7.3.7 Asymptotically Optimal Heuristics165

7.4 Lower Bounds from Decomposition Approaches166

7.4.1 Lagrangian Relaxation166

7.4.2 Capacity and Time-Constrained Shortest-Path Problem167

7.4.3 Variable Splitting168

7.4.4 Column Generation169

7.4.5 Set-Partitioning Formulation169

7.4.6 Lower Bound170

7.4.7 Commodity Aggregation171

7.4.8 Hybrid Approach172

7.5 Integer Solutions173

7.5.1 Binary Decisions on Arc Flow Variables173

7.5.2 Integer Decisions on Arc Flow Variables173

7.5.3 Binary Decisions on Path Flow Variables174

7.5.4 Subtour Elimination and 2-Path Cuts175

7.5.5 k-Path Cuts and Parallelism176

7.5.6 Integer Decisions on(Fractional and Integer)Time Variables176

7.6 Special Cases177

7.6.1 Multiple TSP with Time Windows177

7.6.2 VRP with Backhauls and Time Windows177

7.7 Extensions178

7.7.1 Heterogeneous Fleet,Multiple-Depot,and Initial Conditions178

7.7.2 Fleet Size179

7.7.3 Multiple Time Windows179

7.7.4 Soft Time Windows179

7.7.5 Time-and Load-Dependent Costs180

7.7.6 Driver Considerations180

7.8 Computational Results for VRPTW181

7.9 Conclusions184

Bibliography186

8 VRP with Backhauls&P. Toth,D. Vigo195

8.1 Introduction195

8.1.1 Benchmark Instances197

8.2 Integer Linear Programming Models198

8.2.1 Formulation of Toth and Vigo198

8.2.2 Formulation of Mingozzi,Giorgi,and Baldacci200

8.3 Relaxations201

8.3.1 Relaxation Obtained by Dropping the CCCs202

8.3.2 Relaxation Based on Projection202

8.3.3 Lagrangian Relaxation203

8.3.4 Overall Additive Lower Bound204

8.3.5 Relaxation Based on the Set-Partitioning Model204

8.4 Exact Algorithms208

8.4.1 Algorithm of Toth and Vigo208

8.4.2 Algorithm of Mingozzi,Giorgi,and Baldacci209

8.4.3 Computational Results for the Exact Algorithms210

8.5 Heuristic Algorithms214

8.5.1 Algorithm of Deifand Bodin214

8.5.2 Algorithms of Goetschalckx and Jacobs-Blecha215

8.5.3 Algorithm of Toth and Vigo216

8.5.4 Computational Results for the Heuristics217

Bibliography221

9 VRP with Pickup and Delivery&G. Desaulniers,J. Desrosiers,A. Erdmann,M.M. Solomon,F. Soumis225

9.1 Introduction225

9.2 Mathematical Formulation226

9.2.1 Construction of the Networks226

9.2.2 Formulation227

9.2.3 Service Quality228

9.2.4 Reduction of the Network Size228

9.3 Heuristics229

9.3.1 Construction and Improvement229

9.3.2 Clustering Algorithms230

9.3.3 Metaheuristics230

9.3.4 Neural Network Heuristics231

9.3.5 Theoretical Analysis of Algorithms231

9.4 Optimization-Based Approaches232

9.4.1 Single Vehicle Cases232

9.4.2 Multiple Vehicle Cases234

9.5 Applications236

9.6 Computational Results236

9.7 Conclusions237

Bibliography238

Ⅲ Applications and Case Studies243

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. Wasil245

10.1 Introduction245

10.2 Computerized Vehicle Routing in the Solid Waste Industry247

10.2.1 History247

10.2.2 Background247

10.2.3 Commercial Collection249

10.2.4 Residential Collection250

10.2.5 Case Studies250

10.2.6 Roll-on-Roll-off252

10.2.7 Further Remarks254

10.3 Vehicle Routing in the Beverage,Food,and Dairy Industries254

10.3.1 Introduction254

10.3.2 Beverage Industry255

10.3.3 Food Industry259

10.3.4 Dairy Industry260

10.4 Distribution and Routing in the Newspaper Industry266

10.4.1 Industry Background266

10.4.2 Newspaper Distribution Problem268

10.4.3 Vehicle Routing Algorithms for NDP271

10.4.4 Three Case Studies276

10.4.5 Further Remarks280

10.5 Conclusions280

Bibliography281

11 Capacitated Arc Routing Problem with Vehicle-Site Dependencies:The Philadelphia Experience&J. Sniezek,L. Bodin,L. Levy,M. Ball287

11.1 Introduction287

11.2 Networks,Assumptions,and Goals of the CARP-VSD288

11.2.1 Travel Network288

11.2.2 Service Network289

11.2.3 Vehicle Classes290

11.2.4 Travel Network and Service Network for a Vehicle Class291

11.2.5 Vehicle Preference List291

11.2.6 Other Assumptions292

11.2.7 Goals and Constraints of the CARP-VSD292

11.3 Vehicle Decomposition Algorithm(VDA)293

11.3.1 Step A. Create and Verify Vehicle Class Networks293

11.3.2 Step B. Estimate Total Work and Determine Initial Fleet Mix294

11.3.3 Step C. Partition the Service Network301

11.3.4 Step D. Determine Travel Path and Balance the Partitions304

11.3.5 Step E. Revise Estimate of Total Work and Adjust Fleet Mix305

11.4 Implementation of the VDA in Philadelphia305

11.5 Enhancements and Extensions307

Bibliography308

12 Inventory Routing in Practice&Ann M. Campbell,Lloyd W. Clarke,Martin W.P. Savelsbergh309

12.1 Introduction309

12.2 Problem Definition310

12.3 Literature Review311

12.4 Solution Approach313

12.4.1 Phase Ⅰ:Integer Programming Model313

12.4.2 Phase Ⅰ:Solving the Integer Programming Model315

12.4.3 Phase Ⅱ:Scheduling316

12.5 Computational Experience319

12.5.1 Instances319

12.5.2 Solution Quality322

12.5.3 Alternate Heuristic324

12.5.4 Computational Experiments324

12.6 Conclusion327

Bibliography329

13 Routing Under Uncertainty:An Application in the Scheduling of Field Service Engineers&E. Hadjiconstantinou,D. Roberts331

13.1 Introduction331

13.2 VRPSST with Vailable Costs of Recourse332

13.3 Literature Review332

13.3.1 VRPST333

13.3.2 VRPSD333

13.4 Stochastic Integer VRPSST Formulation334

13.4.1 First-Stage Problem334

13.4.2 Second-Stage Problem335

13.5 Paired Tree Search Algorithm(PTSA)336

13.5.1 Linked Trees337

13.5.2 Lower Bounds337

13.5.3 Computational Implementation339

13.6 Applied Maintenance Scheduling Problem339

13.6.1 Maintenance Scheduling System in Practice340

13.6.2 Stochastic Problem Setting340

13.7 Modeling the Applied Problem as a VRPSST341

13.8 Model Input342

13.8.1 Job Locations and the Road Network342

13.8.2 Service Times342

13.9 Model Output:Computational Considerations343

13.9.1 Framework for the Analysis of Results343

13.9.2 Reoptimization344

13.10 Example Scenario345

13.11 Overall Computational Results348

13.12 Conclusion350

Bibliography350

14 Evolution of Microcomputer-Based Vehicle Routing Software:Case Studies in the United States&E.K. Baker353

14.1 Introduction353

14.2 Definition of the VRP356

14.2.1 Customer Specification356

14.2.2 Product Specification357

14.2.3 Vehicle Specification357

14.3 Algorithms358

14.4 Future Trends in Vehicle Routing Software358

14.5 Summary and Conclusions360

Bibliography360

Index363