@misc{Bushe2021, type = {Master Thesis}, author = {Bushe, Julian}, title = {Rolling Stock Rotation Optimization with Maintenance Paths}, year = {2021}, abstract = {Die Planung vom Zuguml{\"a}ufen ist eine der wichtigsten Aufgaben f{\"u}r Eisenbahnun- ternehmen. Dabei spielt auch die Einhaltung von vorgegebenen Wartungsintervallen eine zentrale Rolle f{\"u}r die Sicherheit und Zuverl{\"a}ssigkeit der Schienenfahrzeuge. Wir zeigen, wie man dieses Umlaufplanungsproblem unter Beachtung von Wartungsbe- dingungen mathematisch formuliert, modelliert und l{\"o}st — sowohl in der Theorie als auch im Anwendungsfall mit Szenarien der DB Fernverkehr AG, einer Konzern- tochter der Deutschen Bahn f{\"u}r den Schienenpersonenfernverkehr. Markus Reuther hat sich in seiner Dissertation [11] mit diesem Problem besch{\"a}ftigt und es mit Hilfe eines passenden Hypergraphen als gemischt-ganzzahliges Programm modelliert. Neben der Modellierung pr{\"a}sentiert Reuther in seiner Arbeit neuartige algorithmische Ideen, darunter den sogenannten Coarse-to-Fine -Ansatz, bei dem zun{\"a}chst Teile des Problems auf einer weniger detaillierten ( coarse ) Ebene gel{\"o}st werden und diese L{\"o}sung dann verwendet wird, um auf effiziente Art und Weise eine L{\"o}sung f{\"u}r das urspr{\"u}ngliche Problem zu finden. Zur Wartungsplanung nutzt Reuther einen Fluss im Hypergraphen, der den Ressourcenverbrauch der Fahrzeuge modelliert. In der linearen Relaxierung des Modells f{\"u}hrt dies dazu, dass die Zahl der notwendigen Wartungen systematisch untersch{\"a}tzt wird. Dadurch bleibt in vielen F{\"a}llen eine große L{\"u}cke zwischen dem Zielfunktionswert einer optimalen L{\"o}sung des ganzzahligen Problems und der untere Schranke, die uns die lineare Relaxierung liefert. Wir nehmen uns in dieser Arbeit dieses Problems an. Wir entwickeln ein auf Pfaden basierendes ganzzahliges Modell f{\"u}r das Umlaufplanungsproblem und zeigen, dass die untere Schranke mindestens so scharf oder sch{\"a}rfer ist als die untere Schranke, die das Modell von Reuther liefert. Um das Modell zu l{\"o}sen, entwickeln wir einen Algorithmus, der Spaltengenerierung mit dem Coarse-to-Fine-Ansatz von Reuther verbindet. Weiterhin entwickeln wir eine Spaltenauswahlregel zur Beschleunigung des Algorithmus. Das Modell und alle in der Arbeit vorgestellten Algorithmen wur- den im Rahmen der Arbeit implementiert und mit Anwendungsszenarien der DB Fernverkehr AG getestet. Unsere Tests zeigen, dass unser Modell f{\"u}r fast alle Szena- rien deutlich sch{\"a}rfere untere Schranken liefert als das Modell von Reuther. In den getesteten Instanzen konnten wir durch die Verbesserung der unteren Schranke bis zu 99\% der Optimalit{\"a}tsl{\"u}cke schließen. In einem Drittel der F{\"a}lle konnten wir durch unseren Ansatz auch f{\"u}r das ganzzahlige Programm verbesserte Zielfunktionswerte erreichen}, language = {en} } @misc{MasingLindnerEbert2023, author = {Masing, Berenike and Lindner, Niels and Ebert, Patricia}, title = {Forward and Line-Based Cycle Bases for Periodic Timetabling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89731}, year = {2023}, abstract = {The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks, and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.}, language = {en} } @article{LindnerMasing2025, author = {Lindner, Niels and Masing, Berenike}, title = {On the split closure of the periodic timetabling polytope}, journal = {Mathematical Programming}, publisher = {Springer Science and Business Media LLC}, issn = {0025-5610}, doi = {10.1007/s10107-025-02220-5}, year = {2025}, abstract = {The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P = NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances.}, language = {en} } @misc{LindnerMehlBartoszuketal.2025, author = {Lindner, Niels and Mehl, Lukas and Bartoszuk, Karolina and Berendes, Sarah and Zittel, Janina}, title = {Demand Uncertainty in Energy Systems: Scenario Catalogs vs. Integrated Robust Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-102404}, year = {2025}, abstract = {Designing efficient energy systems is indispensable for shaping a more sustainable society. This involves making infrastructure investment decisions that must be valid for a long-term time horizon. While energy system optimization models constitute a powerful technique to support planning decisions, they need to cope with inherent uncertainty. For example, predicting future demand on a scale of decades is not only an intricate challenge in itself, but small fluctuations in such a forecast might also largely impact the layout of a complex energy system. In this paper, we compare two methodologies of capturing demand uncertainty for linear-programming based energy system optimization models. On one hand, we generate and analyze catalogs of varying demand scenarios, where each individual scenario is considered independently, so that the optimization produces scenario-specific investment pathways. On the other hand, we make use of robust linear programming to meet the demand of all scenarios at once. Since including a multitude of scenarios increases the size and complexity of the optimization model, we will show how to use warm-starting approaches to accelerate the computation process, by exploiting the similar structure of the linear program across different demand inputs. This allows to integrate a meaningful number of demand scenarios with fully-fledged energy system models. We demonstrate the practical use of our methods in a case study of the Berlin-Brandenburg area in Germany, a region that contains both a metropolitan area and its rural surroundings. As a backbone, we use the open-source framework oemof to create a sector-coupled optimization model for planning an energy system with up to 100\% reduction of greenhouse gas emissions. This model features a fine-grained temporal resolution of one hour for the full year 2050. We consider uncertainty in demand for electricity, hydrogen, natural gas, central, and decentral heat. Based on our computations, we analyze the trade-offs in terms of quality and computation time for scenario catalogs and the robust optimization approach. We further demonstrate that our procedure provides a valuable strategy for decision makers to gain insight on the robustness and sensitivity of solutions regarding demand variability.}, language = {en} } @misc{Lindner2025, author = {Lindner, Niels}, title = {A Multi-Commodity Flow Heuristic for Integrated Periodic Timetabling for Railway Construction Sites}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99449}, year = {2025}, abstract = {Rescheduling a railway system comprises many aspects, such as line planning, timetabling, track allocation, and vehicle scheduling. For periodic timetables, these features can be integrated into a single mixed-integer program extending the Periodic Event Scheduling Problem (PESP) with a routing component. We develop a multi-commodity-flow-based heuristic that allows to compute better solutions faster than a black-box MIP approach on real construction site scenarios on the S-Bahn Berlin network.}, language = {en} } @inproceedings{LoebelBorndoerferWeider2025, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Non-linear Battery Behavior in Electric Vehicle Scheduling Problems}, booktitle = {Operations Research Proceedings 2023. OR 2023.}, editor = {Voigt, Guido and Fliedner, Malte and Haase, Knut and Br{\"u}ggermann, Wolfgang and Hoberg, Kai and Meissner, Joern}, publisher = {Springer Nature Switzerland}, address = {Cham}, isbn = {9783031584046}, issn = {2731-040X}, doi = {10.1007/978-3-031-58405-3_53}, pages = {415 -- 421}, year = {2025}, abstract = {The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve.}, language = {en} } @misc{LindnerLiebchen2025, author = {Lindner, Niels and Liebchen, Christian}, title = {A two-stage model for periodic timetabling with fixed line activities}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101234}, year = {2025}, abstract = {The timetable is a central pillar of any public transportation system. Constructing and optimizing periodic timetables in terms of passenger comfort and operational efficiency leads to NP-hard optimization problems that are also computationally challenging in applications. The Periodic Event Scheduling Problem (PESP) as standard mathematical tool benefits from its succinct formulation and rich combinatorial structure, but suffers from poor linear programming relaxations and weak dual bounds. These difficulties persist in a reduced version, where driving and dwelling activities of the lines are assumed to be fixed. In this case, fixing the initial departure time of each line fully determines the timetable, and for each pair of lines, the resulting (weighted) transfer durations can be expressed in terms of a piecewise linear non-convex function in terms of the difference of the initial times. When the number of activities between two lines is bounded, this function can be computed in polynomial time. By inserting precomputed piecewise linear functions into a mixed-integer program with the initial departure times as variables, we introduce an equivalent formulation for reduced PESP instances. The model bears analogies with quadratic semi-assignment approaches and offers alternative ways to compute primal and dual bounds. We evaluate the computational behavior of our approach on realistic benchmarking instances.}, language = {en} } @inproceedings{LindnerMehlBartoszuketal.2025, author = {Lindner, Niels and Mehl, Lukas and Bartoszuk, Karolina and Berendes, Sarah and Zittel, Janina}, title = {Demand Uncertainty in Energy Systems: Scenario Catalogs vs. Integrated Robust Optimization}, booktitle = {Proceedings of the 38th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems}, year = {2025}, abstract = {Designing efficient energy systems is indispensable for shaping a more sustainable society. This involves making infrastructure investment decisions that must be valid for a long-term time horizon. While energy system optimization models constitute a powerful technique to support planning decisions, they need to cope with inherent uncertainty. For example, predicting future demand on a scale of decades is not only an intricate challenge in itself, but small fluctuations in such a forecast might also largely impact the layout of a complex energy system. In this paper, we compare two methodologies of capturing demand uncertainty for linear-programming based energy system optimization models. On one hand, we generate and analyze catalogs of varying demand scenarios, where each individual scenario is considered independently, so that the optimization produces scenario-specific investment pathways. On the other hand, we make use of robust linear programming to meet the demand of all scenarios at once. Since including a multitude of scenarios increases the size and complexity of the optimization model, we will show how to use warm-starting approaches to accelerate the computation process, by exploiting the similar structure of the linear program across different demand inputs. This allows to integrate a meaningful number of demand scenarios with fully-fledged energy system models. We demonstrate the practical use of our methods in a case study of the Berlin-Brandenburg area in Germany, a region that contains both a metropolitan area and its rural surroundings. As a backbone, we use the open-source framework oemof to create a sector-coupled optimization model for planning an energy system with up to 100\% reduction of greenhouse gas emissions. This model features a fine-grained temporal resolution of one hour for the full year 2050. We consider uncertainty in demand for electricity, hydrogen, natural gas, central, and decentral heat. Based on our computations, we analyze the trade-offs in terms of quality and computation time for scenario catalogs and the robust optimization approach. We further demonstrate that our procedure provides a valuable strategy for decision makers to gain insight on the robustness and sensitivity of solutions regarding demand variability.}, language = {en} } @misc{LindnerLiebchen2021, author = {Lindner, Niels and Liebchen, Christian}, title = {Timetable Merging for the Periodic Event Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81587}, year = {2021}, abstract = {We propose a new mixed integer programming based heuristic for computing new benchmark primal solutions for instances of the PESPlib. The PESPlib is a collection of instances for the Periodic Event Scheduling Problem (PESP), comprising periodic timetabling problems inspired by real-world railway timetabling settings, and attracting several international research teams during the last years. We describe two strategies to merge a set of good periodic timetables. These make use of the instance structure and minimum weight cycle bases, finally leading to restricted mixed integer programming formulations with tighter variable bounds. Implementing this timetable merging approach in a concurrent solver, we improve the objective values of the best known solutions for the smallest and largest PESPlib instances by 1.7 and 4.3 percent, respectively.}, language = {en} } @inproceedings{LindnerLiebchen2020, author = {Lindner, Niels and Liebchen, Christian}, title = {Determining all integer vertices of the PESP polytope by flipping arcs}, volume = {85}, booktitle = {20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)}, editor = {Huisman, Dennis and Zaroliagis, Christos D.}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2020.5}, pages = {5:1 -- 5:18}, year = {2020}, abstract = {We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. We finally present better dual bounds for the smallest and largest instance of the benchmarking library PESPlib.}, 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} }