@unpublished{LiebchenLehnertMehlertetal.2020, author = {Liebchen, Christian and Lehnert, Martin and Mehlert, Christian and Schiefelbusch, Martin}, title = {Betriebliche Effizienzgr{\"o}ßen f{\"u}r Ridepooling-Systeme}, doi = {10.15771/1318}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-13182}, pages = {1 -- 8}, year = {2020}, abstract = {Ridepooling stellt eine viel diskutierte Mobilit{\"a}tsform dar. Ad-hoc und in der Regel von mobilen Endger{\"a}ten {\"u}bermittelte Fahrtw{\"u}nsche einzelner Fahrg{\"a}ste werden bedarfsgesteuert, fahrplanfrei und vollflexibel zu m{\"o}glichst effizienten, geteilten Fahrten geb{\"u}ndelt, welche im Regelfall mit Vans oder Kleinbussen durchgef{\"u}hrt werden. Sowohl aus Betreibersicht als auch insbesondere aus der Sicht von Genehmigungsbeh{\"o}rden stellt sich dabei die Frage nach der betrieblichen Effizienz von Ridepooling-Systemen, welche nicht zuletzt f{\"u}r die Bewertung der Konformit{\"a}t zu {\"o}ffentlichen Verkehrsinteressen, speziell einer effizienten Nutzung {\"o}ffentlicher Verkehrsinfrastruktur, relevant sein k{\"o}nnen. In diesem Zuge werden teilweise auch bereits Aspekte wie Umwegfaktor, Besetzungsgrad und Leerkilometeranteil diskutiert. Im vorliegenden Beitrag werden diese Aspekte als ein Teilergebnis der Arbeit des FGSV-Arbeitskreises 1.6.1 "Verkehrliche Anforderungen an Ridepooling-Systeme" zu einem Kennzahlensystem zusammengef{\"u}gt, die vollst{\"a}ndigen Ausf{\"u}hrungen finden sich dabei in Liebchen et al. (2020).}, language = {de} } @article{KeNieLiebchenetal.2020, author = {Ke, Yu and Nie, Lei and Liebchen, Christian and Yuan, Wuyang and Wu, Xin}, title = {Improving Synchronization in an Air and High-Speed Rail Integration Service via Adjusting a Rail Timetable: A Real-World Case Study in China}, series = {Journal of Advanced Transportation}, volume = {2020}, journal = {Journal of Advanced Transportation}, publisher = {Hindawi}, issn = {2042-3195}, doi = {10.1155/2020/5081315}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-13105}, year = {2020}, abstract = {Air and high-speed rail (AH) integration services are gaining ground with the development of the high-speed railway and airline industries. A well-designed feeder train timetable with good synchronization is of great significance in an AH integration service, because it can improve the connectivity at transfer nodes and offer more opportunities for intermodal passengers to travel. In this study, we propose a multi-objective model of a feeder railway timetable problem in an AH integration service to improve synchronization. The aims of the optimization model are to maximize the number of synchronizations and the coverage of synchronized flights, as well as to minimize the transfer penalties of passengers. We focus on a scenario of a partial subnetwork in which one direction of a two-direction railroad line with one transfer station is considered. The model is applied to Shijiazhuang Zhengding International Airport, China. The results illustrate the effectiveness of the approach developed in the paper.}, language = {en} } @unpublished{LiebchenDutschJinetal.2021, author = {Liebchen, Christian and Dutsch, Steffen and Jin, Shiguang and Tomii, Norio and Wang, Yihui}, title = {The Ring Never Relieves}, doi = {10.15771/1479}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-14790}, pages = {1 -- 23}, year = {2021}, abstract = {Regarding the disposition of metro lines in order to recover from delays, in the literature there can be found two branches of contributions: On the one hand, there are descriptions of response rules such as expressing (also referred to as skip stop), holding and short-turning together with studies in what situation to apply which of them. On the other hand, there are fully-automated optimization models which make use of any possible driving and routing options, according to some specified objective function. To the best of our knowledge, we are not aware of any study that puts its focus specifically on ring lines (also known as circle or loop lines). Yet, in the absence in particular of more or less 'natural' time buffers in turnaround activities in the endpoints, the operation of a circle line is particularly challenging. In this spirit, we are collecting response rules that are applicable especially for circle lines. We sketch their impacts on the passengers' travel experience as well as on the resource schedules for the rolling stock and staff (train drivers). For selected response rules, we provide illustrative drawings. Moreover, we present the answers that experts of eleven metro networks that are operating circle lines were pointing to us during interviews. It turns out that despite the limited possibilities along circle lines there is a broad repertoire of response action that is taken on a regular basis - but also that some standard general response rule (expressing) is almost never applied in practice.}, language = {en} } @inproceedings{LindnerLiebchen2020, author = {Lindner, Niels and Liebchen, Christian}, title = {Determining All Integer Vertices of the PESP Polytope by Flipping Arcs}, series = {20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)}, 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 f{\"u}r Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-170-2}, issn = {2190-6807}, doi = {10.4230/OASIcs.ATMOS.2020.5}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-13650}, 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{LindnerLiebchenMasing2021, author = {Lindner, Niels and Liebchen, Christian and Masing, Berenike}, title = {Forward Cycle Bases and Periodic Timetabling}, series = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)}, booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-15408}, 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} } @article{Liebchen2017, author = {Liebchen, Christian}, title = {Quo vadis Taktfahrplanoptimierung im Eisenbahnverkehr?}, series = {Eisenbahntechnische Rundschau (ETR)}, volume = {66}, journal = {Eisenbahntechnische Rundschau (ETR)}, number = {1+2}, publisher = {DVV Media Group}, issn = {0013-2845}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-16701}, pages = {31 -- 35}, year = {2017}, abstract = {Von 2005 bis 2008 war es gelungen, f{\"u}r mehrere Netze des Schienenpersonenverkehrs durch den Einsatz mathematischer Optimierungsverfahren Verbesserungen in den Fahrpl{\"a}nen zu erzielen. Seither stehen weitere solche Eins{\"a}tze aus. Der vorliegende Beitrag reflektiert daher, ob die eingesetzten Methoden und nicht zuletzt ggf. sogar die Zielgruppe(n) einer Justierung bed{\"u}rfen.}, language = {de} } @incollection{MarcLiebchen2017, author = {Marc, Goerigk and Liebchen, Christian}, title = {An Improved Algorithm for the Periodic Timetabling Problem}, series = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)}, booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)}, editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan}, publisher = {Schloss Dagstuhl / Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl}, isbn = {978-3-95977-042-2}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-9899}, publisher = {Technische Hochschule Wildau}, pages = {12:1 -- 12:14}, year = {2017}, abstract = {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.}, language = {en} } @incollection{BorndoerferKarbsteinLiebchenetal.2018, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels}, title = {A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}, series = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)}, booktitle = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)}, editor = {Bornd{\"o}rfer, Ralf and Storandt, Sabine}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik GmbH}, address = {Wadern}, isbn = {978-3-95977-096-5}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-10549}, publisher = {Technische Hochschule Wildau}, pages = {16:1 -- 16:15}, year = {2018}, abstract = {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.}, language = {en} } @inproceedings{MasingLindnerLiebchen2023, author = {Masing, Berenike and Lindner, Niels and Liebchen, Christian}, title = {Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice}, series = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, isbn = {978-3-95977-302-7}, issn = {2190-6807}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-17916}, pages = {5:1 -- 5:15}, year = {2023}, abstract = {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.}, language = {en} } @article{LindnerLiebchen2022, author = {Lindner, Niels and Liebchen, Christian}, title = {Timetable merging for the Periodic Event Scheduling Problem}, series = {EURO Journal on Transportation and Logistics}, volume = {11}, journal = {EURO Journal on Transportation and Logistics}, publisher = {Elsevier}, issn = {2192-4376}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-16054}, year = {2022}, 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} } @unpublished{Liebchen2021, author = {Liebchen, Christian}, title = {Maximizing Bidirectional Green Waves for Major Road Axes}, doi = {10.15771/2827}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:526-opus4-15449}, pages = {1 -- 20}, year = {2021}, abstract = {Both, from an environmental perspective and with respect to road traffic flow quality, planning so-called green waves along major road axes is a well-established target for traffic engineers. For one-way road axes (e.g. the Avenues in Manhattan), this is a trivial downstream task. For bidirectional arterials, the well-known necessary condition for establishing a green wave in both direction is that the driving times between two subsequent crossings must be an integer multiple of half of the cycle time of the signal programs at the nodes. In this paper, we propose an integer linear optimization model to establish fixed-time green waves in both directions that are as long and as wide as possible, even in the situation where the driving time condition is not fulfilled. In particular, we are considering an arterial along whose nodes separate left-turn signal groups are realized. In our computational results, we provide examples which illustrate that allowing for selecting among different strategies for the left-turn phases is beneficial. Moreover, we show that there is always a solution with green waves in both directions that are as long and as wide as possible, where absolute priority is put on just one direction. Only when considering prioritized parts of a green band (e.g. some first few seconds), then an ideal green wave into one direction can provide suboptimal quality compared to optimizing both directions together.}, language = {en} }