@misc{LindnerLiebchen2021, author = {Lindner, Niels and Liebchen, Christian}, title = {Timetable Merging for the Periodic Event Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81587}, year = {2021}, abstract = {We propose a new mixed integer programming based heuristic for computing new benchmark primal solutions for instances of the PESPlib. The PESPlib is a collection of instances for the Periodic Event Scheduling Problem (PESP), comprising periodic timetabling problems inspired by real-world railway timetabling settings, and attracting several international research teams during the last years. We describe two strategies to merge a set of good periodic timetables. These make use of the instance structure and minimum weight cycle bases, finally leading to restricted mixed integer programming formulations with tighter variable bounds. Implementing this timetable merging approach in a concurrent solver, we improve the objective values of the best known solutions for the smallest and largest PESPlib instances by 1.7 and 4.3 percent, respectively.}, language = {en} } @inproceedings{LindnerLiebchen2020, author = {Lindner, Niels and Liebchen, Christian}, title = {Determining all integer vertices of the PESP polytope by flipping arcs}, volume = {85}, booktitle = {20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)}, editor = {Huisman, Dennis and Zaroliagis, Christos D.}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2020.5}, pages = {5:1 -- 5:18}, year = {2020}, abstract = {We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. We finally present better dual bounds for the smallest and largest instance of the benchmarking library PESPlib.}, language = {en} } @inproceedings{LindnerMasingLiebchen2024, author = {Lindner, Niels and Masing, Berenike and Liebchen, Christian}, title = {Integrierte Baufahrplanoptimierung auf dem Netz der S-Bahn Berlin}, volume = {002/140}, booktitle = {HEUREKA'24 - Optimierung in Verkehr und Transport}, year = {2024}, abstract = {Zur Instandhaltung von Eisenbahnnetzen sind regelm{\"a}ßig Baumaßnahmen erforderlich. Diese erfordern stets Anpassungen der Fahrpl{\"a}ne. Um den Fahrg{\"a}sten trotz der Baumaßnahme weiterhin einen m{\"o}glichst großen Teil des Regelangebotes bieten zu k{\"o}nnen, bewegen sich die resultierenden Baufahrpl{\"a}ne insbesondere in Schnellbahnnetzen mit ihren dichten Zugfolgen h{\"a}ufig nahe der Kapazit{\"a}tsgrenze der Infrastruktur. Etablierte Verfahren zur Taktfahrplanoptimierung k{\"o}nnen diesen Anforderungen nicht gen{\"u}gen, da in der Praxis Anpassungen von Laufwegen der Linien, sowie der Gleisbelegungen h{\"a}ufig Teil der realisierten L{\"o}sungen sind. F{\"u}r diese Aufgabe haben die Autoren zuletzt ein Optimierungsmodell vorgestellt, welches diese M{\"o}glichkeiten aussch{\"o}pft. In dem vorliegenden Beitrag wird erstmalig dessen Anwendung auf ein unmittelbar der Praxis der Baufahrplanung entnommenes Beispiel aus dem Netz der Berliner S-Bahn im Detail beschrieben.}, language = {de} } @inproceedings{LindnerMasing2024, author = {Lindner, Niels and Masing, Berenike}, title = {SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice}, booktitle = {hEART 2024: 12th Symposium of the European Association for Research in Transportation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98066}, year = {2024}, abstract = {Periodic timetabling is a challenging planning task in public transport. As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turn-arounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network.}, language = {de} } @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} } @article{EulerLindnerBorndoerfer2024, author = {Euler, Ricardo and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {Price optimal routing in public transportation}, volume = {13}, journal = {EURO Journal on Transportation and Logistics}, publisher = {Elsevier BV}, issn = {2192-4376}, doi = {10.1016/j.ejtl.2024.100128}, pages = {1 -- 15}, year = {2024}, language = {en} } @article{MasingLindnerEbert2023, author = {Masing, Berenike and Lindner, Niels and Ebert, Patricia}, title = {Forward and Line-Based Cycle Bases for Periodic Timetabling}, volume = {4}, journal = {Operations Research Forum}, number = {3}, doi = {10.1007/s43069-023-00229-0}, pages = {53}, 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{SchlechteBorndoerferDenissenetal.2022, author = {Schlechte, Thomas and 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 S{\"o}hlke, Andreas and Steadman, William}, title = {Timetable Optimization for a Moving Block System}, volume = {22}, journal = {Journal of Rail Transport Planning \& Management}, issn = {2210-9706}, doi = {10.1016/j.jrtpm.2022.100315}, pages = {100315}, year = {2022}, 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{BortolettoLindnerMasing2022, author = {Bortoletto, Enrico and Lindner, Niels and Masing, Berenike}, title = {The Tropical and Zonotopal Geometry of Periodic Timetables}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2204.13501}, doi = {https://doi.org/10.1007/s00454-024-00686-2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86708}, year = {2022}, abstract = {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.}, language = {en} } @misc{BortolettoLindnerMasing2022, author = {Bortoletto, Enrico and Lindner, Niels and Masing, Berenike}, title = {Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2022.3}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-87385}, year = {2022}, abstract = {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.}, language = {en} } @misc{MasingLindnerLiebchen2022, author = {Masing, Berenike and Lindner, Niels and Liebchen, Christian}, title = {Periodic Timetabling with Integrated Track Choice for Railway Construction Sites}, issn = {1438-0064}, doi = {10.1016/j.jrtpm.2023.100416}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88626}, year = {2022}, abstract = {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.}, language = {en} } @article{EulerLindnerBorndoerfer2022, author = {Euler, Ricardo and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {Price Optimal Routing in Public Transportation}, arxiv = {http://arxiv.org/abs/2204.01326}, doi = {https://doi.org/10.48550/arXiv.2204.01326}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86414}, year = {2022}, abstract = {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.}, language = {en} }