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