Network Design with Applications to Transportation and Logistics

Contents
1 A Book About Network Design
	1 Introduction
	2 Contents of the Book
		2.1 Part I: Basic Problems and Models
		2.2 Part II: Advanced Problems and Models
		2.3 Part III: Applications in Transportation and Logistics
	3 Bibliographical Notes
	4 Conclusions and Perspectives
	References
Part I Basic Design Problems
	2 Fixed-Charge Network Design Problems
		1 Introduction
		2 Single-Commodity Formulations
			2.1 Cut-Set-Based Formulation
			2.2 The Uncapacitated Variant of the Problem
			2.3 Fixed-Charge Transportation Problem
		3 Multicommodity Formulations
			3.1 The Uncapacitated Variant of the Problem
			3.2 Cut-Set-Based Inequalities
		4 Bibliographical Notes
		5 Conclusions and Perspectives
		References
	3 Exact Methods for Fixed-Charge Network Design
		1 Introduction
		Part I: Relaxations
		2 Lagrangian Relaxations and Dantzig–Wolfe Reformulations
			2.1 A Primer on Lagrangian Relaxation
			2.2 Relaxing Linking Constraints
			2.3 Relaxing Flow Conservation Constraints
			2.4 Other Lagrangian Relaxations
		3 Relaxations by Projection and Benders Reformulations
			3.1 A Primer on Benders Decomposition
			3.2 Single-Commodity Formulations
			3.3 Multicommodity Formulations
		4 Valid Inequalities
			4.1 Cover Inequalities
			4.2 Flow Cover and Flow Pack Inequalities
		Part II: Enumeration Algorithms
		5 Branch-and-Bound Algorithms
			5.1 Relaxations
			5.2 Branching
			5.3 Filtering
		6 Branch-and-Cut Algorithms
			6.1 Separation and Lifting
			6.2 Computational Issues
		7 Benders Decomposition
			7.1 Linear Programming Relaxation
			7.2 Branch-and-Benders-Cut Algorithms
			7.3 Computational Issues
		8 Branch-and-Price Algorithms
			8.1 Pricing Subproblems
			8.2 Branching and Filtering
			8.3 Computational Issues
		Part III: Solution of Large-Scale Instances
		9 Connections with Heuristic Methods
			9.1 Slope Scaling Heuristics
			9.2 Lagrangian Heuristics
			9.3 Benders Decomposition and Heuristics
			9.4 Enumeration Algorithms and Heuristics
		10 Parallel Algorithms
			10.1 Node-Based Parallelism
			10.2 Single-Tree Parallelism
			10.3 Multiple-Tree Parallelism
		11 Bibliographical Notes
		12 Conclusions and Perspectives
		References
	4 Heuristics and Metaheuristics for Fixed-Charge Network Design
		1 Introduction
		2 Basic Concepts
			2.1 Search Space
			2.2 Neighborhoods
			2.3 Populations
			2.4 Evaluating the Performance of Heuristics and Metaheuristics
		3 Classical Heuristics
			3.1 Constructive Heuristics
			3.2 Improvement Methods (Local Search)
				3.2.1 Basic Local Search
				3.2.2 A Local Approach Search for the Fixed-Charge Transportation Problem
		4 Neighborhood-Based Metaheuristics
			4.1 Tabu Search
				4.1.1 Tabu Search for the Fixed-Charge Transportation Problem
				4.1.2 Tabu Search for the Multicommodity Capacitated Fixed-Charge Network Design Problem
			4.2 Other Neighborhood-Based Metaheuristics
				4.2.1 Simulated Annealing
				4.2.2 Iterated Local Search
				4.2.3 Greedy Randomized Adaptive Search Procedure
				4.2.4 Variable Neighborhood Search
		5 Population-Based Metaheuristics
			5.1 Genetic Algorithms/Evolutionary Algorithms
				5.1.1 A Genetic Algorithm for the Fixed-Charge Transportation Problem
				5.1.2 A Genetic Algorithm for the Multicommodity Capacitated Fixed-Charge Network Design Problem
			5.2 Path Relinking
				5.2.1 Path Relinking for the Multicommodity Capacitated Fixed-Charge Network Design Problem
			5.3 Scatter Search
				5.3.1 Scatter Search for the Multicommodity Capacitated Fixed-Charge Network Design Problem
				5.3.2 An Improved Scatter Search-Evolutionary Algorithm for the Multicommodity Capacitated Fixed-Charge Network Design Problem
		6 Matheuristics
			6.1 A Local Branching Matheuristic for the Multicommodity Capacitated Fixed-Charge Network Design Problem
			6.2 A Matheuristic Combining Exact and Heuristic Approaches for the Multicommodity Capacitated Fixed-Charge Network Design Problem
			6.3 A Hybrid Simulated Annealing-Column Generation Matheuristic for the Multicommodity Capacitated Fixed-Charge Network Design Problem
			6.4 A Cutting-Plane Based Matheuristic for the Multicommodity Capacitated Fixed-Charge Network Design Problem
		7 Parallel Metaheuristics
			7.1 Functional Parallel Strategies
			7.2 Search-Space Separation: Domain-Decomposition Strategies
			7.3 Search-Space Separation: Multi-Search Strategies
		8 Bibliographical Notes
		9 Conclusions and Perspectives
		References
Part II Advanced Problems and Models
	5 Multicommodity Multifacility Network Design
		1 Introduction
		2 Problem Formulation
		3 Preliminaries
			3.1 Metric Inequalities
			3.2 Node Partition Inequalities
			3.3 MIR Inequalities
		4 Valid Inequalities from Arc Sets
			4.1 Splittable-Flow Arc Set
			4.2 Unsplittable-Flow Arc Set
				4.2.1 c-strong inequalities
				4.2.2 k-split c-strong Inequalities
				4.2.3 Lifted Knapsack Cover Inequalities
			4.3 Multifacility Arc Set
		5 Valid Inequalities from Cut Sets
			5.1 Single-Facility Case
			5.2 Multifacility Case
		6 Partition Inequalities
		7 Bibliographical Notes
			7.1 Introduction
			7.2 Problem Formulation and Preliminaries
			7.3 Valid Inequalities from Arc Sets
			7.4 Valid Inequalities from Cut Sets
			7.5 Partition Inequalities
		8 Conclusions and Perspectives
		References
	6 Piecewise Linear Cost Network Design
		1 Introduction
		2 Formulations with Piecewise Linear Costs
			2.1 Generic Piecewise Linear Cost Network Design Formulation
			2.2 Piecewise Linear Cost Model of the Single-Facility Problem
		3 Structured Dantzig-Wolfe Decomposition for Piecewise Linear Cost Network Design
			3.1 Structured Dantzig-Wolfe Decomposition
			3.2 Application to Piecewise Linear Cost Network Design
		4 Bibliographical Notes
		5 Conclusions and Perspectives
		References
	7 Topology-Constrained Network Design
		1 Introduction
		2 Notation and Definitions
		3 Connected Networks
		4 Survivable Networks
		5 Hop Constraints
		6 Rings
		7 Bibliographical Notes
			7.1 Connected Networks
			7.2 Survivable Networks
			7.3 Hop Constraints
			7.4 Rings
		8 Conclusions and Perspectives
		References
	8 Network Design with Routing Requirements
		1 Introduction
		2 Problem Classification and Model Formulation
			2.1 Model Classification
			2.2 Routing Requirements
			2.3 Model Formulation
			2.4 Challenges in Solving the NDRR Problem
		3 Solving the NDRR Problem
			3.1 Problem Reduction
			3.2 Valid Inequalities and Composite Algorithm for the NDRR Problem
			3.3 Extension to Capacitated Network Design with Routing Restrictions
		4 NDRR Special Cases: Constrained Shortest Paths and Hop-Constrained Problems
			4.1 Constrained Shortest Path (CSP) Problem
				4.1.1 Approximation Schemes for the CSP Problem
				4.1.2 CSP Solution Algorithms
				4.1.3 Handler and Zang\'s Algorithm
			4.2 Hop-Constrained Routing and Design Problems
				4.2.1 Approximation Algorithms for the HCMST Problem
				4.2.2 Polyhedral Results for Hop-Constrained Path Problems
				4.2.3 Layered Networks and Extended Formulations for Hop-Constrained Problems
				4.2.4 Extended Formulations for General NDRR Problems
		5 Decomposition Strategies for the NDRR Problem
			5.1 Lagrangian Relaxation
			5.2 Column Generation (Dantzig-Wolfe Decomposition)
			5.3 Benders Decomposition
		6 Bibliographical Notes
		7 Concluding Remarks
		References
	9 Bilevel Network Design
		1 Introduction
		2  A Primer on Bilevel Programming
		3 The Continuous Network Design Problem
		4 A Competitive Location-Queuing Model
		5 Network Pricing
		6 Bilevel Network Interdiction
		7 Bibliographical Notes
		8  Conclusions and Perspectives
		References
	10 Stochastic Network Design
		1 Introduction
		2 Stochastic Models
			2.1 Stochastic Programs with Recourse
			2.2 Stochastic Programming with Probabilistic Constraints
		3 Scenario Generation for Stochastic Network Design
			3.1 Scenario-Based Network Design Models
			3.2 Stability Testing
			3.3 Data Challenges in Scenario Generation
		4 Solution Methods
			4.1 Benders Decomposition
			4.2 Progressive Hedging
		5 Conclusions and Perspectives
		6 Bibliographical Notes
		References
	11 Robust Network Design
		1 Introduction
		2 Robust Optimization
			2.1 What Is Robust Optimization?
			2.2 Chance-Constrained Model
			2.3 Interval Uncertainty
			2.4 Budget Uncertainty
			2.5 Polyhedral Uncertainty and the Robust Counterpart
			2.6 Multi-stage Robustness
		3 Robust Network Designs
		4 Single-Commodity Formulations
			4.1 A Flow-Based Formulation
			4.2 A Cut-Set-Based Formulation
			4.3 Separating Robust Cut-Set-Based Inequalities
				4.3.1 The Single-Commodity Hose Uncertainty Set
				4.3.2 Network Containment
			4.4 Strengthening the Formulations
			4.5 Variants of the Problem
		5 Multicommodity Formulations
			5.1 Standard Uncertainty Sets
			5.2 The VPN Problem
			5.3 Static Routing: Arc-Flow Based Formulations
			5.4 Static Routing: Path Based Formulations
			5.5 Dynamic Routing: Arc-Flow Based Formulations
			5.6 Dynamic Routing: Formulations Without Flow Variables
			5.7 Strengthening the Formulations
		6 Bibliographical Notes
		7 Conclusions and Perspectives
		References
Part III Applications in Transportation and Logistics
	12 Service Network Design
		1 Introduction
		2 Problem Settings
			2.1 Consolidation-Based Freight Carriers
			2.2 Planning and Service Network Design Models
		3 Static SND
		4 Time-Dependent SND
		5 Broadening the Scope of SND: Integrating Resource Management
		6 Managing Uncertainty
			6.1 Uncertainty in Shipment Volumes
			6.2 Other Uncertainties in SND
		7 Bibliographical Notes
		8 Conclusions and Perspectives
		References
	13 Freight Railroad Service Network Design
		1 Introduction
		2 Rail Transportation System and Planning
			2.1 Rail Transportation System
			2.2 Tactical Planning and Network Design
			2.3 Notation
		3 Static SND
			3.1 Service Selection and Train Makeup
			3.2 Car Classification and Blocking
			3.3 Integrated Planning SND
				3.3.1 Arc-Based Integrated SND
				3.3.2 Path-Based Integrated SND
				3.3.3 Advanced Path-Based Integrated SND
			3.4 Service & Block Generation and SND Models
		4 Time-Dependent SND and Integrated Planning
		5 Extending the SSND
		6 Bibliographical Notes
		7 Conclusions and Perspectives
		References
	14 Motor Carrier Service Network Design
		1 Introduction
		2 Consolidation Trucking Operations
			2.1 Trucking Service Network Design Problems
		3 Network Design Models for Flow Planning
			3.1 Arc-Based Flow Planning Model for Consolidation Trucking
			3.2 Single-Path and In-Tree Flow Planning Models
			3.3 Path-Based Models for Flow Planning
			3.4 Balancing Resources in Flow Planning
			3.5 Slope-Scaling Heuristics for Flow Planning
			3.6 A Local Search Heuristic for Flow Planning
		4 Network Design Models for Flow and Load Planning
			4.1 A Time-Expanded Model for LTL Flow Planning
			4.2 Time-Expanded Models for LTL Flow and Load Planning
			4.3 Dynamic Discretization Discovery
		5 Bibliographical Notes
		6 Concluding Remarks and Research Directions
		References
	15 Liner Shipping Network Design
		1 Introduction
		2 Overview of Liner Shipping and Liner Shipping Network Design
			2.1 Containerised Liner Shipping
			2.2 Containerised Liner Shipping Network Design
			2.3 RoRo Network Design
			2.4 The LINER-LIB Test Instances
		3 Overview of Models and Algorithms
		4 Models for the LSNDP
			4.1 Service Selection Formulations
				4.1.1 A Sub-path Service Formulation with Limited Transshipments
			4.2 Arc Formulations
			4.3 Considering Non-simple Services in the Formulation
				4.3.1 Port-Call Formulations
				4.3.2 Layer-Networks for Complex Services Structures
				4.3.3 Time-Space Models
		5 Two-Stage Algorithms
			5.1 The Container Flow Problem
			5.2 Service First Methods
			5.3 Backbone Flow
				5.3.1 From Backbone Flow to Network Design
		6 Bibliographic Notes
		7 Concluding Remarks and Future Challenges
		8 Notation Used in This Chapter
		References
	16 City Logistics
		1 Introduction
		2 City Logistics, Planning, and Design
			2.1 A Two-Tier Setting
			2.2 Planning and Design
		3 A General SSND Modeling Framework
		4 Using the Modeling Framework
			4.1 Tactical Planning for Medium-Term Horizons
			4.2 Demand Uncertainty in Tactical Planning for City Logistics
			4.3 Designing the City Logistics Network: Strategic Planning
		5 Bibliographical Notes
		6 Conclusions and Perspectives
		References
	17 Public Transportation
		1 Introduction
		2 Background
			2.1 Basic Concepts and Notation
			2.2 Problem Nomenclature, General Formulation and Solution Approach for Public Transportation Network Design
		3 Models for Public Transportation Network Optimization
			3.1 User and Operator Oriented Models with Fixed Passenger Behavior
			3.2 Explicit Modeling of Passenger Behavior
			3.3 Including Waiting Time
			3.4 Multiple Objectives and Levels of Decisions
			3.5 Other Relevant Models
		4 Solution Approaches
			4.1 Mathematical Programming Based Methods
				4.1.1 Branch-and-Bound-and-Cut Methods
				4.1.2 Decomposition Methods
			4.2 Heuristic Based Methods
				4.2.1 Route Generation and Selection
				4.2.2 Route Set Generation and Improvement
				4.2.3 Handling Specific Problem Features
		5 Bibliographical Notes
		6 Conclusions and Perspectives
		References
	18 Hub Network Design
		1 Introduction
		2 Preliminaries
		3 Hub Location Problems
			3.1 Multiple Assignments
			3.2 Single Assignments
			3.3 r-Allocation
		4 Hub Network Design Problems
			4.1 Hub Arc Location Problems
				4.1.1 Models with One-Hub-Arc O/D Paths
				4.1.2 Models with Arbitrary O/D Paths
			4.2 Specific Hub Network Topologies
				4.2.1 Star-Star Hub Networks
				4.2.2 Tree-Star Hub Networks
				4.2.3 Cycle-Star Hub Networks
				4.2.4 Hub Line Networks
		5 Bibliographical Notes
			5.1 Hub Location Problems
			5.2 Hub Network Design Problems
		6 Conclusions and Perspectives
		References
	19 Logistics Network Design
		1 Introduction
		2 A General Modeling Framework for Logistics Network Design
			2.1 Notation
			2.2 Formulation
			2.3 Extensions
				2.3.1 Lower Bounds and Capacity Alternatives
				2.3.2 Multi-Period Design Decisions
				2.3.3 Inventory Level Constraints
				2.3.4 Profit Maximization
				2.3.5 International Aspects
		3 Risk and Uncertainty
			3.1 Stochastic Programming
			3.2 Robust Optimization
		4 Reverse Logistics, Environmental Aspects and Sustainability
		5 Solution Methods
			5.1 Exact Algorithms
				5.1.1 Lagrangian Relaxation
				5.1.2 Benders Decomposition
			5.2 Heuristic Algorithms
		6 Bibliographical Notes
		7 Conclusions and Perspectives
		References
	20 Collaboration in Transport and Logistics Networks
		1 Introduction
		2 Key Collaboration Concepts in Transport and Logistics Networks
		3 Cost Sharing: Preliminaries
			3.1 Cooperative Cost Games
			3.2 Solutions for Cooperative Cost Games
				3.2.1 Core
				3.2.2 Shapley Value
				3.2.3 Least-Core
				3.2.4 Nucleolus
				3.2.5 Comparing Solutions
			3.3 Solutions for Situations
		4 Cost Sharing in Logistics Network Situations
			4.1 Minimum Cost Spanning Tree (mcst) Games
			4.2 Facility Location Games
			4.3 Hub Location Games
			4.4 Delivery Consolidation Games
		5 Cost Sharing in Cooperative Truck-Load Delivery Situations
			5.1 Desirable Properties for CTLD Solutions
			5.2 A Solution for CTLD Situations
		6 Bibliographical Notes
			6.1 Collaborations
			6.2 Game Theoretical Concepts
			6.3 Other Classes of Stylized Situations Related to Cooperative Network Design Problems
		7 Conclusions and Perspectives
		References
Index