TY - CHAP A1 - Euler, Ricardo A1 - Borndörfer, Ralf T1 - A Graph- and Monoid-based Framework for Price-Sensitive Routing in Local Public Transportation Networks T2 - 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) N2 - We present a novel framework to mathematically describe the fare systems of local public transit companies. The model allows the computation of a provably cheapest itinerary even if prices depend on a number of parameters and non-linear conditions. Our approach is based on a ticket graph model to represent tickets and their relation to each other. Transitions between tickets are modeled via transition functions over partially ordered monoids and a set of symbols representing special properties of fares (e.g. surcharges). Shortest path algorithms rely on the subpath optimality property. This property is usually lost when dealing with complicated fare systems. We restore it by relaxing domination rules for tickets depending on the structure of the ticket graph. An exemplary model for the fare system of Mitteldeutsche Verkehrsbetriebe (MDV) is provided. By integrating our framework in the multi-criteria RAPTOR algorithm we provide a price-sensitive algorithm for the earliest arrival problem and assess its performance on data obtained from MDV. We discuss three preprocessing techniques that improve run times enough to make the algorithm applicable for real-time queries. Y1 - 2019 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2019.12 VL - 75 SP - 12:1 EP - 12:15 ER - TY - THES A1 - Husemann, Christoph T1 - Multimodales Routing mit Leihfahrradsystemen am Beispiel Berlins N2 - The aim of multimodal routing is to extract the best integrated journey of multiple transportation networks. The integration of bike rental networks is challenging particularly with respect to recognizing a valid path dependent on real-time availability of bike boarding and alighting places. In this work a common model for station-based bike rental networks extended with boarding possibilities for free floating bikes is presented. Moreover a new model for alighting inside a free floating area is introduced. In addition, a prototype of multimodal routing with a bike rental network in Berlin is developed by extending the OpenTripPlanner software. Due to recent public dispute about bike rental networks in Berlin, an examination about speed-up potential of an integrated bike rental network in the public transit of Berlin is provided. Y1 - 2018 ER - TY - THES A1 - Euler, Ricardo T1 - The Bienstock Zuckerberg Algorithm for the Rolling Stock Rotation Problem N2 - The design of rolling stock rotations is an important task in large-scale railway planning. This so-called rolling stock rotation problem (RSRP) is usually tackled using an integer programming approach. Markus Reuther did so in his dissertation [15] for the ICE railway network of DB ("Deutsche Bahn"). Due to the size of the network and the complexity of further technical requirements, the resulting integer problems tend to become very large and computationally involved. In this thesis, we tackle the linear programming relaxation of the RSRP integer program. We will do so by applying a modified version of an algorithm recently proposed by Dan Bienstock and Mark Zuckerberg [2] for the precedence constrained production scheduling problem that arises in open pit mine scheduling. This problem contains a large number of "easy" constraints and a relatively small number of "hard" constraints. We will see that a similar problem structure can also be found in the RSRP. The Bienstock-Zuckerberg algorithm relies on applying Lagrangian relaxation to the hard constraints as well as on partitioning the variable set. We propose three different partition schemes which try to exploit the specific problem structure of the RSRP. Furthermore, we will discuss the influence of primal degeneracy on the algorithm's performance, as well as possible merits of perturbating the right-hand side of the constraint matrix. We provide computational results to assess the performance of those approaches. Y1 - 2018 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Euler, Ricardo A1 - Karbstein, Marika A1 - Mett, Fabian T1 - Ein mathematisches Modell zur Beschreibung von Preissystemen im öV N2 - Dieses Dokument fasst den Stand der mathematischen Modellierung von Preissystemen des öV mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Tarifgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Wir beschreiben zunächst das Konzept. Die konkrete Realisierung wird im Folgenden beispielhaft an den Tarifsystemen der Verkehrsverbünde Warnow, MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erläutert. Anschließend folgen Überlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbundübergriffs. T3 - ZIB-Report - 18-47 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70564 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Euler, Ricardo A1 - Karbstein, Marika T1 - Ein Graphen-basiertes Modell zur Beschreibung von Preissystemen im öffentlichen Nahverkehr JF - HEUREKA 21 N2 - In dieser Arbeit wird ein graphenbasiertes Modell zur Einbindung von Preissystemen des öffentlichen Nahverkehrs in Routing-Algorithmen vorgestellt. Jeder Knoten des Graphen repräsentiert einen abstrakten Preiszustand einer Route und ist an einen tatsächlichen Preis gekoppelt. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen möglich, diesich algorithmisch behandeln lassen. Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Ticketgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Dies ermöglicht die Berechnung von preisoptimalen Routen. An den Tarifsystemen der Verkehrsverbünde MDV (Mitteldeutscher Verkehrsverbund) und VBB (Verkehrsverbund Berlin-Brandenburg) wird die Konstruktion des Modells detailliert erläutert. Y1 - 2021 UR - https://verlag.fgsv-datenbanken.de/tagungsbaende?kat=HEUREKA&subkat=FGSV+002%2F127+%282021%29&fanr=&va=&titel=&text=&autor=&tagungsband=1256&_titel=Ein+Graphen-basiertes+Modell+zur+Beschreibung+von+Preissystemen+im+%C3%B6ffentlichen+Nahverkehr VL - 002/127 SP - 1 EP - 15 PB - FGSV CY - Stuttgart ER - TY - JOUR A1 - Euler, Ricardo A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - Price optimal routing in public transportation JF - EURO Journal on Transportation and Logistics KW - Management Science and Operations Research KW - Transportation KW - Modeling and Simulation Y1 - 2024 U6 - https://doi.org/10.1016/j.ejtl.2024.100128 SN - 2192-4376 VL - 13 SP - 1 EP - 15 PB - Elsevier BV 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 -