@misc{BreugemBorndoerferSchlechteetal.2019, author = {Breugem, Thomas and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Schulz, Christof}, title = {A Three-Phase Heuristic for Cyclic Crew Rostering with Fairness Requirements}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74297}, year = {2019}, abstract = {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.}, language = {en} } @misc{BorndoerferErolGraffagninoetal.2010, author = {Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Schlechte, Thomas and Swarat, Elmar}, title = {Aggregation Methods for Railway Networks}, organization = {Zuse Institut Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11881}, number = {10-23}, year = {2010}, abstract = {In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run.}, language = {en} } @misc{BorndoerferErolGraffagninoetal.2010, author = {Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Schlechte, Thomas and Swarat, Elmar}, title = {Optimizing the Simplon Railway Corridor}, organization = {Zuse Institut Berlin}, issn = {1438-0064}, doi = {10.1007/s10479-012-1260-9}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11892}, number = {10-24}, year = {2010}, abstract = {This paper presents a case study on a railway timetable optimization for the very dense Simplon corridor, a major railway connection in the Alps between Switzerland and Italy. Starting from a detailed microscopic network as it is used in railway simulation, the data is transformed by an automatic procedure to a less detailed macroscopic network, that is sufficient for the purpose of capacity planning and amenable to state-of-the-art integer programming optimization methods. In this way, the macroscopic railway network is saturated with trains. Finally, the corresponding timetable is re-transformed to the microscopic level in such a way that it can be operated without any conflicts among the slots. Using this integer programming based micro-macro aggregation-disaggregation approach, it becomes for the first time possible to generate a profit maximal and conflict free timetable for the complete Simplon corridor over an entire day by a simultaneous optimization of all trains requests. This also allows to to undertake a sensitivity analysis of various problem parameters.}, language = {en} } @article{SchlechteBorndoerferEroletal.2011, author = {Schlechte, Thomas and Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Swarat, Elmar}, title = {Micro-macro transformation of railway networks}, volume = {1}, journal = {Journal of Rail Transport Planning \& Management}, number = {1}, doi = {10.1016/j.jrtpm.2011.09.001}, pages = {38 -- 48}, year = {2011}, abstract = {In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run.}, language = {en} } @article{BorndoerferErolGraffagninoetal.2012, author = {Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Schlechte, Thomas and Swarat, Elmar}, title = {Optimizing the Simplon railway corridor}, volume = {218}, journal = {Annals of Operations Research}, number = {1}, edition = {Annals of Operations Research}, publisher = {Springer US}, doi = {10.1007/s10479-012-1260-9}, pages = {93 -- 106}, year = {2012}, language = {en} } @article{BreugemSchlechteSchulzetal.2023, author = {Breugem, Thomas and Schlechte, Thomas and Schulz, Christof and Bornd{\"o}rfer, Ralf}, title = {A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem}, volume = {154}, journal = {Computers \& Operations Research}, doi = {10.1016/j.cor.2023.106186}, pages = {106186}, year = {2023}, abstract = {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.}, language = {en} } @misc{BorndoerferGrimmReutheretal.2016, 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}, year = {2016}, 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{HarrodSchlechte2013, author = {Harrod, Steven and Schlechte, Thomas}, title = {A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations}, volume = {54}, journal = {Transportation Research Part E: Logistics and Transportation Review}, doi = {10.1016/j.tre.2013.04.003}, pages = {50 -- 66}, year = {2013}, abstract = {Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, RCHF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and RCHF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall.}, language = {en} } @misc{SahinAhmadiBorndoerferetal.2019, author = {Sahin, Guvenc and Ahmadi, Amin and Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Multi-Period Line Planning with Resource Transfers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74662}, year = {2019}, abstract = {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 transfer of resources during a finite length planning horizon of multiple periods. 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 line type designs and question the choice of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.}, language = {en} } @misc{GrimmBorndoerferSchlechte2019, 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}, year = {2019}, 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} }