TY - CHAP A1 - Schenker, Sebastian A1 - Vierhaus, Ingmar A1 - Borndörfer, Ralf A1 - Fügenschuh, Armin A1 - Skutella, Martin ED - Stark, Rainer ED - Seliger, Günther ED - Bonvoisin, Jérémy T1 - Optimisation Methods in Sustainable Manufacturing BT - Challenges, Solutions and Implementation Perspectives T2 - Sustainable Manufacturing N2 - Sustainable manufacturing is driven by the insight that the focus on the economic dimension in current businesses and lifestyles has to be broadened to cover all three pillars of sustainability: economic development, social development, and environmental protection. Y1 - 2017 SN - 978-3-319-48514-0 U6 - https://doi.org/10.1007/978-3-319-48514-0_15 SP - 239 EP - 253 PB - Springer International Publishing ER - TY - GEN A1 - Ahmadi, Sepideh A1 - Gritzbach, Sascha F. A1 - Lund-Nguyen, Kathryn A1 - McCullough-Amal, Devita T1 - Rolling Stock Rotation Optimization in Days of Strike: An Automated Approach for Creating an Alternative Timetable N2 - The operation of a railway network as large as Deutsche Bahn's Intercity Express (ICE) hinges on a number of factors, such as the availability of personnel and the assignment of physical vehicles to a timetable schedule, a problem known as the rolling stock rotation problem (RSRP). In this paper, we consider the problem of creating an alternative timetable in the case that there is a long-term disruption, such as a strike, and the effects that this alternative timetable has on the resulting vehicle rotation plan. We define a priority measure via the Analytic Hierarchy Process (AHP) to determine the importance of each trip in the timetable and therefore which trips to cancel or retain. We then compare our results with those of a limited timetable manually designed by Deutsche Bahn (DB). We find that while our timetable results in a more expensive rotation plan, its flexibility lends itself to a number of simple improvements. Furthermore, our priority measure has the potential to be integrated into the rolling stock rotation optimization process, in particular, the Rotation Optimizer for Railways (ROTOR) software, via the cost function. Ultimately, our method provides the foundation for an automated way of creating a new timetable quickly, and potentially in conjunction with a new rotation plan, in the case of a limited scenario. T3 - ZIB-Report - 15-52 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56425 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schulz, Christof A1 - Seidl, Stephan A1 - Weider, Steffen T1 - Integration of Duty Scheduling and Rostering to Increase Driver Satisfaction N2 - Integrated treatment of hitherto individual steps in the planning process of public transit companies discloses opportunities to reduce costs and to improve the quality of service. The arising integrated planning problems are complex and their solution requires the development of novel mathematical methods. This article proposes a mathematical optimization approach to integrate duty scheduling and rostering in public transit, which allows to significantly increase driver satisfaction at almost zero cost. This is important in order to to increase the attractiveness of the driver profession. The integration is based on coupling the subproblems by duty templates, which, compared to a coupling by duties, drastically reduces the problem complexity. T3 - ZIB-Report - 15-50 KW - Benders decomposition KW - driver satisfaction KW - duty templates KW - duty scheduling KW - rostering Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56299 SN - 1438-0064 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - A Hall Condition for Normal Hypergraphs N2 - Conforti, Cornuéjols, Kapoor, and Vusković gave a Hall-type condition for the non-existence of a perfect matching in a balanced hypergraph. We generalize this result to the class of normal hypergraphs. T3 - ZIB-Report - 15-45 KW - Matchings in hypergraphs KW - Normal hypergraphs KW - Hall condition Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56175 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem T2 - 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems. Y1 - 2014 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2014.79 VL - 42 SP - 79 EP - 91 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Vehicle Rotation Planning for Intercity Railways N2 - This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers. T3 - ZIB-Report - 12-11 KW - rolling-stock-planning KW - mixed-integer-programming KW - hypergraphs KW - column generation KW - rapid branching Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14731 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Eßer, Thomas A1 - Frankenberger, Patrick A1 - Huck, Andreas A1 - Jobmann, Christoph A1 - Krostitz, Boris A1 - Kuchenbecker, Karsten A1 - Moorhagen, Kai A1 - Nagl, Philipp A1 - Peterson, Michael A1 - Reuther, Markus A1 - Schang, Thilo A1 - Schoch, Michael A1 - Schülldorf, Hanno A1 - Schütz, Peter A1 - Therolf, Tobias A1 - Waas, Kerstin A1 - Weider, Steffen T1 - Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization JF - Informs Journal on Applied Analytics N2 - Deutsche Bahn (DB) operates a large fleet of rolling stock (locomotives, wagons, and train sets) that must be combined into trains to perform rolling stock rotations. This train composition is a special characteristic of railway operations that distinguishes rolling stock rotation planning from the vehicle scheduling problems prevalent in other industries. DB models train compositions using hyperarcs. The resulting hypergraph models are ad-dressed using a novel coarse-to-fine method that implements a hierarchical column genera-tion over three levels of detail. This algorithm is the mathematical core of DB’s fleet em-ployment optimization (FEO) system for rolling stock rotation planning. FEO’s impact within DB’s planning departments has been revolutionary. DB has used it to support the company’s procurements of its newest high-speed passenger train fleet and its intermodal cargo locomotive fleet for cross-border operations. FEO is the key to successful tendering in regional transport and to construction site management in daily operations. DB’s plan-ning departments appreciate FEO’s high-quality results, ability to reoptimize (quickly), and ease of use. Both employees and customers benefit from the increased regularity of operations. DB attributes annual savings of 74 million euro, an annual reduction of 34,000 tons of CO2 emissions, and the elimination of 600 coupling operations in cross-border operations to the implementation of FEO. Y1 - 2021 U6 - https://doi.org/10.1287/inte.2020.1069 VL - 51 IS - 1 SP - 42 EP - 62 ER - TY - JOUR A1 - Sahin, Guvenc A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Multi-period line planning with resource transfers JF - Transportation Research Part C: Emerging Technologies N2 - Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions. Y1 - 2020 U6 - https://doi.org/10.1016/j.trc.2020.102726 VL - 119 SP - 102726 ER - TY - THES A1 - Löbel, Fabian T1 - Implementing the Network Simplex for Hypergraphs N2 - The well-known network simplex algorithm is a powerful tool to solve flow problems on graphs. Based on a recent dissertation by Isabel Beckenbach, we develop the necessary theory to extend the network simplex to capacitated flow problems on hypergraphs and implement this new variant. We then attempt to solve instances arising from real-life vehicle rotation planning problems. Y1 - 2020 ER - TY - JOUR A1 - Beckenbach, Isabel T1 - Von Graphen zu Hypergraphen JF - OR News Y1 - 2020 SN - 1437-2045 IS - 70 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 -