TY - CHAP A1 - Klug, Torsten A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Does Laziness Pay Off? - A Lazy-Constraint Approach to Timetabling T2 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - Timetabling is a classical and complex task for public transport operators as well as for railway undertakings. The general question is: Which vehicle is taking which route through the transportation network in which order? In this paper, we consider the special setting to find optimal timetables for railway systems under a moving block regime. We directly set up on our work of [8 ], i.e., we consider the same model formulation and real-world instances of a moving block headway system. In this paper, we present a repair heuristic and a lazy-constraint approach utilizing the callback features of Gurobi, see [3]. We provide an experimental study of the different algorithmic approaches for a railway network with 100 and up to 300 train requests. The computational results show that the lazy-constraint approach together with the repair heuristic significantly improves our previous approaches. Y1 - 2022 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022.11 VL - 106 SP - 11:1 EP - 11:8 PB - Schloss Dagstuhl -- Leibniz-Zentrum für Informatik ER - TY - JOUR A1 - Maristany de las Casas, Pedro A1 - Sedeno-Noda, Antonio A1 - Borndörfer, Ralf T1 - An Improved Multiobjective Shortest Path Algorithm JF - Computers & Operations Research N2 - We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes a minimum 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 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 2 to 9 times faster on all used graph types. On some instances the speedup reaches an order of magnitude. Y1 - 2021 U6 - https://doi.org/10.1016/j.cor.2021.105424 VL - 135 ER - TY - JOUR A1 - Schlechte, Thomas A1 - Borndörfer, Ralf A1 - Denißen, Jonas A1 - Heller, Simon A1 - Klug, Torsten A1 - Küpper, Michael A1 - Lindner, Niels A1 - Reuther, Markus A1 - Söhlke, Andreas A1 - Steadman, William T1 - Timetable Optimization for a Moving Block System JF - Journal of Rail Transport Planning & Management N2 - 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. Y1 - 2022 U6 - https://doi.org/10.1016/j.jrtpm.2022.100315 SN - 2210-9706 VL - 22 SP - 100315 ER - TY - JOUR A1 - Maristany de las Casas, Pedro A1 - Borndörfer, Ralf A1 - Kraus, Luitgard A1 - Sedeño-Noda, Antonio T1 - An FPTAS for Dynamic Multiobjective Shortest Path Problems JF - Algorithms N2 - The Dynamic Multiobjective Shortest Path problem features multidimensional costs that can depend on several variables and not only on time; this setting is motivated by flight planning applications and the routing of electric vehicles. We give an exact algorithm for the FIFO case and derive from it an FPTAS for both, the static Multiobjective Shortest Path (MOSP) problems and, under mild assumptions, for the dynamic problem variant. The resulting FPTAS is computationally efficient and beats the known complexity bounds of other FPTAS for MOSP problems. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.3390/a14020043 VL - 14 IS - 2 SP - 1 EP - 22 ER - TY - JOUR A1 - Roth, Sarah T1 - SAT-Heuristiken für das Periodic Event Scheduling-Problem JF - OR News Y1 - 2021 SN - 1437-2045 IS - 71 ER - TY - GEN A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - The Tropical and Zonotopal Geometry of Periodic Timetables N2 - The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetabling problems in public transport. A solution to PESP consists of three parts: a periodic timetable, a periodic tension, and integer periodic offset values. While the space of periodic tension has received much attention in the past, we explore geometric properties of the other two components, establishing novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables, and decompose it into polytropes, i.e., polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on the tropical neighbourhood of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope. We relate its zonotopal tilings back to the hyperrectangle of fractional periodic tensions and to the tropical neighbourhood of the periodic timetable space. To conclude we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis. T3 - ZIB-Report - 22-09 KW - periodic event scheduling KW - tropical geometry KW - zonotopal tilings Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-86708 SN - 1438-0064 ER - TY - GEN A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling N2 - Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [3]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [4]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances. T3 - ZIB-Report - 22-13 KW - Periodic Timetabling KW - Tropical Geometry KW - Neighbourhood Search KW - Mixed-Integer Programming Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-87385 SN - 1438-0064 ER - TY - GEN A1 - Masing, Berenike A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Periodic Timetabling with Integrated Track Choice for Railway Construction Sites N2 - We propose a mixed-integer linear programming model to generate and optimize periodic timetables with integrated track choice in the context of railway construction sites. When a section of a railway network becomes unavailable, the nearby areas are typically operated close to their capacity limits, and hence carefully modeling headways and allowing flexible routings becomes vital. We therefore discuss first how to integrate headway constraints into the Periodic Event Scheduling Problem (PESP) that do not only prevent overtaking, but also guarantee conflict-free timetables in general and particularly inside stations. Secondly, we introduce a turn-sensitive event-activity network, which is able to integrate routing alternatives for turnarounds at stations, e.g., turning at a platform vs. at a pocket track for metro-like systems. We propose several model formulations to include track choice, and finally evaluate them on six real construction site scenarios on the S-Bahn Berlin network. T3 - ZIB-Report - 22-26 KW - Railway Timetabling KW - Periodic Timetabling KW - Periodic Event Scheduling KW - Train Routing KW - Turnarounds Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88626 SN - 1438-0064 ER - TY - JOUR A1 - Euler, Ricardo A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - Price Optimal Routing in Public Transportation N2 - We consider the price-optimal earliest arrival problem in public transit (POEAP) in which we aim to calculate the Pareto-front of journeys with respect to ticket price and arrival time in a public transportation network. Public transit fare structures are often a combination of various fare strategies such as, e.g., distance-based fares, zone-based fares or flat fares. The rules that determine the actual ticket price are often very complex. Accordingly, fare structures are notoriously difficult to model as it is in general not sufficient to simply assign costs to arcs in a routing graph. Research into POEAP is scarce and usually either relies on heuristics or only considers restrictive fare models that are too limited to cover the full scope of most real-world applications. We therefore introduce conditional fare networks (CFNs), the first framework for representing a large number of real-world fare structures. We show that by relaxing label domination criteria, CFNs can be used as a building block in label-setting multi-objective shortest path algorithms. By the nature of their extensive modeling capabilities, optimizing over CFNs is NP-hard. However, we demonstrate that adapting the multi-criteria RAPTOR (MCRAP) algorithm for CFNs yields an algorithm capable of solving POEAP to optimality in less than 400 ms on average on a real-world data set. By restricting the size of the Pareto-set, running times are further reduced to below 10 ms. Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-86414 ER - TY - JOUR A1 - Lindner, Niels A1 - Reisch, Julian T1 - An analysis of the parameterized complexity of periodic timetabling JF - Journal of Scheduling N2 - Public transportation networks are typically operated with a periodic timetable. The periodic event scheduling problem (PESP) is the standard mathematical modeling tool for periodic timetabling. PESP is a computationally very challenging problem: For example, solving the instances of the benchmarking library PESPlib to optimality seems out of reach. Since PESP can be solved in linear time on trees, and the treewidth is a rather small graph parameter in the networks of the PESPlib, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth, or even better, fixed-parameter tractable algorithms. We show that deciding the feasibility of a PESP instance is NP-hard even when the treewidth is 2, the branchwidth is 2, or the carvingwidth is 3. Analogous results hold for the optimization of reduced PESP instances, where the feasibility problem is trivial. Moreover, we show W[1]-hardness of the general feasibility problem with respect to treewidth, which means that we can most likely only accomplish pseudo-polynomial-time algorithms on input networks with bounded tree- or branchwidth. We present two such algorithms based on dynamic programming. We further analyze the parameterized complexity of PESP with bounded cyclomatic number, diameter, or vertex cover number. For event-activity networks with a special—but standard—structure, we give explicit and sharp bounds on the branchwidth in terms of the maximum degree and the carvingwidth of an underlying line network. Finally, we investigate several parameters on the smallest instance of the benchmarking library PESPlib. Y1 - 2022 U6 - https://doi.org/10.1007/s10951-021-00719-1 VL - 25 SP - 157 EP - 176 ER - TY - CHAP A1 - Euler, Ricardo A1 - Borndörfer, Ralf A1 - Strunk, Timo A1 - Takkula, Tuomo T1 - ULD Build-Up Scheduling with Dynamic Batching in an Air Freight Hub T2 - Operations Research Proceedings 2021 N2 - Air freight is usually shipped in standardized unit load devices (ULDs). The planning process for the consolidation of transit cargo from inbound flights or locally emerging shipments into ULDs for outbound flights is called build-up scheduling. More specifically, outbound ULDs must be assigned a time and a workstation subject to both workstation capacity constraints and the availability of shipments which in turn depends on break-down decisions for incoming ULDs. ULDs scheduled for the same outbound flight should be built up in temporal and spatial proximity. This serves both to minimize overhead in transportation times and to allow workers to move freight between ULDs. We propose to address this requirement by processing ULDs for the same outbound flight in batches. For the above build-up scheduling problem, we introduce a multi-commodity network design model. Outbound flights are modeled as commodities; transit cargo is represented by cargo flow volume and unpack and batch decisions are represented as design variables. The model is solved with a standard MIP solver on a set of benchmark data. For instances with a limited number of resource conflicts, near-optimal solutions are found in under two hours for a whole week of operations. Y1 - 2022 U6 - https://doi.org/10.1007/978-3-031-08623-6_38 SP - 254 EP - 260 ER - TY - GEN A1 - Schlechte, Thomas A1 - Blome, Christian A1 - Gerber, Stefan A1 - Hauser, Stefan A1 - Kasten, Jens A1 - Müller, Gilbert A1 - Schulz, Christof A1 - Thüring, Michel A1 - Weider, Steffen T1 - The Bouquet of Features in Rolling Stock Rotation Planning T2 - Conference Proceedings RailBelgrade 2023 N2 - Rolling stock is one of the major assets for a railway transportation company. Hence, their utilization should be as efficiently and effectively as possible. Railway undertakings are facing rolling stock scheduling challenges in different forms - from rather idealized weekly strategic problems to very concrete operational ones. Thus, a vast of optimization models with different features and objectives exist. Thorlacius et al. (2015) provides a comprehensive and valuable collection on technical requirements, models, and methods considered in the scientific literature. We contribute with an update including recent works. The main focus of the paper is to present a classification and elaboration of the major features which our solver R-OPT is able to handle. Moreover, the basic optimization model and algorithmic ingredients of R-OPT are discussed. Finally, we present computational results for a cargo application at SBB CARGO AG and other railway undertakings for passenger traffic in Europe to show the capabilities of R-OPT. Y1 - 2023 UR - https://easychair.org/publications/preprint/Nms6 ER - TY - JOUR A1 - Maristany de las Casas, Pedro A1 - Kraus, Luitgard A1 - Sedeno-Noda, Antonio A1 - Borndörfer, Ralf T1 - Targeted multiobjective Dijkstra Algorithm JF - Networks N2 - We introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. It is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. For any explored subpath, a label setting MOSP algorithm decides whether the subpath can be discarded or must be stored as part of the output. A major design choice is how to store subpaths from the moment they are first explored until the mentioned final decision can be made. The T-MDA combines the polynomially bounded size of the priority queue used in the MDA and alazy management of paths that are not in the queue. The running time bounds from the MDA remain valid. In practice, the T-MDA outperforms known algorithms from the literature and the increased memory consumption is negligible. In this paper, we benchmark the T-MDA against an improved version of the state of the art NAMOA∗drOne-to-One MOSP algorithm from the literature on a standard testbed. Y1 - 2023 U6 - https://doi.org/10.1002/net.22174 VL - 82 IS - 3 SP - 277 EP - 298 ER - TY - CHAP A1 - Masing, Berenike A1 - Lindner, Niels A1 - Borndörfer, Ralf ED - Trautmann, Norbert ED - Drägi, Mario T1 - Optimal Line Plans in the Parametric City and the Impact of In-Motion Costs T2 - Operations Research Proceedings 2021 N2 - Line planning in public transport involves determining vehicle routes and assigning frequencies of service such that travel demands are satisfied. We evaluate how line plans, which are optimal with respect to in-motion costs (IMC), the objective function depending purely on arc-lengths for both user and operator costs, performs with respect to the value of resources consumed (VRC). The latter is an elaborate, socio-economic cost function which includes discomfort caused by delay, boarding and alighting times, and transfers. Even though discomfort is a large contributing factor to VRC and is entirely disregarded in IMC,  we observe that the two cost functions are qualitatively comparable. Y1 - 2022 SN - 978-3-031-08623-6 U6 - https://doi.org/10.1007/978-3-031-08623-6_44 SP - 295 EP - 301 PB - Springer, Cham ER - TY - JOUR A1 - Schiewe, Philine A1 - Goerigk, Marc A1 - Lindner, Niels T1 - Introducing TimPassLib – A Library for Integrated Periodic Timetabling and Passenger Routing JF - Operations Research Forum N2 - Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing. Y1 - 2023 U6 - https://doi.org/10.1007/s43069-023-00244-1 VL - 4 IS - 3 SP - 64 ER - TY - CHAP A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Maristany de las Casas, Pedro T1 - An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles T2 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A∗ heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances. Y1 - 2022 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022.1 VL - 106 SP - 1:1 EP - 1:15 ER - TY - JOUR A1 - Masing, Berenike A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - The price of symmetric line plans in the Parametric City JF - Transportation Research Part B: Methodological N2 - We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. We prove that the symmetry gap is small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations. Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88613 VL - 166 SP - 419 EP - 443 ER - TY - JOUR A1 - Beckenbach, Isabel T1 - Von Graphen zu Hypergraphen JF - OR News Y1 - 2020 SN - 1437-2045 IS - 70 ER - TY - CHAP A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Bushe, Julian T1 - Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization T2 - 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) N2 - The fundamental task of every passenger railway operator is to offer an attractive railway timetable to the passengers while operating it as cost efficiently as possible. The available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating costs are minimum. This so-called Rolling Stock Rotation Problem (RSRP) is well studied in the literature. In this paper we consider an acyclic version of the RSRP that includes vehicle maintenance. As the latter is an important aspect, maintenance services have to be planned simultaneously to ensure the rotation’s feasibility in practice. Indeed, regular maintenance is important for the safety and reliability of the rolling stock as well as enforced by law in many countries. We present a new integer programming formulation that links a hyperflow to model vehicle compositions and their coupling decisions to a set of path variables that take care of the resource consumption of the individual vehicles. To solve the model we developed different column generation algorithms which are compared to each other as well as to the MILP flow formulation of [Ralf Borndörfer et al., 2016] on a test set of real world instances. Y1 - 2023 U6 - https://doi.org/https://doi.org/10.4230/OASIcs.ATMOS.2023.13 VL - 115 SP - 13:1 EP - 13:15 PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Schade, Stanley T1 - A Robustness Analysis of Long Distance Train Crew Schedules in Germany T2 - Proceedings Of The Fifth Iinternational Conference On Railway Technology: Research, Development and Maintenance N2 - Nowadays railway networks are highly complex and often very fragile systems. A wide variety of individual operations that influence each other have to go hand in hand to end up with a smoothly and efficiently running system. Many of these operations suffer from uncertainty as trains could be delayed, the signaling system be disrupted or scheduled crews could be ill. Usually these opartions could be organized hierarchically from long term strategical decisions to real time decision management. Each stage in the hierarchy defines a different mathematical optimization problem, which is solved sequentially. At every stage the knowledge about preceding or succeeding planning stages may vary and also the interaction between two stages in this chain of problems may vary from almost no interaction to highly dependent situations. This paper deals with a topic that is an example for the latter case, namely the interaction between vehicle schedules, vehicle punctuality, and crew schedules. To reduce the number of potential rescheduling actions we developed a software tool in cooperation with our practical partner DB Fernverkehr AG (DBF) to predict a certain set of critical crew schedules. This tool evaluates, predicts, and determines "bottlenecks" in the crew schedule in the sense of potentially required rescheduling actions due to likely delays. The approach was tested on real life crew and train timetable data of DBF and can be regarded as the computation of key performance indicators, which is often desired. For our experiments we had access to the operated timetable and crew schedule of DBF for periods of two and six weeks in 2019. Y1 - 2023 U6 - https://doi.org/10.4203/ccc.1.23.17 SN - 2753-3239 VL - CCC 1 ER - TY - CHAP A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling T2 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [Borndörfer et al., 2020]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [Bortoletto et al., 2022]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances. Y1 - 2022 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022.3 VL - 106 SP - 3:1 EP - 3:19 ER - TY - CHAP A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - Periodic Timetabling with Cyclic Order Constraints T2 - 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) N2 - Periodic timetabling for highly utilized railway networks is a demanding challenge. We formulate an infrastructure-aware extension of the Periodic Event Scheduling Problem (PESP) by requiring that not only events, but also activities using the same infrastructure must be separated by a minimum headway time. This extended problem can be modeled as a mixed-integer program by adding constraints on the sum of periodic tensions along certain cycles, so that it shares some structural properties with standard PESP. We further refine this problem by fixing cyclic orders at each infrastructure element. Although the computational complexity remains unchanged, the mixed-integer programming model then becomes much smaller. Furthermore, we also discuss how to find a minimal subset of infrastructure elements whose cyclic order already prescribes the order for the remaining parts of the network, and how cyclic order information can be modeled in a mixed-integer programming context. In practice, we evaluate the impact of cyclic orders on a real-world instance on the S-Bahn Berlin network, which turns out to be computationally fruitful. Y1 - 2023 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2023.7 VL - 115 SP - 7:1 EP - 7:18 ER - TY - CHAP A1 - Masing, Berenike A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice T2 - 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) N2 - We consider maintenance sites for urban rail systems, where unavailable tracks typically require changes to the regular timetable, and often even to the line plan. In this paper, we present an integrated mixed-integer linear optimization model to compute an optimal line plan that makes best use of the available tracks, together with a periodic timetable, including its detailed routing on the tracks within the stations. The key component is a flexible, turn-sensitive event-activity network that allows to integrate line planning and train routing using a track choice extension of the Periodic Event Scheduling Problem (PESP). Major goals are to maintain as much of the regular service as possible, and to keep the necessary changes rather local. Moreover, we present computational results on real construction site scenarios on the S-Bahn Berlin network. We demonstrate that this integrated problem is indeed solvable on practically relevant instances. Y1 - 2023 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2023.5 VL - 115 SP - 5:1 EP - 5:15 ER - TY - CHAP A1 - Masing, Berenike ED - Trautmann, Norbert ED - Drägi, Mario T1 - Optimal Line Planning in the Parametric City T2 - Operations Research Proceedings 2021. OR 2021. N2 - We formulate the line planning problem in public transport as a mixed integer linear program (MILP), which selects both passenger and vehicle routes, such that travel demands are met with respect to minimized travel times for both operators and users. We apply MILP to the Parametric City, a generic city model developed by Fielbaum et al. [2]. While the infrastructure graph and demand are entirely rotation symmetric, asymmetric optimal line plans can occur. Using group theory, we analyze the properties of symmetric solutions and introduce a symmetry gap to measure their deviation of the optimum. We also develop a 1+1+2√g-approximation algorithm, depending only on the cost related parameter g. Supported by computational experiments, we conclude that in practice symmetric line plans provide good solutions for the line planning problem in the Parametric City. Y1 - 2022 SN - 978-3-031-08623-6 U6 - https://doi.org/10.1007/978-3-031-08623-6_7 SP - 39 EP - 44 PB - Springer, Cham ER - TY - CHAP A1 - Lindner, Niels A1 - van Lieshout, Rolf T1 - Benders Decomposition for the Periodic Event Scheduling Problem T2 - Operations Research Proceedings 2021 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. Y1 - 2022 U6 - https://doi.org/10.1007/978-3-031-08623-6_43 SP - 289 EP - 294 PB - Springer International Publishing CY - Cham ER - TY - CHAP A1 - Löbel, Fabian A1 - Lindner, Niels A1 - Borndörfer, Ralf ED - Neufeld, Janis S. ED - Buscher, Udo ED - Lasch, Rainer ED - Möst, Dominik ED - Schönberger, Jörn T1 - The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing T2 - Operations Research Proceedings 2019 N2 - The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances. Y1 - 2020 SN - 978-3-030-48438-5 U6 - https://doi.org/https://doi.org/10.1007/978-3-030-48439-2_92 SP - 757 EP - 763 PB - Springer International Publishing CY - Cham ER - TY - GEN ED - D'Emidio, Mattia ED - Lindner, Niels T1 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - OASIcs, Volume 106, ATMOS 2022, Complete Volume Y1 - 2022 SN - 978-3-95977-259-4 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022 VL - 106 PB - Schloss Dagstuhl -- Leibniz-Zentrum für Informatik ER - TY - CHAP A1 - Prause, Felix A1 - Borndörfer, Ralf T1 - A Bayesian Rolling Horizon Approach for Rolling Stock Rotation Planning with Predictive Maintenance T2 - 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) N2 - We consider the rolling stock rotation planning problem with predictive maintenance (RSRP-PdM), where a timetable given by a set of trips must be operated by a fleet of vehicles. Here, the health states of the vehicles are assumed to be random variables, and their maintenance schedule should be planned based on their predicted failure probabilities. Utilizing the Bayesian update step of the Kalman filter, we develop a rolling horizon approach for RSRP-PdM, in which the predicted health state distributions are updated as new data become available. This approach reduces the uncertainty of the health states and thus improves the decision-making basis for maintenance planning. To solve the instances, we employ a local neighborhood search, which is a modification of a heuristic for RSRP-PdM, and demonstrate its effectiveness. Using this solution algorithm, the presented approach is compared with the results of common maintenance strategies on test instances derived from real-world timetables. The obtained results show the benefits of the rolling horizon approach. Y1 - 2024 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2024.13 VL - 123 SP - 13:1 EP - 13:19 ER - TY - CHAP A1 - Bortoletto, Enrico A1 - Lindner, Niels ED - Voigt, Guido ED - Fliedner, Malte ED - Haase, Knut ED - Brüggemann, Wolfgang ED - Hoberg, Kai ED - Meissner, Jörn T1 - Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times T2 - Operations Research Proceedings 2023 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. Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-58405-3_51 SP - 397 EP - 402 ER - TY - CHAP A1 - Ebert, Patricia A1 - Masing, Berenike A1 - Lindner, Niels A1 - Gleixner, Ambros T1 - Sorting Criteria for Line-based Periodic Timetabling Heuristics T2 - Operations Research Proceedings 2024. OR 2024 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%. Y1 - 2025 SP - 348 EP - 354 ER - TY - CHAP A1 - Franke, Paula A1 - Hamacher, Kay A1 - Manns, Paul T1 - Minimizing and Maximizing the Shannon Entropy for Fixed Marginals T2 - Operations Research Proceedings 2025 N2 - The mutual information (MI) between two random variables is an important correlation measure in data analysis. The Shannon entropy of a joint probability distri- bution is the variable part under fixed marginals. We aim to minimize and maximize it to obtain the largest and smallest MI possible in this case, leading to a scaled MI ratio for better comparability. We present algorithmic approaches and optimal solutions for a set of problem instances based on data from molecular evolution. We show that this allows us to construct a sensible, systematic correction to raw MI values. Y1 - 2026 ER - TY - CHAP A1 - Riccardi, Gabor A1 - Lindner, Niels T1 - On The Minimum-Weight Forward (Weakly) Fundamental Cycle Basis Problem in Directed Graphs T2 - International Network Optimization Conference 2026 (INOC 2026) N2 - The cycle space of a directed graph is generated by a cycle basis, where, in general, cycles are allowed to have both forward and backward arcs. In a forward cycle, all arcs have to follow the given direction. We study the existence, structure, and computational complexity of minimum-weight forward cycle bases in directed graphs. We give a complete structural characterization of digraphs that admit weakly fundamental (and hence integral) forward cycle bases, showing that this holds if and only if every block is either strongly connected or a single arc. We further provide an easily verifiable characterization of when a strongly connected digraph admits a forward fundamental cycle basis, proving that such a basis exists if and only if the set of directed cycles has cardinality equal to the cycle rank; in this case, the basis is unique and computable in polynomial time, and nonexistence can likewise be certified efficiently. Lastly, we show that while minimum-weight forward fundamental cycle bases can be found in polynomial time whenever they exist, the minimum-weight forward weakly fundamental cycle basis problem is NP-hard via a polynomial-time reduction from the minimum-weight weakly fundamental cycle basis problem on digraphs with metric weights. Y1 - 2026 ER -