@misc{LindnerBartoszukDebguptaetal.2024, author = {Lindner, Niels and Bartoszuk, Karolina and Debgupta, Srinwanti and Gering, Marie-Claire and Muschner, Christoph and Zittel, Janina}, title = {Warm-starting modeling to generate alternatives for energy transition paths in the Berlin-Brandenburg area}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-97835}, year = {2024}, abstract = {Energy system optimization models are key to investigate energy transition paths towards a decarbonized future. Since this approach comes with intrinsic uncertainties, it is insufficient to compute a single optimal solution assuming perfect foresight to provide a profound basis for decision makers. The paradigm of modeling to generate alternatives enables to explore the near-optimal solution space to a certain extent. However, large-scale energy models require a non-negligible computation time to be solved. We propose to use warm start methods to accelerate the process of finding close-to-optimal alternatives. In an extensive case study for the energy transition of the Berlin-Brandenburg area, we make use of the sector-coupled linear programming oemof-B3 model to analyze a scenario for the year 2050 with a resolution of one hour and 100\% reduction of greenhouse gas emissions. We demonstrate that we can actually achieve a significant computational speedup.}, language = {en} } @misc{LindnerMasing2024, author = {Lindner, Niels and Masing, Berenike}, title = {SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-94644}, year = {2024}, abstract = {Periodic timetabling is a challenging planning task in public transport. As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turnarounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network.}, language = {en} } @inproceedings{LindnerMasingLiebchen2024, author = {Lindner, Niels and Masing, Berenike and Liebchen, Christian}, title = {Integrierte Baufahrplanoptimierung auf dem Netz der S-Bahn Berlin}, volume = {002/140}, booktitle = {HEUREKA'24 - Optimierung in Verkehr und Transport}, year = {2024}, abstract = {Zur Instandhaltung von Eisenbahnnetzen sind regelm{\"a}ßig Baumaßnahmen erforderlich. Diese erfordern stets Anpassungen der Fahrpl{\"a}ne. Um den Fahrg{\"a}sten trotz der Baumaßnahme weiterhin einen m{\"o}glichst großen Teil des Regelangebotes bieten zu k{\"o}nnen, bewegen sich die resultierenden Baufahrpl{\"a}ne insbesondere in Schnellbahnnetzen mit ihren dichten Zugfolgen h{\"a}ufig nahe der Kapazit{\"a}tsgrenze der Infrastruktur. Etablierte Verfahren zur Taktfahrplanoptimierung k{\"o}nnen diesen Anforderungen nicht gen{\"u}gen, da in der Praxis Anpassungen von Laufwegen der Linien, sowie der Gleisbelegungen h{\"a}ufig Teil der realisierten L{\"o}sungen sind. F{\"u}r diese Aufgabe haben die Autoren zuletzt ein Optimierungsmodell vorgestellt, welches diese M{\"o}glichkeiten aussch{\"o}pft. In dem vorliegenden Beitrag wird erstmalig dessen Anwendung auf ein unmittelbar der Praxis der Baufahrplanung entnommenes Beispiel aus dem Netz der Berliner S-Bahn im Detail beschrieben.}, language = {de} } @inproceedings{LindnerMasing2024, author = {Lindner, Niels and Masing, Berenike}, title = {SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice}, booktitle = {hEART 2024: 12th Symposium of the European Association for Research in Transportation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98066}, year = {2024}, abstract = {Periodic timetabling is a challenging planning task in public transport. As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turn-arounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network.}, language = {de} } @misc{EbertMasingLindneretal.2024, author = {Ebert, Patricia and Masing, Berenike and Lindner, Niels and Gleixner, Ambros}, title = {Sorting Criteria for Line-based Periodic Timetabling Heuristics}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-97826}, year = {2024}, abstract = {It is well-known that optimal solutions are notoriously hard to find for the Periodic Event Scheduling Problem (PESP), which is the standard mathematical formulation to optimize periodic timetables in public transport. We consider a class of incremental heuristics that have been demonstrated to be effective by Lindner and Liebchen (2023), however, for only one fixed sorting strategy of lines along which a solution is constructed. Thus, in this paper, we examine a variety of sortings based on the number, weight, weighted span, and lower bound of arcs, and test for each setting various combinations of the driving, dwelling, and transfer arcs of lines. Additionally, we assess the impact on the incremental extension of the event-activity network by minimizing resp. maximizing a connectivity measure between subsets of lines. We compare our 27 sortings on the railway instances of the benchmarking library PESPlib within the ConcurrentPESP solver framework. We are able to find five new incumbent solutions, resulting in improvements of up to 2\%.}, language = {en} } @inproceedings{BortolettovanLieshoutMasingetal.2024, author = {Bortoletto, Enrico and van Lieshout, Rolf Nelson and Masing, Berenike and Lindner, Niels}, title = {Periodic Event Scheduling with Flexible Infrastructure Assignment}, volume = {123}, booktitle = {24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)}, doi = {10.4230/OASIcs.ATMOS.2024.4}, pages = {4:1 -- 4:18}, year = {2024}, abstract = {We present novel extensions of the Periodic Event Scheduling Problem (PESP) that integrate the assignment of activities to infrastructure elements. An application of this is railway timetabling, as station and platform capacities are limited and need to be taken into account. We show that an assignment of activities to platforms can always be made periodic, and that it can be beneficial to allow larger periods for the assignment than for the timetable. We present mixed-integer programming formulations for the general problem, as well as for the practically relevant case when multiple platforms can be considered equivalent, for which we present a bipartite matching approach. We finally test and compare these models on real-world instances.}, language = {en} } @article{EulerLindnerBorndoerfer2024, author = {Euler, Ricardo and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {Price optimal routing in public transportation}, volume = {13}, journal = {EURO Journal on Transportation and Logistics}, publisher = {Elsevier BV}, issn = {2192-4376}, doi = {10.1016/j.ejtl.2024.100128}, pages = {1 -- 15}, year = {2024}, language = {en} }