TY - CHAP A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schade, Stanley A1 - Schlechte, Thomas T1 - A Propagation Approach to Acyclic Rolling Stock Rotation Optimization T2 - Proceedings of the IAROR conference RailLille N2 - The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach. Y1 - 2017 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Breuer, Matthias A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schade, Stanley A1 - Schlechte, Thomas T1 - Timetable Sparsification by Rolling Stock Rotation Optimization N2 - Rolling stock optimization is a task that naturally arises by operating a railway system. It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike. Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data. T3 - ZIB-Report - 17-63 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65948 SN - 1438-0064 ER - TY - GEN A1 - Schade, Stanley A1 - Borndörfer, Ralf A1 - Breuer, Matthias A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Siebeneicher, Patrick T1 - Pattern Detection For Large-Scale Railway Timetables N2 - We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner. T3 - ZIB-Report - 17-17 KW - railway timetables KW - visualization KW - pattern detection Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-63390 SN - 1438-0064 ER - TY - CHAP A1 - Schade, Stanley A1 - Borndörfer, Ralf A1 - Breuer, Matthias A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Siebeneicher, Patrick T1 - Pattern Detection For Large-Scale Railway Timetables T2 - Proceedings of the IAROR conference RailLille N2 - We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner. Y1 - 2017 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Template-based Re-optimization of Rolling Stock Rotations JF - Public Transport N2 - Rolling stock, i.e., the set of railway vehicles, is among the most expensive and limited assets of a railway company and must be used efficiently. We consider in this paper the re-optimization problem to recover from unforeseen disruptions. We propose a template concept that allows to recover cost minimal rolling stock rotations from reference rotations under a large variety of operational requirements. To this end, connection templates as well as rotation templates are introduced and their application within a rolling stock rotation planning model is discussed. We present an implementation within the rolling stock rotation optimization framework rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe. Y1 - 2017 U6 - https://doi.org/10.1007/s12469-017-0152-4 SP - 1 EP - 19 PB - Springer ER - TY - GEN A1 - Prause, Felix A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Tesch, Alexander T1 - Approximating the RSRP with Predictive Maintenance N2 - We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions. T3 - ZIB-Report - 23-04 KW - Rolling Stock Rotation Planning KW - Predictive Maintenance KW - Integer Linear Programming KW - Heuristic KW - Lower Bound Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89531 SN - 1438-0064 ER - TY - JOUR A1 - Prause, Felix A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Tesch, Alexander T1 - Approximating rolling stock rotations with integrated predictive maintenance JF - Journal of Rail Transport Planning & Management N2 - We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for six instances derived from real-world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions. Y1 - 2024 U6 - https://doi.org/10.1016/j.jrtpm.2024.100434 VL - 30 SP - 100434 ER - TY - CHAP A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Bushe, Julian T1 - Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization T2 - 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) N2 - The fundamental task of every passenger railway operator is to offer an attractive railway timetable to the passengers while operating it as cost efficiently as possible. The available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating costs are minimum. This so-called Rolling Stock Rotation Problem (RSRP) is well studied in the literature. In this paper we consider an acyclic version of the RSRP that includes vehicle maintenance. As the latter is an important aspect, maintenance services have to be planned simultaneously to ensure the rotation’s feasibility in practice. Indeed, regular maintenance is important for the safety and reliability of the rolling stock as well as enforced by law in many countries. We present a new integer programming formulation that links a hyperflow to model vehicle compositions and their coupling decisions to a set of path variables that take care of the resource consumption of the individual vehicles. To solve the model we developed different column generation algorithms which are compared to each other as well as to the MILP flow formulation of [Ralf Borndörfer et al., 2016] on a test set of real world instances. Y1 - 2023 U6 - https://doi.org/https://doi.org/10.4230/OASIcs.ATMOS.2023.13 VL - 115 SP - 13:1 EP - 13:15 PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Schade, Stanley T1 - A Robustness Analysis of Long Distance Train Crew Schedules in Germany T2 - Proceedings Of The Fifth Iinternational Conference On Railway Technology: Research, Development and Maintenance N2 - Nowadays railway networks are highly complex and often very fragile systems. A wide variety of individual operations that influence each other have to go hand in hand to end up with a smoothly and efficiently running system. Many of these operations suffer from uncertainty as trains could be delayed, the signaling system be disrupted or scheduled crews could be ill. Usually these opartions could be organized hierarchically from long term strategical decisions to real time decision management. Each stage in the hierarchy defines a different mathematical optimization problem, which is solved sequentially. At every stage the knowledge about preceding or succeeding planning stages may vary and also the interaction between two stages in this chain of problems may vary from almost no interaction to highly dependent situations. This paper deals with a topic that is an example for the latter case, namely the interaction between vehicle schedules, vehicle punctuality, and crew schedules. To reduce the number of potential rescheduling actions we developed a software tool in cooperation with our practical partner DB Fernverkehr AG (DBF) to predict a certain set of critical crew schedules. This tool evaluates, predicts, and determines "bottlenecks" in the crew schedule in the sense of potentially required rescheduling actions due to likely delays. The approach was tested on real life crew and train timetable data of DBF and can be regarded as the computation of key performance indicators, which is often desired. For our experiments we had access to the operated timetable and crew schedule of DBF for periods of two and six weeks in 2019. Y1 - 2023 U6 - https://doi.org/10.4203/ccc.1.23.17 SN - 2753-3239 VL - CCC 1 ER -