@inproceedings{FischerGrimmKlugetal., author = {Fischer, Frank and Grimm, Boris and Klug, Torsten and Schlechte, Thomas}, title = {A Re-optimization Approach for Train Dispatching}, series = {Operations Research Proceedings 2016}, booktitle = {Operations Research Proceedings 2016}, doi = {10.1007/978-3-319-55702-1_85}, pages = {645 -- 651}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferGrimmReutheretal.2015, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Template based re-optimization of rolling stock rotations}, series = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57539}, year = {2015}, abstract = {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.}, language = {en} } @misc{FischerGrimmKlugetal., author = {Fischer, Frank and Grimm, Boris and Klug, Torsten and Schlechte, Thomas}, title = {A Re-optimization Approach for Train Dispatching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60493}, abstract = {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.}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schade, Stanley}, title = {Regularity patterns for rolling stock rotation optimization}, series = {8th International Conference on Applied Operational Research, Proceedings}, volume = {8}, booktitle = {8th International Conference on Applied Operational Research, Proceedings}, pages = {28 -- 32}, abstract = {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.}, language = {en} } @inproceedings{SchadeBorndoerferBreueretal., author = {Schade, Stanley and Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schlechte, Thomas and Siebeneicher, Patrick}, title = {Pattern Detection For Large-Scale Railway Timetables}, series = {Proceedings of the IAROR conference RailLille}, booktitle = {Proceedings of the IAROR conference RailLille}, abstract = {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.}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {A Propagation Approach to Acyclic Rolling Stock Rotation Optimization}, series = {Proceedings of the IAROR conference RailLille}, booktitle = {Proceedings of the IAROR conference RailLille}, abstract = {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.}, language = {en} } @misc{GrimmBorndoerferReutheretal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {A Propagation Approach to Acyclic Rolling Stock Rotation Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-63930}, abstract = {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.}, language = {en} } @misc{SchadeBorndoerferBreueretal., author = {Schade, Stanley and Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schlechte, Thomas and Siebeneicher, Patrick}, title = {Pattern Detection For Large-Scale Railway Timetables}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-63390}, abstract = {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.}, language = {en} } @misc{Grimm, type = {Master Thesis}, author = {Grimm, Boris}, title = {Train Dispatching by Disjunctive Programming}, language = {en} } @misc{BorndoerferBreuerGrimmetal., author = {Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {Timetable Sparsification by Rolling Stock Rotation Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65948}, abstract = {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.}, language = {en} } @misc{BorndoerferGrimmReutheretal., author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Optimization of Handouts for Rolling Stock Rotations Visualization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61430}, abstract = {A railway operator creates (rolling stock) rotations in order to have a precise master plan for the operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply traverses a set of operational days while covering trips of the timetable. As it is well known, the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging and still a topical research subject. Nevertheless, we study a completely different but strongly related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In our industrial application at DB Fernverkehr AG, the handout is exactly as important as the rotation itself. Moreover, it turns out that also other European railway operators use exactly the same methodology (but not terminology). Since a rotation can have many handouts of different quality, we show how to compute optimal ones through an integer program (IP) by standard software. In addition, a construction as well as an improvement heuristic are presented. Our computational results show that the heuristics are a very reliable standalone approach to quickly find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a computational comparison to the IP approach.}, language = {en} } @article{BorndoerferGrimmReutheretal., author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Template-based Re-optimization of Rolling Stock Rotations}, series = {Public Transport}, journal = {Public Transport}, publisher = {Springer}, doi = {10.1007/s12469-017-0152-4}, pages = {1 -- 19}, abstract = {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.}, language = {en} } @misc{BrettHobergPachecoetal.2015, author = {Brett, Charles and Hoberg, Rebecca and Pacheco, Meritxell and Smith, Kyle and Bornd{\"o}rfer, Ralf and Euler, Ricardo and Gamrath, Gerwin and Grimm, Boris and Heismann, Olga and Reuther, Markus and Schlechte, Thomas and Tesch, Alexander}, title = {G-RIPS 2014 RailLab - Towards robust rolling stock rotations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53475}, year = {2015}, abstract = {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.}, language = {en} } @misc{ConiglioGrimmKosteretal., author = {Coniglio, Stefano and Grimm, Boris and Koster, Arie M.C.A. and Tieves, Martin and Werner, Axel}, title = {Optimal offline virtual network embedding with rent-at-bulk aspects}, pages = {9}, abstract = {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.}, language = {en} } @misc{GrimmBorndoerferSchlechte, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73976}, abstract = {Planning rolling stock movements in industrial passenger railway applications isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for the ICE high speed fleet of DB Fernverkehr AG one of the largest passenger railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended.}, language = {en} } @inproceedings{BorndoerferGrimmSchlechte, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Schlechte, Thomas}, title = {Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt}, series = {Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrk{\"o}ping 2019}, volume = {Link{\"o}ping Electronic Conference Proceedings}, booktitle = {Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrk{\"o}ping 2019}, number = {069}, publisher = {Link{\"o}ping University Electronic Press, Link{\"o}pings universitet}, address = {Link{\"o}ping, Sweden}, isbn = {978-91-7929-992-7}, issn = {1650-3686}, pages = {160 -- 168}, abstract = {Planning rolling stock movements in industrial passenger railway applications isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for the ICE high speed fleet of DB Fernverkehr AG one of the largest passenger railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended.}, language = {en} } @article{BorndoerferGrimmReutheretal., author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Optimization of handouts for rolling stock rotations}, series = {Journal of Rail Transport Planning \& Management}, journal = {Journal of Rail Transport Planning \& Management}, number = {10}, doi = {10.1016/j.jrtpm.2019.02.001}, pages = {1 -- 8}, abstract = {A railway operator creates (rolling stock) rotations in order to have a precise master plan for the operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply traverses a set of operational days while covering trips of the timetable. As it is well known, the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging and still a topical research subject. Nevertheless, we study a completely different but strongly related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In our industrial application at DB Fernverkehr AG, the handout is exactly as important as the rotation itself. Moreover, it turns out that also other European railway operators use exactly the same methodology (but not terminology). Since a rotation can have many handouts of different quality, we show how to compute optimal ones through an integer program (IP) by standard software. In addition, a construction as well as an improvement heuristic are presented. Our computational results show that the heuristics are a very reliable standalone approach to quickly find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a computational comparison to the IP approach.}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}, series = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, volume = {75}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, editor = {Cacchiani, Valentina and Marchetti-Spaccamela, Alberto}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2019.1}, pages = {1:1 -- 1:12}, abstract = {For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Mar{\´o}ti and Kroon, 2005; G{\´a}bor Mar{\´o}ti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Bornd{\"o}rfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.}, language = {en} } @misc{GrimmBorndoerferReutheretal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}, series = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, journal = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, issn = {1438-0064}, doi = {https://doi.org/10.4230/OASIcs.ATMOS.2019.1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75501}, abstract = {For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see Maroti and Kroon 2005, or Cordeau et. al. 2001 for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in Bornd{\"o}rfer et. al. 2015. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of Reuther 2017 that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.}, language = {en} } @inproceedings{BertholdGrimmReutheretal., author = {Berthold, Timo and Grimm, Boris and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {Strategic Planning of Rolling Stock Rotations for Public Tenders}, series = {Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019}, volume = {Link{\"o}ping Electronic Conference Proceedings}, booktitle = {Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019}, number = {069}, publisher = {Link{\"o}ping University Electronic Press, Link{\"o}pings universitet}, isbn = {978-91-7929-992-7}, issn = {1650-3686}, pages = {148 -- 159}, abstract = {Since railway companies have to apply for long-term public contracts to operate railway lines in public tenders, the question how they can estimate the operating cost for long-term periods adequately arises naturally. We consider a rolling stock rotation problem for a time period of ten years, which is based on a real world instance provided by an industry partner. We use a two stage approach for the cost estimation of the required rolling stock. In the first stage, we determine a weekly rotation plan. In the second stage, we roll out this weekly rotation plan for a longer time period and incorporate scheduled maintenance treatments. We present a heuristic approach and a mixed integer programming model to implement the process of the second stage. Finally, we discuss computational results for a real world tendering scenario.}, language = {en} } @inproceedings{GrimmBorndoerferSchulzetal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schulz, Christof and Weider, Steffen}, title = {The Rolling Stock Rotation Planning Problem under Revenue Considerations}, series = {Proceedings of the Rail Transport Demand Management Conference}, booktitle = {Proceedings of the Rail Transport Demand Management Conference}, abstract = {In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.}, language = {en} } @misc{GrimmBorndoerferSchulzetal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schulz, Christof and Weider, Steffen}, title = {The Rolling Stock Rotation Planning Problem under Revenue Considerations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71339}, abstract = {In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.}, language = {en} } @inproceedings{GrimmBorndoerferOlthoff, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Olthoff, Mats}, title = {A Solution Approach to the Vehicle Routing Problem with Perishable Goods}, series = {Operations Research 2019 Proceedings}, booktitle = {Operations Research 2019 Proceedings}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-77020}, abstract = {This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date date, which may vary for different products. Storing products is prohibited. Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e., temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018.}, language = {en} } @misc{GrimmBorndoerferOlthoff, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Olthoff, Mats}, title = {A Solution Approach to the Vehicle Routing Problem with Perishable Goods}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-77020}, abstract = {This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date date, which may vary for different products. Storing products is prohibited. Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e., temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018.}, language = {en} } @inproceedings{BorndoerferBreuerGrimmetal., author = {Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {Timetable Sparsification by Rolling Stock Rotation Optimization}, series = {Operations Research 2017}, booktitle = {Operations Research 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_96}, pages = {723 -- 728}, abstract = {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.}, language = {en} } @article{GrimmHoogervorstBorndoerfer, author = {Grimm, Boris and Hoogervorst, Rowan and Bornd{\"o}rfer, Ralf}, title = {A Comparison of Models for Rolling Stock Scheduling}, doi = {10.48550/arXiv.2312.09697}, abstract = {A major step in the planning process of passenger railway operators is the assignment of rolling stock, i.e., 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 a rolling stock scheduling setting similar to that of NS, which we show to be strongly NP-hard, and propose different variants of the Hypergraph model to tune the model to the NS setting. We prove that, in this setting, the linear programming bounds of both models are equally strong as long as a Hypergraph model variant is chosen that is sufficiently expressive. However, through a numerical evaluation on NS instances, we show that the Composition model is generally more compact in practice and can find optimal solutions in the shortest running time.}, language = {en} } @inproceedings{GrimmBorndoerferBushe, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Bushe, Julian}, title = {Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization}, series = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {https://doi.org/10.4230/OASIcs.ATMOS.2023.13}, pages = {13:1 -- 13:15}, abstract = {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{\"o}rfer et al., 2016] on a test set of real world instances.}, language = {en} } @inproceedings{BorndoerferGrimmSchade, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Schade, Stanley}, title = {A Robustness Analysis of Long Distance Train Crew Schedules in Germany}, series = {Proceedings Of The Fifth Iinternational Conference On Railway Technology: Research, Development and Maintenance}, volume = {CCC 1}, booktitle = {Proceedings Of The Fifth Iinternational Conference On Railway Technology: Research, Development and Maintenance}, issn = {2753-3239}, doi = {10.4203/ccc.1.23.17}, abstract = {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.}, language = {en} } @misc{PrauseBorndoerferGrimmetal., author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating the RSRP with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89531}, abstract = {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.}, language = {en} } @article{PrauseBorndoerferGrimmetal., author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating rolling stock rotations with integrated predictive maintenance}, series = {Journal of Rail Transport Planning \& Management}, volume = {30}, journal = {Journal of Rail Transport Planning \& Management}, doi = {10.1016/j.jrtpm.2024.100434}, pages = {100434}, abstract = {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.}, language = {en} }