@inproceedings{BlancoBorndoerferMaristanydelasCasas2022, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Maristany de las Casas, Pedro}, title = {An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles}, volume = {106}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, doi = {10.4230/OASIcs.ATMOS.2022.1}, pages = {1:1 -- 1:15}, year = {2022}, abstract = {The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A∗ heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances.}, language = {en} } @article{MasingLindnerBorndoerfer2022, author = {Masing, Berenike and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {The price of symmetric line plans in the Parametric City}, volume = {166}, journal = {Transportation Research Part B: Methodological}, doi = {10.1016/j.trb.2022.10.009}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88613}, pages = {419 -- 443}, year = {2022}, abstract = {We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. We prove that the symmetry gap is small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations.}, language = {de} } @article{Beckenbach2020, author = {Beckenbach, Isabel}, title = {Von Graphen zu Hypergraphen}, journal = {OR News}, number = {70}, issn = {1437-2045}, year = {2020}, language = {en} } @inproceedings{GrimmBorndoerferBushe2023, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Bushe, Julian}, title = {Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization}, 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}, year = {2023}, 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{BorndoerferGrimmSchade2023, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Schade, Stanley}, title = {A Robustness Analysis of Long Distance Train Crew Schedules in Germany}, 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}, year = {2023}, 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} } @inproceedings{BortolettoLindnerMasing2022, author = {Bortoletto, Enrico and Lindner, Niels and Masing, Berenike}, title = {Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling}, volume = {106}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, doi = {10.4230/OASIcs.ATMOS.2022.3}, pages = {3:1 -- 3:19}, year = {2022}, abstract = {Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [Bornd{\"o}rfer et al., 2020]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [Bortoletto et al., 2022]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances.}, language = {en} } @inproceedings{BortolettoLindnerMasing2023, author = {Bortoletto, Enrico and Lindner, Niels and Masing, Berenike}, title = {Periodic Timetabling with Cyclic Order Constraints}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, doi = {10.4230/OASIcs.ATMOS.2023.7}, pages = {7:1 -- 7:18}, year = {2023}, abstract = {Periodic timetabling for highly utilized railway networks is a demanding challenge. We formulate an infrastructure-aware extension of the Periodic Event Scheduling Problem (PESP) by requiring that not only events, but also activities using the same infrastructure must be separated by a minimum headway time. This extended problem can be modeled as a mixed-integer program by adding constraints on the sum of periodic tensions along certain cycles, so that it shares some structural properties with standard PESP. We further refine this problem by fixing cyclic orders at each infrastructure element. Although the computational complexity remains unchanged, the mixed-integer programming model then becomes much smaller. Furthermore, we also discuss how to find a minimal subset of infrastructure elements whose cyclic order already prescribes the order for the remaining parts of the network, and how cyclic order information can be modeled in a mixed-integer programming context. In practice, we evaluate the impact of cyclic orders on a real-world instance on the S-Bahn Berlin network, which turns out to be computationally fruitful.}, language = {en} } @inproceedings{MasingLindnerLiebchen2023, author = {Masing, Berenike and Lindner, Niels and Liebchen, Christian}, title = {Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, doi = {10.4230/OASIcs.ATMOS.2023.5}, pages = {5:1 -- 5:15}, year = {2023}, abstract = {We consider maintenance sites for urban rail systems, where unavailable tracks typically require changes to the regular timetable, and often even to the line plan. In this paper, we present an integrated mixed-integer linear optimization model to compute an optimal line plan that makes best use of the available tracks, together with a periodic timetable, including its detailed routing on the tracks within the stations. The key component is a flexible, turn-sensitive event-activity network that allows to integrate line planning and train routing using a track choice extension of the Periodic Event Scheduling Problem (PESP). Major goals are to maintain as much of the regular service as possible, and to keep the necessary changes rather local. Moreover, we present computational results on real construction site scenarios on the S-Bahn Berlin network. We demonstrate that this integrated problem is indeed solvable on practically relevant instances.}, language = {en} } @inproceedings{Masing2022, author = {Masing, Berenike}, title = {Optimal Line Planning in the Parametric City}, booktitle = {Operations Research Proceedings 2021. OR 2021.}, editor = {Trautmann, Norbert and Dr{\"a}gi, Mario}, publisher = {Springer, Cham}, isbn = {978-3-031-08623-6}, doi = {10.1007/978-3-031-08623-6_7}, pages = {39 -- 44}, year = {2022}, abstract = {We formulate the line planning problem in public transport as a mixed integer linear program (MILP), which selects both passenger and vehicle routes, such that travel demands are met with respect to minimized travel times for both operators and users. We apply MILP to the Parametric City, a generic city model developed by Fielbaum et al. [2]. While the infrastructure graph and demand are entirely rotation symmetric, asymmetric optimal line plans can occur. Using group theory, we analyze the properties of symmetric solutions and introduce a symmetry gap to measure their deviation of the optimum. We also develop a 1+1+2√g-approximation algorithm, depending only on the cost related parameter g. Supported by computational experiments, we conclude that in practice symmetric line plans provide good solutions for the line planning problem in the Parametric City.}, language = {en} } @inproceedings{LindnervanLieshout2022, author = {Lindner, Niels and van Lieshout, Rolf}, title = {Benders Decomposition for the Periodic Event Scheduling Problem}, booktitle = {Operations Research Proceedings 2021}, publisher = {Springer International Publishing}, address = {Cham}, doi = {10.1007/978-3-031-08623-6_43}, pages = {289 -- 294}, year = {2022}, abstract = {The Periodic Event Scheduling Problem (PESP) is the central mathematical model behind the optimization of periodic timetables in public transport. We apply Benders decomposition to the incidence-based MIP formulation of PESP. The resulting formulation exhibits particularly nice features: The subproblem is a minimum cost network flow problem, and feasibility cuts are equivalent to the well-known cycle inequalities by Odijk. We integrate the Benders approach into a branch-and-cut framework, and assess the performance of this method on instances derived from the benchmarking library PESPlib.}, language = {en} }