Handbook of Optimization in the Railway Industry (eBook)

Ralf Borndörfer is a Professor of Discrete Mathematics at the FU Berlin, and Head of the Optimization Department at Zuse Institute, Berlin. He earned his Ph.D. in Mathematics, as well as his Habilitation in Mathematics, Mathematical Optimization and Public Transportation at the Technical University of Berlin. Torsten Klug is a Research Assistant in Optimization at the Zuse Institute, Berlin. He earned his Diploma in Mathematics at the Technical University of Berlin. Leonardo Lamorgese is a Researcher in Applied Mathematics in the Optimization Group at SINTEF ICT, Oslo, Norway. He earned his M.Sc. in Decision Science and Operations Research at the University of Rome, La Sapienza. His research interests include Transportation, Logistics, and Health Care and Sports Scheduling. Carlo Mannino is a Senior Scientist at SINTEF ICT in Oslo, Norway and Professor of Operations Research at the University of Oslo. He earned his Ph.D. in Operations Research at the University of Rome, La Sapienza and was awarded the 2014 INFORMS Best Paper Award, Telecommunications Section, as well as the 2009 EURO Excellence in Practice Award and 2014 AIRO best application award for his work in railroad optimization. Markus Reuther is an expert in the development of integrated optimization software with many years of experience in tour planning and railroad planning at the Zuse Institute, Berlin. He has successfully graduated and promoted on novel algorithmic methods for solving complex application problems specializing in railway optimization at the Technical University of Berlin. Thomas Schlechte is a shareholder of LBW Optimization GmbH and was post-doctoral Research Fellow at the Zuse Institute, Berlin. He earned his Ph.D.  on Railway Track Allocation Models and Algorithms at the Technical University of Berlin. He is a Board Member of the International Association of Railway Operations Research (IAROR).

Preface 5
References 9
Acknowledgments 11
Contents 12
The Editors 14
List of Contributors 15
In Memoriam of Alberto Caprara(1968–2012) 18
In Memoriam of Leo G. Kroon(1958–2016) 20
1 Simulation of Rail Operations 22
1.1 Introduction 22
1.2 Types of Simulation 23
1.2.1 Simulation Tools 24
1.3 Application Fields 26
1.3.1 Simulation to Calculate the Running Times 26
1.3.2 Simulation to Verify a Timetable 26
1.3.3 Simulation to Estimate Capacity 27
1.3.4 Simulation of Yards 28
1.3.5 Simulation to Support the Definition of Infrastructure Improvements 29
1.3.6 Simulation to Estimate the Robustness of a Timetable 29
1.3.7 Simulation to Evaluate the Impact of Maintenance or Construction Works 29
1.3.8 Simulation to Estimate Ex-ante the Punctuality of a Timetable 30
1.4 Setting up a Simulation Model 30
1.4.1 Defining the Simulation Area 31
1.4.2 Creating the Infrastructure Model 32
1.4.3 Characteristics of the Rolling Stock 32
1.4.4 Running and Checking the Correctness of a Simulation Model 34
1.4.5 Inserting the Stochastic Phenomena 35
1.4.5.1 Initial Delays 35
1.4.5.2 Dwell Times 36
1.4.5.3 Train Performances 37
1.4.6 Incidents 38
1.4.7 Output 39
1.4.7.1 Animation 39
1.4.7.2 Timetable Graph 39
1.4.7.3 Diagrams 39
1.4.7.4 Statistics of Occupation 40
1.4.7.5 Delay Statistics 40
1.4.8 Evaluating the Quality of a Simulation Model 40
1.5 Weaknesses of Simulation 41
1.5.1 Stochastic Nature of Inputs Not Fully Modeled 42
1.5.2 Dispatching 43
1.5.3 Effectively Modeling Seriously Delayed Trains 43
1.5.4 Modeling Major Disruptions 44
References 44
2 Capacity Assessment in Railway Networks 46
2.1 Introduction 47
2.2 Railway Capacity and Blocking Times 48
2.2.1 Blocking Times 49
2.3 Existing Methods in Practice 51
2.3.1 UIC 406 Capacity Method 51
2.3.2 CUI Method 52
2.3.3 Open Challenges 53
2.4 Capacity Assessment of Corridors 53
2.5 Capacity Assessment of Nodes 54
2.5.1 Max-Plus Automata Model 54
2.5.2 Satisfying Additional Timetable Constraints 57
2.6 Capacity Assessment in Networks 58
2.7 Conclusions and Future Developments 61
References 62
3 Aggregation Methods for Railway Network Design Based on Lifted Benders Cuts 67
3.1 Introduction 68
3.2 Basic Aggregation Scheme 71
3.2.1 The Aggregation Master Problem 72
3.2.2 Definition of the Subproblem and Graph Disaggregation 73
3.2.3 Properties and Implementations of the Aggregation Scheme 75
3.3 Integration of Routing Costs via Lifted Benders Cuts 76
3.4 Computational Results 81
3.4.1 Test Instances 81
3.4.2 Computational Setup 82
3.4.3 Results Without Routing Costs 83
3.4.4 Results with Routing Costs 83
3.5 Conclusion 91
References 91
4 Freight Train Routing 93
4.1 Introduction 94
4.2 The Freight Train Routing Problem 97
4.2.1 Transportation Network 97
4.2.2 Freight Train Demand and Objective 98
4.2.3 Time Slice Expanded Graph 100
4.3 MIP Formulation and Solution 102
4.3.1 MIP Formulation 102
4.3.2 Solving the FTRP 103
4.3.3 Presolving 104
4.3.4 Linearization 105
4.4 Computational Results 106
4.5 Conclusion 109
References 109
5 Robust Train Timetabling 112
5.1 Introduction 113
5.2 Problem Description 114
5.2.1 Nominal TTP 114
5.2.1.1 Periodic TTP 114
5.2.1.2 Non-periodic TTP 115
5.2.2 Robust TTP 116
5.3 Robustness in Train Timetabling 117
5.3.1 Stochastic Programming 117
5.3.2 Recoverable Robustness 120
5.3.3 Recovery-to-Optimality 122
5.3.4 Light Robustness 123
5.3.5 Lagrangian Robustness 125
5.4 Comments on the Computational Results 129
5.4.1 Validation Tool 129
5.4.2 Real-World Instances 129
5.4.3 Practical Considerations 130
5.5 Conclusions and Open Perspectives 131
References 132
6 Modern Challenges in Timetabling 135
6.1 Introduction 136
6.2 Periodic Timetabling with Multiple Periods 136
6.2.1 Aperiodic Timetabling 136
6.2.2 Periodic Timetabling 137
6.2.3 The PESP 138
6.2.3.1 Solving the PESP 139
6.2.4 PESP with Multiple Periods 141
6.2.5 Solving PESP with Multiple, Nested Periods 142
6.2.6 Finding Sharp Trees 145
6.2.7 Accelerating mPESP Instances 145
6.3 Delay-Robust Event Scheduling: A Mathematical Framework 146
6.3.1 Event Scheduling and Delay Propagation Networks 147
6.3.2 Delay-Recovery Robustness 149
6.3.2.1 The Scenario Set 152
6.3.3 A Real-World Study: Delay Robust Platforming 153
6.3.3.1 Events and Delay-Propagation Network 154
6.3.3.2 The Overall Delay-Robust Model and Its Solution 155
6.4 Conclusion 156
References 157
7 Railway Track Allocation 159
7.1 Introduction 160
7.2 On Microscopy and Macroscopy 162
7.3 Macroscopic Optimization Models 164
7.3.1 Clique Separation 166
7.3.2 Configuration Networks 168
7.4 Algorithmic Techniques for the TAP 168
7.4.1 Lagrangian Relaxation 169
7.4.2 Bundle Methods 170
7.4.3 Dynamic Graph Generation 171
7.5 Status Quo and Future Opportunities 173
References 175
8 Use of Optimization Tools for Routing in Rail Freight Transport 178
8.1 Introduction 179
8.2 Survey of the Literature 180
8.3 Model Formulation 181
8.4 Model Adaptation 184
8.4.1 Interlocking of Unit Trains and Single Cars 185
8.4.2 Hierarchy Constraints Revisited 187
8.4.3 Waiting Time Revisited 187
8.4.4 Restraint Order Acceptance 189
8.4.5 A Multi-Period Approach Towards Robust Planning 190
8.4.6 Moving Horizon 192
8.4.7 Less-Than-Truckload Optimization 193
8.5 Conclusion 194
References 195
9 Optimization of Railway Freight Shunting 197
9.1 Introduction 198
9.1.1 Classification Problems in Classification Yards 198
9.1.2 Short Historical Review of Classification Methods 199
9.2 Classification Scheme of Classification Problem Variants 202
9.2.1 Track Topology 203
9.2.1.1 Design 203
9.2.1.2 Length 203
9.2.2 Sorting Mode 203
9.2.2.1 Shunting 203
9.2.2.2 Timing of t-o-Moves 204
9.2.2.3 Splitting 204
9.2.3 Requirement for Outbound Sequence 205
9.2.4 Goal 205
9.3 Single-Stage Classification 205
9.3.1 Notations 207
9.3.2 Complexity Results 207
9.3.2.1 Unbounded Variants 208
9.3.2.2 b-Bounded Variants 212
9.4 Multi-Stage Classification 214
9.4.1 Requirements for the Outbound Sequence 215
9.4.2 Goals 216
9.4.3 Complexity Results 217
9.4.4 Real-World Results for BASF, Ludwigshafen, Germany 220
9.4.5 Real-World Results for Hallsberg, Sweden 221
9.5 Practical Relevance and Conclusions 222
References 223
10 Optimization of Rolling Stock Rotations 229
10.1 Introduction 229
10.2 Literature 232
10.3 Model via Hypergraphs 234
10.4 Solve via Coarse-to-Fine 239
10.4.1 C2F Column Generation for Linear Programs 240
10.4.2 Layers for Rolling Stock Rotation Optimization 244
10.5 Apply via Re-optimization 251
References 255
11 Railway Crew Management 258
11.1 Introduction 259
11.2 Main Concepts in Crew Management 260
11.2.1 Tasks 260
11.2.2 Duties 260
11.2.3 Depots 262
11.2.4 Rosters 262
11.3 Strategic Planning 263
11.4 Operational Planning 264
11.4.1 Planning for Generic Duties 265
11.4.2 Crew Rostering 265
11.4.3 Planning for Calendar Duties 266
11.4.4 Ultra-Short Term Rescheduling 267
11.5 Real-Time Operations 267
11.6 Optimization Models 268
11.6.1 Objectives 269
11.6.2 Constraints 269
11.6.3 Crew Scheduling: Model 270
11.6.4 Crew Scheduling: Solution Technique 271
11.6.5 Real-Time Crew Rescheduling: Model 272
11.6.6 Real-Time Crew Rescheduling: Solution Technique 274
11.7 Planning Support System CREWS 275
11.7.1 CREWS: The First Phase 275
11.7.2 CREWS: Stand-Alone 276
11.7.3 CREWS: Real-Time Dispatcher 277
11.8 Further Developments 277
References 278
12 Train Dispatching 280
12.1 Introduction 281
12.1.1 Background and Scope 281
12.1.2 Aspects of Disturbance Management in Railway Traffic Systems 282
12.2 Alternative Graph and Disjunctive Formulation 285
12.3 Algorithmic Aspects 289
12.4 State of Practice 291
References 295
13 Delay Propagation and Delay Management in Transportation Networks 299
13.1 Introduction and Motivation 300
13.2 Delay Propagation 302
13.2.1 The Event-Activity Network 302
13.2.2 Delay Propagation 305
13.2.2.1 Source Delays 305
13.2.2.2 Delay Propagation Along a Single Activity 305
13.2.2.3 Delay Propagation for a Bundle of Activities 307
13.2.2.4 Delay Propagation for a Delay Scenario 307
13.3 Models: Integer Programming Formulations and Objective Functions 308
13.3.1 The Basic Model: Wait-Depart Decisions 308
13.3.2 Adding Precedence Decisions on Tracks 310
13.3.3 Adding Station Capacities and Platform Re-assignment 311
13.3.4 Delay Management Objectives 313
13.3.4.1 Delay Management with Constant Weights 313
13.3.4.2 Delay Management with Fixed Routes 314
13.3.4.3 Delay Management with Re-routing 316
13.4 Heuristics 319
13.4.1 The Basic Decision: Wait or Depart? 320
13.4.2 Adding Precedence Decisions: Which Train Goes First? 321
13.4.3 Adding Decisions in Stations: Which Platform to Use? 322
13.4.4 Adding Decisions on Passengers Paths: Which Route to Take? 324
13.4.4.1 Passenger Re-routing with Constant Penalties 324
13.4.4.2 Passenger Re-routing with OD-Dependent Penalties 325
13.5 Practical Considerations and Conclusions 326
References 328
Index 332