Network Design with Applications to Transportation and Logistics (eBook)

Contents 6
1 A Book About Network Design 8
1 Introduction 8
2 Contents of the Book 9
2.1 Part I: Basic Problems and Models 10
2.2 Part II: Advanced Problems and Models 11
2.3 Part III: Applications in Transportation and Logistics 13
3 Bibliographical Notes 16
4 Conclusions and Perspectives 16
References 18
Part I Basic Design Problems 19
2 Fixed-Charge Network Design Problems 20
1 Introduction 20
2 Single-Commodity Formulations 21
2.1 Cut-Set-Based Formulation 24
2.2 The Uncapacitated Variant of the Problem 24
2.3 Fixed-Charge Transportation Problem 25
3 Multicommodity Formulations 26
3.1 The Uncapacitated Variant of the Problem 29
3.2 Cut-Set-Based Inequalities 30
4 Bibliographical Notes 31
5 Conclusions and Perspectives 32
References 33
3 Exact Methods for Fixed-Charge Network Design 34
1 Introduction 34
Part I: Relaxations 35
2 Lagrangian Relaxations and Dantzig–Wolfe Reformulations 35
2.1 A Primer on Lagrangian Relaxation 35
2.2 Relaxing Linking Constraints 36
2.3 Relaxing Flow Conservation Constraints 38
2.4 Other Lagrangian Relaxations 40
3 Relaxations by Projection and Benders Reformulations 44
3.1 A Primer on Benders Decomposition 44
3.2 Single-Commodity Formulations 46
3.3 Multicommodity Formulations 48
4 Valid Inequalities 50
4.1 Cover Inequalities 51
4.2 Flow Cover and Flow Pack Inequalities 52
Part II: Enumeration Algorithms 53
5 Branch-and-Bound Algorithms 53
5.1 Relaxations 54
5.2 Branching 56
5.3 Filtering 58
6 Branch-and-Cut Algorithms 59
6.1 Separation and Lifting 60
6.2 Computational Issues 62
7 Benders Decomposition 64
7.1 Linear Programming Relaxation 64
7.2 Branch-and-Benders-Cut Algorithms 66
7.3 Computational Issues 67
8 Branch-and-Price Algorithms 68
8.1 Pricing Subproblems 69
8.2 Branching and Filtering 71
8.3 Computational Issues 72
Part III: Solution of Large-Scale Instances 73
9 Connections with Heuristic Methods 73
9.1 Slope Scaling Heuristics 74
9.2 Lagrangian Heuristics 75
9.3 Benders Decomposition and Heuristics 76
9.4 Enumeration Algorithms and Heuristics 78
10 Parallel Algorithms 79
10.1 Node-Based Parallelism 79
10.2 Single-Tree Parallelism 80
10.3 Multiple-Tree Parallelism 82
11 Bibliographical Notes 82
12 Conclusions and Perspectives 88
References 89
4 Heuristics and Metaheuristics for Fixed-Charge Network Design 95
1 Introduction 95
2 Basic Concepts 96
2.1 Search Space 97
2.2 Neighborhoods 98
2.3 Populations 99
2.4 Evaluating the Performance of Heuristics and Metaheuristics 99
3 Classical Heuristics 100
3.1 Constructive Heuristics 101
3.2 Improvement Methods (Local Search) 101
3.2.1 Basic Local Search 102
3.2.2 A Local Approach Search for the Fixed-Charge Transportation Problem 102
4 Neighborhood-Based Metaheuristics 103
4.1 Tabu Search 104
4.1.1 Tabu Search for the Fixed-Charge Transportation Problem 105
4.1.2 Tabu Search for the Multicommodity Capacitated Fixed-Charge Network Design Problem 106
4.2 Other Neighborhood-Based Metaheuristics 109
4.2.1 Simulated Annealing 109
4.2.2 Iterated Local Search 110
4.2.3 Greedy Randomized Adaptive Search Procedure 110
4.2.4 Variable Neighborhood Search 111
5 Population-Based Metaheuristics 111
5.1 Genetic Algorithms/Evolutionary Algorithms 112
5.1.1 A Genetic Algorithm for the Fixed-Charge Transportation Problem 113
5.1.2 A Genetic Algorithm for the Multicommodity Capacitated Fixed-Charge Network Design Problem 113
5.2 Path Relinking 114
5.2.1 Path Relinking for the Multicommodity Capacitated Fixed-Charge Network Design Problem 115
5.3 Scatter Search 116
5.3.1 Scatter Search for the Multicommodity Capacitated Fixed-Charge Network Design Problem 116
5.3.2 An Improved Scatter Search-Evolutionary Algorithm for the Multicommodity Capacitated Fixed-Charge Network Design Problem 117
6 Matheuristics 119
6.1 A Local Branching Matheuristic for the Multicommodity Capacitated Fixed-Charge Network Design Problem 119
6.2 A Matheuristic Combining Exact and Heuristic Approaches for the Multicommodity Capacitated Fixed-Charge Network Design Problem 120
6.3 A Hybrid Simulated Annealing-Column Generation Matheuristic for the Multicommodity Capacitated Fixed-Charge Network Design Problem 121
6.4 A Cutting-Plane Based Matheuristic for the Multicommodity Capacitated Fixed-Charge Network Design Problem 121
7 Parallel Metaheuristics 122
7.1 Functional Parallel Strategies 123
7.2 Search-Space Separation: Domain-Decomposition Strategies 124
7.3 Search-Space Separation: Multi-Search Strategies 126
8 Bibliographical Notes 132
9 Conclusions and Perspectives 137
References 138
Part II Advanced Problems and Models 143
5 Multicommodity Multifacility Network Design 144
1 Introduction 144
2 Problem Formulation 145
3 Preliminaries 148
3.1 Metric Inequalities 148
3.2 Node Partition Inequalities 149
3.3 MIR Inequalities 150
4 Valid Inequalities from Arc Sets 151
4.1 Splittable-Flow Arc Set 152
4.2 Unsplittable-Flow Arc Set 153
4.2.1 c-strong inequalities 154
4.2.2 k-split c-strong Inequalities 154
4.2.3 Lifted Knapsack Cover Inequalities 155
4.3 Multifacility Arc Set 156
5 Valid Inequalities from Cut Sets 157
5.1 Single-Facility Case 157
5.2 Multifacility Case 160
6 Partition Inequalities 162
7 Bibliographical Notes 165
7.1 Introduction 165
7.2 Problem Formulation and Preliminaries 165
7.3 Valid Inequalities from Arc Sets 165
7.4 Valid Inequalities from Cut Sets 166
7.5 Partition Inequalities 166
8 Conclusions and Perspectives 166
References 167
6 Piecewise Linear Cost Network Design 170
1 Introduction 170
2 Formulations with Piecewise Linear Costs 172
2.1 Generic Piecewise Linear Cost Network Design Formulation 172
2.2 Piecewise Linear Cost Model of the Single-Facility Problem 175
3 Structured Dantzig-Wolfe Decomposition for Piecewise Linear Cost Network Design 179
3.1 Structured Dantzig-Wolfe Decomposition 180
3.2 Application to Piecewise Linear Cost Network Design 182
4 Bibliographical Notes 185
5 Conclusions and Perspectives 187
References 187
7 Topology-Constrained Network Design 189
1 Introduction 189
2 Notation and Definitions 191
3 Connected Networks 193
4 Survivable Networks 196
5 Hop Constraints 200
6 Rings 202
7 Bibliographical Notes 205
7.1 Connected Networks 205
7.2 Survivable Networks 205
7.3 Hop Constraints 206
7.4 Rings 207
8 Conclusions and Perspectives 207
References 208
8 Network Design with Routing Requirements 211
1 Introduction 211
2 Problem Classification and Model Formulation 215
2.1 Model Classification 215
2.2 Routing Requirements 216
2.3 Model Formulation 218
2.4 Challenges in Solving the NDRR Problem 220
3 Solving the NDRR Problem 222
3.1 Problem Reduction 222
3.2 Valid Inequalities and Composite Algorithm for the NDRR Problem 224
3.3 Extension to Capacitated Network Design with Routing Restrictions 228
4 NDRR Special Cases: Constrained Shortest Paths and Hop-Constrained Problems 230
4.1 Constrained Shortest Path (CSP) Problem 230
4.1.1 Approximation Schemes for the CSP Problem 231
4.1.2 CSP Solution Algorithms 232
4.1.3 Handler and Zang's Algorithm 233
4.2 Hop-Constrained Routing and Design Problems 234
4.2.1 Approximation Algorithms for the HCMST Problem 235
4.2.2 Polyhedral Results for Hop-Constrained Path Problems 236
4.2.3 Layered Networks and Extended Formulations for Hop-Constrained Problems 237
4.2.4 Extended Formulations for General NDRR Problems 239
5 Decomposition Strategies for the NDRR Problem 241
5.1 Lagrangian Relaxation 241
5.2 Column Generation (Dantzig-Wolfe Decomposition) 242
5.3 Benders Decomposition 243
6 Bibliographical Notes 244
7 Concluding Remarks 250
References 252
9 Bilevel Network Design 256
1 Introduction 256
2 A Primer on Bilevel Programming 256
3 The Continuous Network Design Problem 261
4 A Competitive Location-Queuing Model 264
5 Network Pricing 269
6 Bilevel Network Interdiction 275
7 Bibliographical Notes 279
8 Conclusions and Perspectives 280
References 281
10 Stochastic Network Design 283
1 Introduction 283
2 Stochastic Models 286
2.1 Stochastic Programs with Recourse 287
2.2 Stochastic Programming with Probabilistic Constraints 291
3 Scenario Generation for Stochastic Network Design 293
3.1 Scenario-Based Network Design Models 294
3.2 Stability Testing 295
3.3 Data Challenges in Scenario Generation 297
4 Solution Methods 298
4.1 Benders Decomposition 298
4.2 Progressive Hedging 304
5 Conclusions and Perspectives 311
6 Bibliographical Notes 313
References 314
11 Robust Network Design 316
1 Introduction 316
2 Robust Optimization 317
2.1 What Is Robust Optimization? 317
2.2 Chance-Constrained Model 317
2.3 Interval Uncertainty 318
2.4 Budget Uncertainty 319
2.5 Polyhedral Uncertainty and the Robust Counterpart 321
2.6 Multi-stage Robustness 322
3 Robust Network Designs 322
4 Single-Commodity Formulations 323
4.1 A Flow-Based Formulation 324
4.2 A Cut-Set-Based Formulation 325
4.3 Separating Robust Cut-Set-Based Inequalities 326
4.3.1 The Single-Commodity Hose Uncertainty Set 326
4.3.2 Network Containment 327
4.4 Strengthening the Formulations 328
4.5 Variants of the Problem 328
5 Multicommodity Formulations 329
5.1 Standard Uncertainty Sets 329
5.2 The VPN Problem 330
5.3 Static Routing: Arc-Flow Based Formulations 331
5.4 Static Routing: Path Based Formulations 335
5.5 Dynamic Routing: Arc-Flow Based Formulations 336
5.6 Dynamic Routing: Formulations Without Flow Variables 337
5.7 Strengthening the Formulations 338
6 Bibliographical Notes 339
7 Conclusions and Perspectives 340
References 340
Part III Applications in Transportation and Logistics 343
12 Service Network Design 344
1 Introduction 344
2 Problem Settings 346
2.1 Consolidation-Based Freight Carriers 346
2.2 Planning and Service Network Design Models 349
3 Static SND 352
4 Time-Dependent SND 354
5 Broadening the Scope of SND: Integrating Resource Management 357
6 Managing Uncertainty 363
6.1 Uncertainty in Shipment Volumes 365
6.2 Other Uncertainties in SND 367
7 Bibliographical Notes 368
8 Conclusions and Perspectives 373
References 377
13 Freight Railroad Service Network Design 380
1 Introduction 380
2 Rail Transportation System and Planning 382
2.1 Rail Transportation System 382
2.2 Tactical Planning and Network Design 386
2.3 Notation 390
3 Static SND 392
3.1 Service Selection and Train Makeup 393
3.2 Car Classification and Blocking 395
3.3 Integrated Planning SND 397
3.3.1 Arc-Based Integrated SND 398
3.3.2 Path-Based Integrated SND 399
3.3.3 Advanced Path-Based Integrated SND 400
3.4 Service & Block Generation and SND Models
4 Time-Dependent SND and Integrated Planning 405
5 Extending the SSND 410
6 Bibliographical Notes 414
7 Conclusions and Perspectives 418
References 419
14 Motor Carrier Service Network Design 424
1 Introduction 424
2 Consolidation Trucking Operations 425
2.1 Trucking Service Network Design Problems 428
3 Network Design Models for Flow Planning 430
3.1 Arc-Based Flow Planning Model for Consolidation Trucking 432
3.2 Single-Path and In-Tree Flow Planning Models 435
3.3 Path-Based Models for Flow Planning 439
3.4 Balancing Resources in Flow Planning 441
3.5 Slope-Scaling Heuristics for Flow Planning 443
3.6 A Local Search Heuristic for Flow Planning 445
4 Network Design Models for Flow and Load Planning 447
4.1 A Time-Expanded Model for LTL Flow Planning 448
4.2 Time-Expanded Models for LTL Flow and Load Planning 450
4.3 Dynamic Discretization Discovery 455
5 Bibliographical Notes 457
6 Concluding Remarks and Research Directions 461
References 462
15 Liner Shipping Network Design 465
1 Introduction 465
2 Overview of Liner Shipping and Liner Shipping Network Design 466
2.1 Containerised Liner Shipping 466
2.2 Containerised Liner Shipping Network Design 468
2.3 RoRo Network Design 472
2.4 The LINER-LIB Test Instances 474
3 Overview of Models and Algorithms 474
4 Models for the LSNDP 476
4.1 Service Selection Formulations 477
4.1.1 A Sub-path Service Formulation with Limited Transshipments 478
4.2 Arc Formulations 480
4.3 Considering Non-simple Services in the Formulation 484
4.3.1 Port-Call Formulations 485
4.3.2 Layer-Networks for Complex Services Structures 485
4.3.3 Time-Space Models 486
5 Two-Stage Algorithms 487
5.1 The Container Flow Problem 488
5.2 Service First Methods 489
5.3 Backbone Flow 492
5.3.1 From Backbone Flow to Network Design 493
6 Bibliographic Notes 494
7 Concluding Remarks and Future Challenges 495
8 Notation Used in This Chapter 496
References 500
16 City Logistics 502
1 Introduction 502
2 City Logistics, Planning, and Design 504
2.1 A Two-Tier Setting 504
2.2 Planning and Design 507
3 A General SSND Modeling Framework 508
4 Using the Modeling Framework 512
4.1 Tactical Planning for Medium-Term Horizons 513
4.2 Demand Uncertainty in Tactical Planning for City Logistics 517
4.3 Designing the City Logistics Network: Strategic Planning 523
5 Bibliographical Notes 524
6 Conclusions and Perspectives 527
References 529
17 Public Transportation 533
1 Introduction 533
2 Background 535
2.1 Basic Concepts and Notation 535
2.2 Problem Nomenclature, General Formulation and Solution Approach for Public Transportation Network Design 537
3 Models for Public Transportation Network Optimization 539
3.1 User and Operator Oriented Models with Fixed Passenger Behavior 540
3.2 Explicit Modeling of Passenger Behavior 542
3.3 Including Waiting Time 543
3.4 Multiple Objectives and Levels of Decisions 545
3.5 Other Relevant Models 547
4 Solution Approaches 548
4.1 Mathematical Programming Based Methods 548
4.1.1 Branch-and-Bound-and-Cut Methods 548
4.1.2 Decomposition Methods 549
4.2 Heuristic Based Methods 550
4.2.1 Route Generation and Selection 550
4.2.2 Route Set Generation and Improvement 551
4.2.3 Handling Specific Problem Features 552
5 Bibliographical Notes 553
6 Conclusions and Perspectives 555
References 556
18 Hub Network Design 560
1 Introduction 560
2 Preliminaries 562
3 Hub Location Problems 564
3.1 Multiple Assignments 565
3.2 Single Assignments 567
3.3 r-Allocation 570
4 Hub Network Design Problems 572
4.1 Hub Arc Location Problems 572
4.1.1 Models with One-Hub-Arc O/D Paths 573
4.1.2 Models with Arbitrary O/D Paths 576
4.2 Specific Hub Network Topologies 578
4.2.1 Star-Star Hub Networks 578
4.2.2 Tree-Star Hub Networks 580
4.2.3 Cycle-Star Hub Networks 582
4.2.4 Hub Line Networks 583
5 Bibliographical Notes 584
5.1 Hub Location Problems 585
5.2 Hub Network Design Problems 586
6 Conclusions and Perspectives 587
References 588
19 Logistics Network Design 592
1 Introduction 592
2 A General Modeling Framework for Logistics Network Design 594
2.1 Notation 594
2.2 Formulation 596
2.3 Extensions 599
2.3.1 Lower Bounds and Capacity Alternatives 599
2.3.2 Multi-Period Design Decisions 599
2.3.3 Inventory Level Constraints 600
2.3.4 Profit Maximization 602
2.3.5 International Aspects 604
3 Risk and Uncertainty 605
3.1 Stochastic Programming 605
3.2 Robust Optimization 607
4 Reverse Logistics, Environmental Aspects and Sustainability 608
5 Solution Methods 611
5.1 Exact Algorithms 611
5.1.1 Lagrangian Relaxation 611
5.1.2 Benders Decomposition 612
5.2 Heuristic Algorithms 612
6 Bibliographical Notes 613
7 Conclusions and Perspectives 615
References 616
20 Collaboration in Transport and Logistics Networks 619
1 Introduction 619
2 Key Collaboration Concepts in Transport and Logistics Networks 621
3 Cost Sharing: Preliminaries 622
3.1 Cooperative Cost Games 623
3.2 Solutions for Cooperative Cost Games 624
3.2.1 Core 625
3.2.2 Shapley Value 626
3.2.3 Least-Core 627
3.2.4 Nucleolus 628
3.2.5 Comparing Solutions 628
3.3 Solutions for Situations 629
4 Cost Sharing in Logistics Network Situations 630
4.1 Minimum Cost Spanning Tree (mcst) Games 630
4.2 Facility Location Games 634
4.3 Hub Location Games 637
4.4 Delivery Consolidation Games 639
5 Cost Sharing in Cooperative Truck-Load Delivery Situations 640
5.1 Desirable Properties for CTLD Solutions 643
5.2 A Solution for CTLD Situations 646
6 Bibliographical Notes 647
6.1 Collaborations 647
6.2 Game Theoretical Concepts 649
6.3 Other Classes of Stylized Situations Related to Cooperative Network Design Problems 649
7 Conclusions and Perspectives 650
References 651
Index 655