TY - JOUR A1 - Grimm, Boris A1 - Hoogervorst, Rowan A1 - Borndörfer, Ralf T1 - A Comparison of Two Models for Rolling Stock Scheduling JF - Transportation Science N2 - A major step in the planning process of passenger railway operators is the assignment of rolling stock, that is, train units, to the trips of the timetable. A wide variety of mathematical optimization models have been proposed to support this task, which we discuss and argue to be justified in order to deal with operational differences between railway operators, and hence different planning requirements, in the best possible way. Our investigation focuses on two commonly used models, the composition model and the hypergraph model, that were developed for Netherlands Railways (NS) and DB Fernverkehr AG (DB), respectively. We compare these models in two distinct problem settings, an NS setting and DB-light setting and consider different model variants to tune the models to these settings. We prove that in both of these settings, the linear programming bounds of the two models are equally strong as long as a number of reasonable assumptions are met. However, through a numerical evaluation on NS and DB-light instances, we show that the numerical performance of the models strongly depends on the instances. Although the composition model is the most compact and fastest model for the NS instances, an adjusted version of this model grows quickly for the DB-light instances and is then outperformed by the considered hypergraph model variants. Moreover, we show that a depot-extended version of the hypergraph model is able to combine strengths of both models and show good performance on both the NS and DB-light instances. Y1 - 2025 U6 - https://doi.org/10.1287/trsc.2024.0505 VL - 59 IS - 5 ER - TY - THES A1 - Grimm, Boris T1 - Train Dispatching by Disjunctive Programming Y1 - 2012 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Template based re-optimization of rolling stock rotations T2 - Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015) N2 - Rolling stock, i.e., rail vehicles, are among the most expensive and limited assets of a railway company. They must be used efficiently applying optimization techniques. One important aspect is re-optimization, which is the topic that we consider in this paper. We propose a template concept that allows to compute cost minimal rolling stock rotations under a large variety of re-optimization requirements. Two examples, involving a connection template and a rotation template, are discussed. An implementation within the rolling stock rotation optimizer rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe, are presented. Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57539 ER - TY - CHAP A1 - Fischer, Frank A1 - Grimm, Boris A1 - Klug, Torsten A1 - Schlechte, Thomas T1 - A Re-optimization Approach for Train Dispatching T2 - Operations Research Proceedings 2016 N2 - The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation. We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_85 SP - 645 EP - 651 ER - TY - CHAP A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schade, Stanley T1 - Regularity patterns for rolling stock rotation optimization T2 - 8th International Conference on Applied Operational Research, Proceedings N2 - The operation of railways gives rise to many fundamental optimization problems. One of these problems is to cover a given set of timetabled trips by a set of rolling stock rotations. This is well known as the Rolling Stock Rotation Problem (RSRP). Most approaches in the literature focus primarily on modeling and minimizing the operational costs. However, an essential aspect for the industrial application is mostly neglected. As the RSRP follows timetabling and line planning, where periodicity is a highly desired property, it is also desired to carry over periodic structures to rolling stock rotations and following operations. We call this complex requirement regularity. Regularity turns out to be of essential interest, especially in the industrial scenarios that we tackle in cooperation with DB Fernverkehr AG. Moreover, regularity in the context of the RSRP has not been investigated thoroughly in the literature so far. We introduce three regularity patterns to tackle this requirement, namely regular trips, regular turns, and regular handouts. We present a two-stage approach in order to optimize all three regularity patterns. At first, we integrate regularity patterns into an integer programming approach for the minimization of the operational cost of rolling stock rotations. Afterwards regular handouts are computed. These handouts present the rotations of the first stage in the most regular way. Our computational results (i.e., rolling stock rotations evaluated by planners of DB Fernverkehr AG) show that the three regularity patterns and our concept are a valuable and, moreover, an essential contribution to rolling stock rotation optimization. Y1 - 2016 VL - 8 SP - 28 EP - 32 ER - TY - GEN 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 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. T3 - ZIB-Report - 17-24 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-63930 SN - 1438-0064 ER - TY - GEN A1 - Brett, Charles A1 - Hoberg, Rebecca A1 - Pacheco, Meritxell A1 - Smith, Kyle A1 - Borndörfer, Ralf A1 - Euler, Ricardo A1 - Gamrath, Gerwin A1 - Grimm, Boris A1 - Heismann, Olga A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Tesch, Alexander T1 - G-RIPS 2014 RailLab - Towards robust rolling stock rotations N2 - The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an opportunity for high-achieving graduate-level students to work in teams on a real-world research project proposed by a sponsor from industry or the public sector. Each G-RIPS team consists of four international students (two from the US and two from European universities), an academic mentor, and an industrial sponsor. This is the report of the Rail-Lab project on the definition and integration of robustness aspects into optimizing rolling stock schedules. In general, there is a trade-off for complex systems between robustness and efficiency. The ambitious goal was to explore this trade-off by implementing numerical simulations and developing analytic models. In rolling stock planning a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects, have to be considered in an integrated model. General hypergraphs provide the modeling power to tackle those requirements. Furthermore, integer programming approaches are able to produce high quality solutions for the deterministic problem. When stochastic time delays are considered, the mathematical programming problem is much more complex and presents additional challenges. Thus, we started with a basic variant of the deterministic case, i.e., we are only considering hypergraphs representing vehicle composition and regularity. We transfered solution approaches for robust optimization from the airline industry to the setting of railways and attained a reasonable measure of robustness. Finally, we present and discuss different methods to optimize this robustness measure. T3 - ZIB-Report - 14-34 KW - robust optimization, rolling stock planning Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53475 SN - 1438-0064 N1 - ZIB-Report 14-34 ER - TY - GEN A1 - Fischer, Frank A1 - Grimm, Boris A1 - Klug, Torsten A1 - Schlechte, Thomas T1 - A Re-optimization Approach for Train Dispatching N2 - The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation. We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012. T3 - ZIB-Report - 16-49 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60493 SN - 1438-0064 ER - TY - GEN A1 - Coniglio, Stefano A1 - Grimm, Boris A1 - Koster, Arie M.C.A. A1 - Tieves, Martin A1 - Werner, Axel T1 - Optimal offline virtual network embedding with rent-at-bulk aspects N2 - Network virtualization techniques allow for the coexistence of many virtual networks (VNs) jointly sharing the resources of an underlying substrate network. The Virtual Network Embedding problem (VNE) arises when looking for the most profitable set of VNs to embed onto the substrate. In this paper, we address the offline version of the problem. We propose a Mixed-Integer Linear Programming formulation to solve it to optimality which accounts for acceptance and rejection of virtual network requests, allowing for both splittable and unsplittable (single path) routing schemes. Our formulation also considers a Rent-at-Bulk (RaB) model for the rental of substrate capacities where economies of scale apply. To better emphasize the importance of RaB, we also compare our method to a baseline one which only takes RaB into account a posteriori, once a solution to VNE, oblivious to RaB, has been found. Computational experiments show the viability of our approach, stressing the relevance of addressing RaB directly with an exact formulation. Y1 - 2015 ER - 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 -