Solving Network Design Problems via Decomposition, Aggregation and Approximation (eBook)

Dr. Andreas Bärmann is currently working as a postdoctoral researcher at the Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) at the chair of Economics, Discrete Optimization and Mathematics. His research is focussed on mathematical optimization, especially the optimization of logistic processes.

Danksagung 5
Abstract 7
Zusammenfassung 9
Contents 11
List of Figures 13
List of Tables 14
Introduction 15
Part I. Decomposition Algorithms for Multi-Period Network Design 20
1. Motivation 23
2. Strategic Infrastructure Planning in Railway Networks 27
2.1. Basic Terminology 27
2.1.1. Structure of the Rail Freight Network 27
2.1.2. Railway Companys 29
2.2. Strategic Track Infrastructure Planning 30
2.2.1. Planning Leve 30
2.2.2. Link Capacities and Bottlenecks 31
2.2.3. Investments in the Infrastructure 37
2.3. The Problem in the Literature 40
2.3.1. The Network Design Problem 41
2.3.2. The Design and Expansion of Railway Networks 55
3. Modelling the Expansion Problem 60
3.1. Modelling Assumptions 61
3.1.1. Link Capacities 61
3.1.2. Passenger Traffic 61
3.1.3. The Annual Budget 62
3.1.4. The Infrastructure Upgrades 62
3.1.5. Demand Orders 63
3.1.6. Transportation Revenues and Expenses 63
3.1.7. Objective 64
3.2. Input Parameters 64
3.2.1. Planning Horizon and Observation Horizon 64
3.2.2. The Railway Network 65
3.2.3. The Demand 65
3.2.4. The Upgrades 65
3.2.5. Further Parameters 66
3.2.6. Summary of Parameters 66
3.3. Single-Period Approach 67
3.4. Multi-Period Approach 70
3.4.1. Model (FMNEP) 70
3.4.2. Model (BMNEP) 75
4. Model Analysis and Solution Approaches 78
4.1. Comparing Models (FMNEP) and (BMNEP) 78
4.2. A Compact Reformulation of Model (FMNEP) 81
4.3. Preprocessing of (NEP) and (CFMNEP) 83
4.4. Decomposition Algorithms 85
4.4.1. Multiple-Knapsack Decomposition 85
4.4.2. Extending the Heuristic to an Exact Decomposition Method 89
5. Case Study for the German Railway Network 96
5.1. Our Planning Software and the Computational Setup 96
5.1.1. Implementation 97
5.1.2. The Input Data 97
5.2. Evaluating the Models and their Enhancements 99
5.2.1. Comparing the Three Model Formulations for (MNEP) 99
5.2.2. Efficiency of the Preprocessing 101
5.3. The Germany Case Study 101
5.3.1. Assessing the Quality of the Solution 103
5.3.2. Presentation and Discussion of the Solution 106
Part II. Iterative Aggregation Proceduresfor Network Design Problems 114
6. Motivation 117
7. An Iterative Aggregation Algorithm for Optimal Network Design 120
7.1. Graph Aggregation and the Definition of the Master Problem 121
7.1.1. Definition of the Subproblem and Graph Disaggregation 122
7.1.2. Correctness of the Algorithm 125
7.1.3. Relation to Benders Decomposition 125
7.2. Possible Enhancements of the Algorithm 128
8. Integration of Routing Costs into the Aggregation Scheme 131
8.1. A Special Case: Aggregating Minimum-Cost s-t-Flow Problems 132
8.1.1. The Benders Reformulation 133
8.1.2. Computing Underestimators for ? 134
8.2. An Aggregation Algorithm incorporating Routing Costs 137
9. The Computational Impact of Aggregation 143
9.1. Computational Setup and Benchmark Instances 143
9.2. Computational Results on Scale-Free Networks 144
9.2.1. Computational Results for Small Instances 145
9.2.2. Behaviour for Medium-Sized and Large Instances 148
9.2.3. Computational Results on Scale-Free Networks with Multi-Commodity Demand 152
9.2.4. Computational Results on Scale-Free Networks with Routing Costs 154
9.3. Computational Results on Real-World Railway Networks 156
9.3.1. Railway Instances without Routing Costs 157
9.3.2. Railway Instances including Routing Costs 158
Part III. Approximate Second-Order Cone Robust Optimization 162
10. Motivation 164
11. Polyhedral Approximation of Second-Order Cone Robust Counterparts 168
11.1. Outer Approximation of the Second-Order Cone 168
11.2. Inner Approximation of the Second-Order Cone 171
11.3. Upper Bounds for Second-Order Cone Programs via Linear Approximation 176
11.4. Approximating SOC Robust Counterparts 177
11.4.1. Basics in Robust Optimization 178
11.4.2. The Robust Counterpart under Linear and Ellipsoidal Uncertainty 179
11.4.3. Linear Approximation of the SOC Robust Counterpart 180
12. Computational Assessment of Approximate Robust Optimization 183
12.1. Implementation and Test Instances 183
12.2. Results on Portfolio Instances from the Literature 184
12.2.1. Description of the Portfolio Instances 184
12.2.2. Results on Small Instances: Calibration of Parameters 185
12.2.3. Results for Larger Instances 188
12.3. Results on Real-World Railway Instances 189
12.3.1. Results under Moderate Uncertainty 190
12.3.2. Results under High Uncertainty 191
Conclusions and Outlook 193
Bibliography 196