TY - GEN A1 - Borndörfer, Ralf A1 - Langenhan, Andreas A1 - Löbel, Andreas A1 - Schulz, Christof A1 - Weider, Steffen T1 - Duty Scheduling Templates N2 - We propose duty templates as a novel concept to produce similar duty schedules for similar days of operation in public transit. Duty templates can conveniently handle various types of similarity requirements, and they can be implemented with ease using standard algorithmic techniques. They have produced good results in practice. T3 - ZIB-Report - 12-09 KW - duty scheduling KW - duty templates Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14699 SN - 1438-0064 ER - TY - JOUR A1 - Langenhan, Andreas A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Schulz, Christof A1 - Weider, Steffen ED - Muñoz, J. C. ED - Voß, S. T1 - Duty Scheduling Templates JF - Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12) N2 - We propose duty templates as a novel concept to produce similar duty schedules for similar days of operation in public transit. Duty templates can conveniently handle various types of similarity requirements, and they can be implemented with ease using standard algorithmic techniques. They have produced good results in practice. Y1 - 2012 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Swarat, Elmar A1 - Weider, Steffen T1 - Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue T2 - Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015) N2 - Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively. Y1 - 2015 ER - TY - CHAP A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Sinan A1 - Tesch, Alexander T1 - Conflict-Free Railway Track Assignment at Depots T2 - Proceedings of the IAROR conference RailLille N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables. Y1 - 2017 ER - TY - GEN A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Sinan A1 - Tesch, Alexander T1 - Conflict-Free Railway Track Assignment at Depots N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables. T3 - ZIB-Report - 17-23 KW - Depot Planning KW - Railway Track Assignment Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-63843 SN - 1438-0064 ER - TY - JOUR A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Senan A1 - Tesch, Alexander T1 - Conflict-free railway track assignment at depots JF - Journal of Rail Transport Planning & Management N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. One aspect of managing rolling stock is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with a fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we show that the TAP is NP-hard and present two integer programming models for solving the TAP. We compare both models on a theoretical level. Moreover, to our knowledge, we consider the first approach that integrates track lengths along with the three most common types of parking tracks FIFO, LIFO and FREE tracks in a common model. Furthermore, to optimize against uncertainty in the arrival times of the trains we extend our models by stochastic and robust modeling techniques. We conclude by giving computational results for both models, observing that they perform well on real timetables. Y1 - 2018 U6 - https://doi.org/10.1016/j.jrtpm.2017.12.004 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Swarat, Elmar A1 - Weider, Steffen T1 - Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue N2 - Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively. T3 - ZIB-Report - 15-44 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56070 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 - Breugem, Thomas A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Schulz, Christof T1 - A Three-Phase Heuristic for Cyclic Crew Rostering with Fairness Requirements N2 - In this paper, we consider the Cyclic Crew Rostering Problem with Fairness Requirements (CCRP-FR). In this problem, attractive cyclic rosters have to be constructed for groups of employees, considering multiple, a priori determined, fairness levels. The attractiveness follows from the structure of the rosters (e.g., sufficient rest times and variation in work), whereas fairness is based on the work allocation among the different roster groups. We propose a three-phase heuristic for the CCRP-FR, which combines the strength of column generation techniques with a large-scale neighborhood search algorithm. The design of the heuristic assures that good solutions for all fairness levels are obtained quickly, and can still be further improved if additional running time is available. We evaluate the performance of the algorithm using real-world data from Netherlands Railways, and show that the heuristic finds close to optimal solutions for many of the considered instances. In particular, we show that the heuristic is able to quickly find major improvements upon the current sequential practice: For most instances, the heuristic is able to increase the attractiveness by at least 20% in just a few minutes. T3 - ZIB-Report - 19-43 KW - Crew Planning KW - Column Generation KW - Variable-Depth Neighborhood Search Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74297 SN - 1438-0064 ER - TY - CHAP A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Schulz, Christof A1 - Weider, Steffen T1 - The Rolling Stock Rotation Planning Problem under Revenue Considerations T2 - Proceedings of the Rail Transport Demand Management Conference N2 - 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. Y1 - 2018 ER - TY - GEN A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Schulz, Christof A1 - Weider, Steffen T1 - The Rolling Stock Rotation Planning Problem under Revenue Considerations N2 - 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. T3 - ZIB-Report - 19-01 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71339 SN - 1438-0064 ER - TY - GEN A1 - Schlechte, Thomas A1 - Blome, Christian A1 - Gerber, Stefan A1 - Hauser, Stefan A1 - Kasten, Jens A1 - Müller, Gilbert A1 - Schulz, Christof A1 - Thüring, Michel A1 - Weider, Steffen T1 - The Bouquet of Features in Rolling Stock Rotation Planning T2 - Conference Proceedings RailBelgrade 2023 N2 - Rolling stock is one of the major assets for a railway transportation company. Hence, their utilization should be as efficiently and effectively as possible. Railway undertakings are facing rolling stock scheduling challenges in different forms - from rather idealized weekly strategic problems to very concrete operational ones. Thus, a vast of optimization models with different features and objectives exist. Thorlacius et al. (2015) provides a comprehensive and valuable collection on technical requirements, models, and methods considered in the scientific literature. We contribute with an update including recent works. The main focus of the paper is to present a classification and elaboration of the major features which our solver R-OPT is able to handle. Moreover, the basic optimization model and algorithmic ingredients of R-OPT are discussed. Finally, we present computational results for a cargo application at SBB CARGO AG and other railway undertakings for passenger traffic in Europe to show the capabilities of R-OPT. Y1 - 2023 UR - https://easychair.org/publications/preprint/Nms6 ER - TY - JOUR A1 - Breugem, Thomas A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Borndörfer, Ralf T1 - A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem JF - Computers & Operations Research N2 - The Fairness-Oriented Crew Rostering Problem (FCRP) considers the joint optimization of attractiveness and fairness in cyclic crew rostering. Like many problems in scheduling and logistics, the combinatorial complexity of cyclic rostering causes exact methods to fail for large-scale practical instances. In case of the FCRP, this is accentuated by the additionally imposed fairness requirements. Hence, heuristic methods are necessary. We present a three-phase heuristic for the FCRP combining column generation techniques with variable-depth neighborhood search. The heuristic exploits different mathematical formulations to find feasible solutions and to search for improvements. We apply our methodology to practical instances from Netherlands Railways (NS), the main passenger railway operator in the Netherlands Our results show the three-phase heuristic finds good solutions for most instances and outperforms a state-of-the-art commercial solver. Y1 - 2023 U6 - https://doi.org/https://doi.org/10.1016/j.cor.2023.106186 VL - 154 ER -