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	403
	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