TY - GEN A1 - Bortoletto, Enrico A1 - Lindner, Niels T1 - Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times N2 - 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. T3 - ZIB-Report - 23-23 KW - Timetabling KW - Mixed-Integer Programming KW - Public Transport Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-92315 SN - 1438-0064 ER - TY - THES A1 - Bushe, Julian T1 - Rolling Stock Rotation Optimization with Maintenance Paths N2 - Die Planung vom Zugumläufen ist eine der wichtigsten Aufgaben für Eisenbahnun- ternehmen. Dabei spielt auch die Einhaltung von vorgegebenen Wartungsintervallen eine zentrale Rolle für die Sicherheit und Zuverlässigkeit der Schienenfahrzeuge. Wir zeigen, wie man dieses Umlaufplanungsproblem unter Beachtung von Wartungsbe- dingungen mathematisch formuliert, modelliert und löst — sowohl in der Theorie als auch im Anwendungsfall mit Szenarien der DB Fernverkehr AG, einer Konzern- tochter der Deutschen Bahn für den Schienenpersonenfernverkehr. Markus Reuther hat sich in seiner Dissertation [11] mit diesem Problem beschäftigt und es mit Hilfe eines passenden Hypergraphen als gemischt-ganzzahliges Programm modelliert. Neben der Modellierung präsentiert Reuther in seiner Arbeit neuartige algorithmische Ideen, darunter den sogenannten Coarse-to-Fine -Ansatz, bei dem zunächst Teile des Problems auf einer weniger detaillierten ( coarse ) Ebene gelöst werden und diese Lösung dann verwendet wird, um auf effiziente Art und Weise eine Lösung für das ursprü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ührt dies dazu, dass die Zahl der notwendigen Wartungen systematisch unterschätzt wird. Dadurch bleibt in vielen Fällen eine große Lücke zwischen dem Zielfunktionswert einer optimalen Lö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ür das Umlaufplanungsproblem und zeigen, dass die untere Schranke mindestens so scharf oder schärfer ist als die untere Schranke, die das Modell von Reuther liefert. Um das Modell zu lö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ür fast alle Szena- rien deutlich schä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ätslücke schließen. In einem Drittel der Fälle konnten wir durch unseren Ansatz auch für das ganzzahlige Programm verbesserte Zielfunktionswerte erreichen Y1 - 2021 ER - TY - GEN A1 - Masing, Berenike A1 - Lindner, Niels A1 - Ebert, Patricia T1 - Forward and Line-Based Cycle Bases for Periodic Timetabling N2 - 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. T3 - ZIB-Report - 23-05 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89731 SN - 1438-0064 ER - TY - JOUR A1 - Lindner, Niels A1 - Masing, Berenike T1 - On the split closure of the periodic timetabling polytope JF - Mathematical Programming N2 - 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. KW - Periodic event scheduling problem KW - Periodic timetabling KW - Split closure KW - Mixed-integer programming Y1 - 2025 U6 - https://doi.org/10.1007/s10107-025-02220-5 SN - 0025-5610 PB - Springer Science and Business Media LLC ER - TY - GEN A1 - Lindner, Niels T1 - A Multi-Commodity Flow Heuristic for Integrated Periodic Timetabling for Railway Construction Sites N2 - 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. T3 - ZIB-Report - 25-02 KW - Railway Timetabling KW - Periodic Timetabling KW - Rescheduling KW - Railway Track Allocation Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-99449 SN - 1438-0064 ER - TY - CHAP A1 - Löbel, Fabian A1 - Borndörfer, Ralf A1 - Weider, Steffen ED - Voigt, Guido ED - Fliedner, Malte ED - Haase, Knut ED - Brüggermann, Wolfgang ED - Hoberg, Kai ED - Meissner, Joern T1 - Non-linear Battery Behavior in Electric Vehicle Scheduling Problems T2 - Operations Research Proceedings 2023. OR 2023. N2 - 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. KW - Electric Vehicle Scheduling KW - Non-Linear Charging Y1 - 2025 SN - 9783031584046 U6 - https://doi.org/10.1007/978-3-031-58405-3_53 SN - 2731-040X SP - 415 EP - 421 PB - Springer Nature Switzerland CY - Cham ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - A two-stage model for periodic timetabling with fixed line activities N2 - 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. T3 - ZIB-Report - 25-14 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101234 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Timetable Merging for the Periodic Event Scheduling Problem N2 - 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. T3 - ZIB-Report - 21-06 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Railway Timetabling KW - PESPlib KW - Benchmark Solutions KW - Mixed Integer Programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81587 SN - 1438-0064 ER - TY - CHAP A1 - Lindner, Niels A1 - Liebchen, Christian ED - Huisman, Dennis ED - Zaroliagis, Christos D. T1 - Determining all integer vertices of the PESP polytope by flipping arcs T2 - 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020) N2 - 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. Y1 - 2020 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2020.5 VL - 85 SP - 5:1 EP - 5:18 PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany ER - TY - CHAP A1 - Lindner, Niels A1 - Masing, Berenike A1 - Liebchen, Christian T1 - Integrierte Baufahrplanoptimierung auf dem Netz der S-Bahn Berlin T2 - HEUREKA'24 - Optimierung in Verkehr und Transport N2 - Zur Instandhaltung von Eisenbahnnetzen sind regelmäßig Baumaßnahmen erforderlich. Diese erfordern stets Anpassungen der Fahrpläne. Um den Fahrgästen trotz der Baumaßnahme weiterhin einen möglichst großen Teil des Regelangebotes bieten zu können, bewegen sich die resultierenden Baufahrpläne insbesondere in Schnellbahnnetzen mit ihren dichten Zugfolgen häufig nahe der Kapazitätsgrenze der Infrastruktur. Etablierte Verfahren zur Taktfahrplanoptimierung können diesen Anforderungen nicht genügen, da in der Praxis Anpassungen von Laufwegen der Linien, sowie der Gleisbelegungen häufig Teil der realisierten Lösungen sind. Für diese Aufgabe haben die Autoren zuletzt ein Optimierungsmodell vorgestellt, welches diese Möglichkeiten ausschö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. Y1 - 2024 VL - 002/140 ER - TY - CHAP A1 - Lindner, Niels A1 - Masing, Berenike T1 - SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice T2 - hEART 2024: 12th Symposium of the European Association for Research in Transportation N2 - 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. KW - Periodic Timetabling KW - Railway Timetabling KW - Railway Track Allocation KW - Boolean Satisfiability Problem KW - Rescheduling KW - Line Planning Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-98066 UR - https://transp-or.epfl.ch/heart/2024/abstracts/hEART_2024_paper_3685.pdf ER - TY - CHAP A1 - Lindner, Niels A1 - Liebchen, Christian A1 - Masing, Berenike T1 - Forward Cycle Bases and Periodic Timetabling T2 - 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) N2 - 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. Y1 - 2021 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2021.2 VL - 96 SP - 2:1 EP - 2:14 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian A1 - Masing, Berenike T1 - Forward Cycle Bases and Periodic Timetabling N2 - 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. T3 - ZIB-Report - 21-18 KW - Periodic Timetabling KW - Cycle Bases KW - Mixed Integer Programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82756 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Maristany de las Casas, Pedro A1 - Schiewe, Philine T1 - Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data N2 - 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. T3 - ZIB-Report - 21-17 KW - Preprocessing Shortest Path Problems KW - Interval Data KW - Graph Algorithms Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82716 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - van Lieshout, Rolf T1 - Benders Decomposition for the Periodic Event Scheduling Problem N2 - 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. T3 - ZIB-Report - 21-29 KW - Periodic Timetabling KW - Periodic Event Scheduling Problem KW - Benders Decomposition KW - Mixed-Integer Programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-83338 SN - 1438-0064 ER - TY - CHAP A1 - Lindner, Niels A1 - Maristany de las Casas, Pedro A1 - Schiewe, Philine T1 - Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data T2 - 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) N2 - 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. Y1 - 2021 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2021.7 VL - 96 SP - 7:1 EP - 7:15 ER - TY - GEN A1 - Ebert, Patricia A1 - Masing, Berenike A1 - Lindner, Niels A1 - Gleixner, Ambros T1 - Sorting Criteria for Line-based Periodic Timetabling Heuristics N2 - 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%. T3 - ZIB-Report - 24-07 KW - Public Transport KW - Timetabling KW - Periodic Event Scheduling Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-97826 SN - 1438-0064 ER - TY - CHAP A1 - Bortoletto, Enrico A1 - van Lieshout, Rolf Nelson A1 - Masing, Berenike A1 - Lindner, Niels T1 - Periodic Event Scheduling with Flexible Infrastructure Assignment T2 - 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) N2 - 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. Y1 - 2024 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2024.4 VL - 123 SP - 4:1 EP - 4:18 ER - TY - CHAP A1 - Euler, Ricardo A1 - Borndörfer, Ralf A1 - Puchert, Christian A1 - Takkula, Tuomo T1 - ULD Build-Up Scheduling with Logic-Based Benders Decomposition T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research N2 - 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 Y1 - 2024 U6 - https://doi.org/10.1007/978-3-031-60597-0_17 VL - 14742 SP - 259 EP - 276 ER - TY - JOUR A1 - Euler, Ricardo A1 - Maristany de las Casas, Pedro T1 - Labeling methods for partially ordered paths JF - European Journal of Operational Research N2 - 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. Y1 - 2024 U6 - https://doi.org/10.1016/j.ejor.2024.05.002 VL - 318 IS - 1 SP - 19 EP - 30 PB - Elsevier BV ET - 1 ER - TY - THES A1 - Henning, Erin T1 - Tropical Geometry Approach to Shortest Paths with Parameterized Arc Weights - A Case Study in Public Transportation Networks N2 - 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ö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 Y1 - 2020 ER -