@article{RiedmuellerLindner2025, author = {Riedm{\"u}ller, Stephanie and Lindner, Niels}, title = {Column Generation for Periodic Timetabling}, arxiv = {http://arxiv.org/abs/2510.12466}, year = {2025}, abstract = {Periodic timetabling for public transportation networks is typically modelled as a Periodic Event Scheduling Problem (PESP). Solving instances of the benchmark library PESPlib to optimality continues to pose a challenge. As a further approach towards this goal, we remodel the problem by a time discretization of the underlying graph and consider arc-based as well as path-based integer programming formulations. For the path-based case, we use cycles on the graph expansion of the operational lines as variables and, therefore, include more of the problem inherent structure into the model. A consequence is the validity of several known inequalities and a lower bound on the LP-relaxation, that is the best known to date. As an extension we integrate passenger routing into the new model. The proposed models have an advantage in the linear programming relaxation, on the one hand, but have an increased problem size, on the other hand. We define the corresponding pricing problems for the use of column generation to handle the size. Both models are practically tested on different problem instances.}, language = {en} } @inproceedings{LoebelLindner2025, author = {L{\"o}bel, Fabian and Lindner, Niels}, title = {A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing}, volume = {137}, booktitle = {25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)}, editor = {Sauer, Jonas and Schmidt, Marie}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-404-8}, issn = {2190-6807}, doi = {10.4230/OASIcs.ATMOS.2025.2}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-247580}, pages = {2:1 -- 2:19}, year = {2025}, abstract = {We offer a geometric perspective on the problem of integrated periodic timetabling and passenger routing in public transport. Inside the space of periodic tensions, we single out those regions, where the same set of paths provides shortest passenger routes. This results in a polyhedral subdivision, which we combine with the known decomposition by polytropes. On each maximal region of the common refinement, the integrated problem is solvable in polynomial time. We transform these insights into a new geometry-driven primal heuristic, integrated tropical neighborhood search (ITNS). Computationally, we compare implementations of ITNS and the integrated (restricted) modulo network simplex algorithm on the TimPassLib benchmark set, and contribute better solutions in terms of total travel time for all but one of the twenty-five instances for which a proven optimal solution is not yet known.}, language = {en} } @article{vanLieshoutLindner2025, author = {van Lieshout, Rolf and Lindner, Niels}, title = {A Compact Cycle Formulation for the Multiperiodic Event Scheduling Problem}, arxiv = {http://arxiv.org/abs/2507.17566}, year = {2025}, abstract = {The Periodic Event Scheduling Problem (PESP) is a fundamental model in periodic timetabling for public transport systems, assuming a common period across all events. However, real-world networks often feature heterogeneous service frequencies. This paper studies the Multiperiodic Event Scheduling Problem (MPESP), a generalization of PESP that allows each event to recur at its own individual period. While more expressive, MPESP presents new modeling challenges due to the loss of a global period. We present a cycle-based formulation for MPESP that extends the strongest known formulation for PESP and, in contrast to existing approaches, is valid for any MPESP instance. Crucially, the formulation requires a cycle basis derived from a spanning tree satisfying specific structural properties, which we formalize and algorithmically construct, extending the concept of sharp spanning trees to rooted instances. We further prove a multiperiodic analogue of the cycle periodicity property. Our new formulation solves nearly all tested instances, including several large-scale real-world public transport networks, to optimality or with small optimality gaps, dramatically outperforming existing arc-based models. The results demonstrate the practical potential of MPESP in capturing heterogeneous frequencies without resorting to artificial event duplication.}, language = {en} } @article{MaristanydelasCasasSedenoNodaBorndoerfer2025, author = {Maristany de las Casas, Pedro and Sede{\~n}o-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {New Dynamic Programming Algorithm for the Multiobjective Minimum Spanning Tree Problem}, volume = {173}, journal = {Computers \& Operations Research}, arxiv = {http://arxiv.org/abs/2306.16203}, doi = {10.1016/j.cor.2024.106852}, pages = {106852}, year = {2025}, abstract = {The Multiobjective Minimum Spanning Tree (MO-MST) problem is a variant of the Minimum Spanning Tree problem, in which the costs associated with every edge of the input graph are vectors. In this paper, we design a new dynamic programming MO-MST algorithm. Dynamic programming for a MO-MST instance leads to the definition of an instance of the One-to-One Multiobjective Shortest Path (MOSP) problem and both instances have equivalent solution sets. The arising MOSP instance is defined on a so called transition graph. We study the original size of this graph in detail and reduce its size using cost dependent arc pruning criteria. To solve the MOSP instance on the reduced transition graph, we design the Implicit Graph Multiobjective Dijkstra Algorithm (IG-MDA), exploiting recent improvements on MOSP algorithms from the literature. All in all, the new IG-MDA outperforms the current state of the art on a big set of instances from the literature. Our code and results are publicly available.}, language = {en} } @article{MasingLindnerBortoletto2025, author = {Masing, Berenike and Lindner, Niels and Bortoletto, Enrico}, title = {Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm}, volume = {14}, journal = {EURO Journal on Transportation and Logistics}, arxiv = {http://arxiv.org/abs/2412.14654}, doi = {10.1016/j.ejtl.2025.100163}, year = {2025}, abstract = {Given a public transportation network, which and how many passenger routes can potentially be shortest paths, when all possible timetables are taken into account? This question leads to shortest path problems on graphs with interval costs on their arcs and is closely linked to multi-objective optimization. We introduce a Dijkstra algorithm based on polynomials over the tropical semiring that computes complete or minimal sets of efficient paths. We demonstrate that this approach is computationally feasible by employing it on the public transport network of the city of Wuppertal and instances of the benchmarking set TimPassLib, and we evaluate the resulting sets of passenger routes.}, language = {en} } @misc{EbertSchlechteSchwartz2025, author = {Ebert, Patricia and Schlechte, Thomas and Schwartz, Stephan}, title = {Scheduling for German Road Inspectors}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101999}, year = {2025}, abstract = {For the yearly over 500,000 vehicle inspections of the German Federal Logistics and Mobility Office (BALM), crew rosters must be scheduled to efficiently achieve Germany's road inspection control targets. For that, we present a model to solve the respective duty scheduling and crew rostering problem in order to obtain duty rosters that comply with numerous legal regulations while maximizing the 'control success' to achieve the control targets. We formulate the Template Assignment Problem, which can be modelled as a large scale mixed-integer linear program. Here, feasible combinations of control topics are assigned to the duties using a hypergraph approach. The model is used in production by BALM, and we prove its effectiveness on a number of real-world instances.}, language = {en} } @article{GrimmHoogervorstBorndoerfer2025, author = {Grimm, Boris and Hoogervorst, Rowan and Bornd{\"o}rfer, Ralf}, title = {A Comparison of Two Models for Rolling Stock Scheduling}, volume = {59}, journal = {Transportation Science}, number = {5}, arxiv = {http://arxiv.org/abs/2312.09697}, doi = {10.1287/trsc.2024.0505}, year = {2025}, abstract = {A major step in the planning process of passenger railway operators is the assignment of rolling stock, that is, train units, to the trips of the timetable. A wide variety of mathematical optimization models have been proposed to support this task, which we discuss and argue to be justified in order to deal with operational differences between railway operators, and hence different planning requirements, in the best possible way. Our investigation focuses on two commonly used models, the composition model and the hypergraph model, that were developed for Netherlands Railways (NS) and DB Fernverkehr AG (DB), respectively. We compare these models in two distinct problem settings, an NS setting and DB-light setting and consider different model variants to tune the models to these settings. We prove that in both of these settings, the linear programming bounds of the two models are equally strong as long as a number of reasonable assumptions are met. However, through a numerical evaluation on NS and DB-light instances, we show that the numerical performance of the models strongly depends on the instances. Although the composition model is the most compact and fastest model for the NS instances, an adjusted version of this model grows quickly for the DB-light instances and is then outperformed by the considered hypergraph model variants. Moreover, we show that a depot-extended version of the hypergraph model is able to combine strengths of both models and show good performance on both the NS and DB-light instances.}, language = {en} } @inproceedings{LindnerLiebchen2025, author = {Lindner, Niels and Liebchen, Christian}, title = {Incremental Heuristics for Periodic Timetabling}, booktitle = {Operations Research Proceedings 2023}, editor = {Voigt, Guido and Fliedner, Malte and Haase, Knut and Br{\"u}ggemann, Wolfgang and Hoberg, Kai and Meissner, J{\"o}rn}, publisher = {Springer Nature Switzerland}, address = {Cham}, doi = {10.1007/978-3-031-58405-3_59}, pages = {461 -- 467}, year = {2025}, abstract = {We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances.}, language = {en} } @article{MaristanydelasCasasSedenoNodaBorndoerferetal.2025, author = {Maristany de las Casas, Pedro and Sede{\~n}o-Noda, Antonio and Bornd{\"o}rfer, Ralf and Huneshagen, Max}, title = {K-Shortest Simple Paths Using Biobjective Path Search}, volume = {17}, journal = {Mathematical Programming Computation}, arxiv = {http://arxiv.org/abs/2309.10377}, doi = {10.1007/s12532-025-00276-0}, pages = {349 -- 384}, year = {2025}, abstract = {In this paper we introduce a new algorithm for the k-Shortest Simple Paths (K-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick (2012) that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.}, 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} } @misc{BorndoerferDenissenHelleretal.2021, author = {Bornd{\"o}rfer, Ralf and Denißen, Jonas and Heller, Simon and Klug, Torsten and K{\"u}pper, Michael and Lindner, Niels and Reuther, Markus and Schlechte, Thomas and S{\"o}hlke, Andreas and Steadman, William}, title = {Microscopic Timetable Optimization for a Moving Block System}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82547}, year = {2021}, abstract = {We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.}, language = {en} } @misc{LindnerMasing2023, author = {Lindner, Niels and Masing, Berenike}, title = {On the Split Closure of the Periodic Timetabling Polytope}, issn = {1438-0064}, doi = {10.1007/s10107-025-02220-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91156}, year = {2023}, 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{LindnerLiebchen2023, author = {Lindner, Niels and Liebchen, Christian}, title = {Incremental Heuristics for Periodic Timetabling}, issn = {1438-0064}, doi = {10.1007/978-3-031-58405-3_59}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92309}, year = {2023}, abstract = {We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances.}, language = {en} } @misc{BortolettoLindner2023, author = {Bortoletto, Enrico and Lindner, Niels}, title = {Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times}, issn = {1438-0064}, doi = {10.1007/978-3-031-58405-3_51}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92315}, year = {2023}, abstract = {The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.}, language = {en} } @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} } @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} } @inproceedings{LindnerLiebchenMasing2021, author = {Lindner, Niels and Liebchen, Christian and Masing, Berenike}, title = {Forward Cycle Bases and Periodic Timetabling}, volume = {96}, booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)}, doi = {10.4230/OASIcs.ATMOS.2021.2}, pages = {2:1 -- 2:14}, year = {2021}, abstract = {Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance R1L1 of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.}, language = {en} } @misc{LindnerLiebchenMasing2021, author = {Lindner, Niels and Liebchen, Christian and Masing, Berenike}, title = {Forward Cycle Bases and Periodic Timetabling}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2021.2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82756}, year = {2021}, abstract = {Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance \texttt{R1L1} of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.}, language = {en} } @misc{LindnerMaristanydelasCasasSchiewe2021, author = {Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine}, title = {Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2021.7}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82716}, year = {2021}, abstract = {We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.}, language = {en} } @misc{LindnervanLieshout2021, author = {Lindner, Niels and van Lieshout, Rolf}, title = {Benders Decomposition for the Periodic Event Scheduling Problem}, issn = {1438-0064}, doi = {10.1007/978-3-031-08623-6_43}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83338}, year = {2021}, 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} } @inproceedings{LindnerMaristanydelasCasasSchiewe2021, author = {Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine}, title = {Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}, volume = {96}, booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)}, doi = {10.4230/OASIcs.ATMOS.2021.7}, pages = {7:1 -- 7:15}, year = {2021}, abstract = {We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.}, language = {en} } @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} } @inproceedings{EulerBorndoerferPuchertetal.2024, author = {Euler, Ricardo and Bornd{\"o}rfer, Ralf and Puchert, Christian and Takkula, Tuomo}, title = {ULD Build-Up Scheduling with Logic-Based Benders Decomposition}, volume = {14742}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, doi = {10.1007/978-3-031-60597-0_17}, pages = {259 -- 276}, year = {2024}, abstract = {We study a complex planning and scheduling problem arising from the build-up process of air cargo pallets and containers, collectively referred to as unit load devices (ULD), in which ULDs must be assigned to workstations for loading. Since air freight usually becomes available gradually along the planning horizon, ULD build-ups must be scheduled neither too early to avoid underutilizing ULD capacity, nor too late to avoid resource conflicts with other flights. Whenever possible, ULDs should be built up in batches, thereby giving ground handlers more freedom to rearrange cargo and utilize the ULD's capacity efficiently. The resulting scheduling problem has an intricate cost function and produces large time-expanded models, especially for longer planning horizons. We propose a logic-based Benders decomposition approach that assigns batches to time intervals and workstations in the master problem, while the actual schedule is decided in a subproblem. By choosing appropriate intervals, the subproblem becomes a feasibility problem that decomposes over the workstations. Additionally, the similarity of many batches is exploited by a strengthening procedure for no-good cuts. We benchmark our approach against a time-expanded MIP formulation from the literature on a publicly available data set. It solves 15\% more instances to optimality and decreases run times by more than 50\% in the geometric mean. This improvement is especially pronounced for longer planning horizons of up to one week, where the Benders approach solves over 50\% instances more than the baseline}, language = {en} } @article{EulerMaristanydelasCasas2024, author = {Euler, Ricardo and Maristany de las Casas, Pedro}, title = {Labeling methods for partially ordered paths}, volume = {318}, journal = {European Journal of Operational Research}, number = {1}, edition = {1}, publisher = {Elsevier BV}, arxiv = {http://arxiv.org/abs/2307.10332}, doi = {10.1016/j.ejor.2024.05.002}, pages = {19 -- 30}, year = {2024}, abstract = {The landscape of applications and subroutines relying on shortest path computations continues to grow steadily. This growth is driven by the undeniable success of shortest path algorithms in theory and practice. It also introduces new challenges as the models and assessing the optimality of paths become more complicated. Hence, multiple recent publications in the field adapt existing labeling methods in an ad hoc fashion to their specific problem variant without considering the underlying general structure: they always deal with multi-criteria scenarios, and those criteria define different partial orders on the paths. In this paper, we introduce the partial order shortest path problem (POSP), a generalization of the multi-objective shortest path problem (MOSP) and in turn also of the classical shortest path problem. POSP captures the particular structure of many shortest path applications as special cases. In this generality, we study optimality conditions or the lack of them, depending on the objective functions' properties. Our final contribution is a big lookup table summarizing our findings and providing the reader with an easy way to choose among the most recent multi-criteria shortest path algorithms depending on their problems' weight structure. Examples range from time-dependent shortest path and bottleneck path problems to the electric vehicle shortest path problem with recharging and complex financial weight functions studied in the public transportation community. Our results hold for general digraphs and, therefore, surpass previous generalizations that were limited to acyclic graphs.}, language = {en} } @misc{Henning2020, type = {Master Thesis}, author = {Henning, Erin}, title = {Tropical Geometry Approach to Shortest Paths with Parameterized Arc Weights - A Case Study in Public Transportation Networks}, year = {2020}, abstract = {In graphical representations of public transportation networks, there is often some degree of uncertainty in the arc values, due to delays or transfer times. This uncertainty can be expressed as a parameterized weight on the transfer arcs. Classical shortest path algorithms often have difficulty handling parameterized arc weights and a tropical geometry approach has been shown as a possible solution. The connection between the classical shortest path problem and tropical geometry is well establish: Tropically multiplying the n × n adjacency matrix of a graph with itself n - 1 times results in the so-called Kleene star, and is a matrix-form solution to the all-pairs shortest path problem. Michael Joswig and Benjamin Schr{\"o}ter showed in their paper The Tropical Geometry of Shortest Paths that the same method can be used to find the solution to the all-pairs shortest path problem even in the case of variable arc weights and they proposed an algorithm to solve the single-target shortest path problem in such a case. The solution takes the form of a polyhedral subdivision of the parameter space. As the number of variable arc weights grows, the time needed to execute an implementation of this algorithm grows exponentially. As the size of a public transportation network grows, the number of variable arc weights grows exponentially as well. However, it has been observed that in public transportation networks, there are usually only a few possible shortest routes. Geometrically, this means that there should be few polyhedra in the polyhedral subdivision. This algorithm is used on an example of a real-world public transportation network and an analysis of the polyhedral subdivision is made. Then a geometrical approach is used to analyze the impact of limiting the number of transfers, and thereby limiting the number of parameterized arcs used, as an estimation of the solution to the all-pairs shortest path problem}, language = {en} } @misc{Masing2020, type = {Master Thesis}, author = {Masing, Berenike}, title = {Optimal Line Planning in the Parametric City}, year = {2020}, abstract = {One of the fundamental steps in the optimization of public transport is line planning. It involves determining lines and assigning frequencies of service such that costs are minimized while also maximizing passenger comfort and satisfying travel demands. We formulate the problem as a mixed integer linear program that considers all circuit-like lines in a graph and allows free passenger routing. Traveler and operator costs are included in a linear scalarization in the objective. We apply said programming problem to the Parametric City, which is a graph model introduced by Fielbaum, Jara-D{\´i}az and Gschwender that exibly represents different cities. In his dissertation, Fielbaum solved the line planning problem for various parameter choices in the Parametric City. In a first step, we therefore review his results and make comparative computations. Unlike Fielbaum we arrive at the conclusion that the optimal line plan for this model indeed depends on the demand. Consequently, we analyze the line planning problem in-depth: We find equivalent, but easier to compute formulations and provide a lower bound by LP-relaxation, which we show to be equivalent to a multi-commodity flow problem. Further, we examine what impact symmetry has on the solutions. Supported both by computational results as well as by theoretical analysis, we reach the conclusion that symmetric line plans are optimal or near-optimal in the Parametric City. Restricting the model to symmetric line plans allows for a \kappa-factor approximation algorithm for the line planning problem in the Parametric City.}, language = {en} } @masterthesis{Lange2021, type = {Bachelor Thesis}, author = {Lange, Johanna}, title = {A Decomposition and Dualization Approach to the Periodic Event Scheduling Problem}, year = {2021}, abstract = {Scheduling ist ein wichtiger Forschungsgegenstand im Bereich der diskreten Optimierung. Es geht darum, einen Schedule, d.h. einen Ablaufplan, f{\"u}r gegebene Ereignisse zu finden. Dieser soll optimal hinsichtlich einer Zielfunktion wie zum Beispiel minimaler Dauer oder Kosten sein. Dabei gibt es in der Regel Nebenbedingungen wie Vorrangbeziehungen zwischen den Ereignissen oder zeitliche Einschr{\"a}nkungen, die zu erf{\"u}llen sind. Falls die Ereignisse periodisch wiederkehren, spricht man von periodischem Scheduling. Beispiele sind das Erstellen von Zugfahrpl{\"a}nen, die Schaltungvon Ampelsignalen oder die Planung von Produktionsabl{\"a}ufen. Mathematisch k{\"o}nnen diese Probleme mit dem Periodic Event Scheduling Problem (PESP) modelliert werden, das als gemischt-ganzzahliges Programm formuliert werden kann. In dieser Bachelorarbeit wird ein Ansatz zur L{\"o}sung des PESP mittels Zerlegung und Dualisierung entwickelt. In den Kapiteln 2 und 3 werden zun{\"a}chst die notwendigen graphentheoretischen Grundlagen und das PESP eingef{\"u}hrt. In Kapitel 4 wird das PESP durch Fixierung der ganzzahligen Variablen in lineare Programme zerlegt. Dieses Unterproblem wird dualisiert und wieder in das PESP eingesetzt. Daf{\"u}r ist eine weitere Nebenbedingung n{\"o}tig. Im f{\"u}nften Kapitel behandeln wir die L{\"o}sung des teildualisierten PESP. Eine M{\"o}glichkeit ist es, sich auf eine Teilmenge der Nebenbedingungen zu beschr{\"a}nken. Eine weitere M{\"o}glichkeit ist ein Algorithmus, der{\"a}hnlich wie BendersZerlegung die Nebenbedingungen dynamisch erzeugt. Dieser Algorithmus wird in Kapitel 6 implementiert und an vier Beispielen getestet.}, language = {en} } @misc{Kuehner2021, type = {Master Thesis}, author = {K{\"u}hner, Arno}, title = {Shortest Paths with Boolean Constraints}, year = {2021}, abstract = {For this thesis we study the Constrained Horizontal Flightplanning Problem (CHFPP) for which one has to find the path of minimum cost between airports s and t in a directed graph that respects a set of boolean constraints. To this end we give a survey of three different multilabel algorithms that all use a domination subroutine. We summarize an approach by Knudsen, Chiarandini and Larsen to define this domination and afterwards present our own method which builds on that approach. We suggest different implementation techniques to speed up the computation time, most notably a Reoptimization for an iterative method to solve the problem. Furthermore we implemented the different versions of the algorithm and present statistics on their computation as well as an overview of statistics on the set of real-world constraints that we were given. Finally we present two alternative approaches that tackle the problem, a heuristic with similarities to a Lagrangian relaxation and an approach that makes use of an algorithm which finds the k shortest path of a graph such as the ones of Epstein or Yen.}, language = {en} } @misc{MaristanydelasCasasSedenoNodaBorndoerfer2021, author = {Maristany de las Casas, Pedro and Sedeno-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {An Improved Multiobjective Shortest Path Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79712}, year = {2021}, abstract = {We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes the minimal complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm \emph{Multiobjective Dijkstra Algorithm} (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins', which we improved using new data structures and pruning techniques. On average, the MDA is \$\times2\$ to \$\times9\$ times faster on all used graph types. On some instances the speedup reaches an order of magnitude.}, language = {en} } @misc{PrauseBorndoerferGrimmetal.2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating the RSRP with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89531}, year = {2023}, abstract = {We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.}, language = {en} } @misc{Prause2023, author = {Prause, Felix}, title = {A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-93133}, year = {2023}, abstract = {We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subse- quently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables.}, language = {en} } @misc{LoebelBorndoerferWeider2024, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Electric Bus Scheduling with Non-Linear Charging, Power Grid Bottlenecks, and Dynamic Recharge Rates}, arxiv = {http://arxiv.org/abs/2407.14446}, year = {2024}, abstract = {Public transport operators are gradually electrifying their bus fleets, predominantly with battery-powered drive trains. These buses commonly have to be scheduled to recharge in-service, which gives rise to a number of challenges. A major problem is that the relationship between charging time and replenished driving range is non-linear, which is often approximately modeled. We examine the associated approximation error and show how it can result in a gross over- or underestimation of the fleet size. Moreover, we demonstrate that commonly used piecewise linear underestimations of the charge curve do not result in an underestimation of the predicted charge states in electric vehicle scheduling and routing models. Furthermore, since power grid upgrades are currently not keeping up with an ever growing electricity demand, operators are introducing active charge management tools to dynamically adjust the charging speed depending on the amount of available energy. It is therefore imperative to extend electric bus scheduling models to account for these developments. We propose a novel mixed-integer programming formulation for the electric bus scheduling problem featuring an improved approximation of the non-linear battery charging behavior as well as dynamic recharge speeds to accommodate grid load limits. The idea is to linearly interpolate what we call the charge increment function, which is closely related to the derivative of the commonly used charge curve. This provides very good error control and integrates easily into integer programming models. We demonstrate the practical usefulness of our model on a diverse library of real-life instances.}, language = {en} } @inproceedings{BorndoerferLoebelLoebeletal.2024, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and L{\"o}bel, Fabian and Weider, Steffen}, title = {Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach}, volume = {123}, booktitle = {24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2024.11}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-211992}, pages = {11:1 -- 11:16}, year = {2024}, abstract = {Attractive and cost-efficient public transport requires solving computationally difficult optimization problems from network design to crew rostering. While great progress has been made in many areas, new requirements to handle increasingly complex constraints are constantly coming up. One such challenge is a new type of resource constraints that are used to deal with the state-of-charge of battery-electric vehicles, which have limited driving ranges and need to be recharged in-service. Resource constrained vehicle scheduling problems can classically be modelled in terms of either a resource constrained (multi-commodity) flow problem or in terms of a path-based set partition problem. We demonstrate how a novel integrated version of both formulations can be leveraged to solve resource constrained vehicle scheduling with replenishment in general and the electric bus scheduling problem in particular by Lagrangian relaxation and the proximal bundle method.}, language = {en} } @article{PrauseBorndoerfer2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {An Iterative Refinement Approach for the Rolling Stock Rotation Problem with Predictive Maintenance}, arxiv = {http://arxiv.org/abs/2404.08367}, year = {2024}, abstract = {The rolling stock rotation problem with predictive maintenance (RSRP-PdM) involves the assignment of trips to a fleet of vehicles with integrated maintenance scheduling based on the predicted failure probability of the vehicles. These probabilities are determined by the health states of the vehicles, which are considered to be random variables distributed by a parameterized family of probability distribution functions. During the operation of the trips, the corresponding parameters get updated. In this article, we present a dual solution approach for RSRP-PdM and generalize a linear programming based lower bound for this problem to families of probability distribution functions with more than one parameter. For this purpose, we define a rounding function that allows for a consistent underestimation of the parameters and model the problem by a state-expanded event-graph in which the possible states are restricted to a discrete set. This induces a flow problem that is solved by an integer linear program. We show that the iterative refinement of the underlying discretization leads to solutions that converge from below to an optimal solution of the original instance. Thus, the linear relaxation of the considered integer linear program results in a lower bound for RSRP-PdM. Finally, we report on the results of computational experiments conducted on a library of test instances.}, language = {en} } @inproceedings{Prause2024, author = {Prause, Felix}, title = {A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance}, booktitle = {Proceedings of the 11th International Network Optimization Conference (INOC), Dublin, Ireland, March 11-23, 2024}, doi = {10.48786/inoc.2024.11}, pages = {58 -- 63}, year = {2024}, abstract = {We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subsequently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables.}, language = {en} } @article{PrauseBorndoerferGrimmetal.2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating rolling stock rotations with integrated predictive maintenance}, volume = {30}, journal = {Journal of Rail Transport Planning \& Management}, doi = {10.1016/j.jrtpm.2024.100434}, pages = {100434}, year = {2024}, abstract = {We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for six instances derived from real-world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.}, language = {en} } @misc{Bortoletto2021, type = {Master Thesis}, author = {Bortoletto, Enrico}, title = {The tropical tiling of periodic timetable space and a dual modulo network simplex algorithm}, year = {2021}, abstract = {We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem.}, language = {en} } @masterthesis{Kraus2021, type = {Bachelor Thesis}, author = {Kraus, Luitgard}, title = {A Label Setting Multiobjective Shortest Path FPTAS}, year = {2021}, abstract = {Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants.}, language = {en} } @misc{Rahmati2021, type = {Master Thesis}, author = {Rahmati, Niloofar}, title = {Resource Constrained APSP-Algorithm with Possible Reloading Stops}, year = {2021}, language = {en} } @misc{PrauseBorndoerfer2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91734}, year = {2023}, abstract = {We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM.}, language = {en} } @misc{LoebelBorndoerferWeider2023, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Non-Linear Battery Behavior in Electric Vehicle Scheduling Problems}, issn = {1438-0064}, doi = {10.1007/978-3-031-58405-3_53}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92441}, year = {2023}, 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} }