TY - CHAP A1 - Marc, Goerigk A1 - Liebchen, Christian ED - D'Angelo, Gianlorenzo ED - Dollevoet, Twan T1 - An Improved Algorithm for the Periodic Timetabling Problem T2 - 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017) N2 - We consider the computation of periodic timetables, which is a key task in the service design process of public transportation companies. We propose a new approach for solving the periodic timetable optimisation problem. It consists of a (partially) heuristic network aggregation to reduce the problem size and make it accessible to standard mixed-integer programming (MIP) solvers. We alternate the invocation of a MIP solver with the well-known problem specific modulo network simplex heuristic (ModSim). This iterative approach helps the ModSim-method to overcome local minima efficiently, and provides the MIP solver with better initial solutions. Our computational experiments are based on the 16 railway instances of the PESPlib, which is the only currently available collection of periodic event scheduling problem instances. For each of these instances, we are able to reduce the objective values of previously best known solutions by at least 10.0%, and up to 22.8% with our iterative combined method. KW - periodic timetabling KW - railway optimisation KW - modulo network simplex KW - periodic event scheduling problem Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:526-opus4-9899 SN - 978-3-95977-042-2 SP - 12:1 EP - 12:14 PB - Schloss Dagstuhl / Leibniz-Zentrum für Informatik CY - Dagstuhl ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Liebchen, Christian A1 - Lindner, Niels ED - Borndörfer, Ralf ED - Storandt, Sabine T1 - A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable T2 - 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018) N2 - We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [Julius Paetzold et al., 2017], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same. KW - vehicle scheduling KW - periodic timetabling KW - bipartite matching Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:526-opus4-10549 SN - 978-3-95977-096-5 SP - 16:1 EP - 16:15 PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH CY - Wadern ER - TY - CHAP A1 - Lindner, Niels A1 - Liebchen, Christian T1 - New Perspectives on PESP: T-Partitions and Separators T2 - 19th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) N2 - In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions and dual bounds for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that have been proposed, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. This heuristic already had been proven to be useful in computational experiments [Ralf Borndörfer et al., 2019], and we locate it in the more general concept of what we denote T-partitions. With the second of these algorithms we propose to turn a strategy, that has been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time. KW - periodic event scheduling problem KW - periodic timetabling KW - graph partitioning KW - graph separators KW - balanced cuts Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:526-opus4-20074 SP - 2:1 EP - 2:18 PB - Schloss Dagstuhl, Leibniz-Zentrum für Informatik CY - Dagstuhl ER - TY - JOUR A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Timetable merging for the Periodic Event Scheduling Problem JF - EURO Journal on Transportation and Logistics 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. KW - periodic event scheduling problem KW - periodic timetabling KW - railway timetabling KW - PESPlib KW - benchmark solution KW - mixed-integer programming Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:526-opus4-16054 SN - 2192-4376 VL - 11 PB - Elsevier 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. KW - periodic event scheduling problem KW - periodic timetabling KW - mixed integer programming Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:526-opus4-13650 SN - 978-3-95977-170-2 SN - 2190-6807 PB - Schloss Dagstuhl, Leibniz-Zentrum für Informatik CY - Dagstuhl, Germany 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. KW - periodic timetabling KW - line planning KW - track choice KW - mixed-integer programming KW - construction site KW - railway rescheduling Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:526-opus4-17916 SN - 978-3-95977-302-7 SN - 2190-6807 VL - 115 SP - 5:1 EP - 5:15 ER -