@misc{BrettHobergPachecoetal.2015, author = {Brett, Charles and Hoberg, Rebecca and Pacheco, Meritxell and Smith, Kyle and Bornd{\"o}rfer, Ralf and Euler, Ricardo and Gamrath, Gerwin and Grimm, Boris and Heismann, Olga and Reuther, Markus and Schlechte, Thomas and Tesch, Alexander}, title = {G-RIPS 2014 RailLab - Towards robust rolling stock rotations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53475}, year = {2015}, abstract = {The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an opportunity for high-achieving graduate-level students to work in teams on a real-world research project proposed by a sponsor from industry or the public sector. Each G-RIPS team consists of four international students (two from the US and two from European universities), an academic mentor, and an industrial sponsor. This is the report of the Rail-Lab project on the definition and integration of robustness aspects into optimizing rolling stock schedules. In general, there is a trade-off for complex systems between robustness and efficiency. The ambitious goal was to explore this trade-off by implementing numerical simulations and developing analytic models. In rolling stock planning a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects, have to be considered in an integrated model. General hypergraphs provide the modeling power to tackle those requirements. Furthermore, integer programming approaches are able to produce high quality solutions for the deterministic problem. When stochastic time delays are considered, the mathematical programming problem is much more complex and presents additional challenges. Thus, we started with a basic variant of the deterministic case, i.e., we are only considering hypergraphs representing vehicle composition and regularity. We transfered solution approaches for robust optimization from the airline industry to the setting of railways and attained a reasonable measure of robustness. Finally, we present and discuss different methods to optimize this robustness measure.}, language = {en} } @inproceedings{EulerBorndoerfer, author = {Euler, Ricardo and Bornd{\"o}rfer, Ralf}, title = {A Graph- and Monoid-based Framework for Price-Sensitive Routing in Local Public Transportation Networks}, series = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, volume = {75}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, doi = {10.4230/OASIcs.ATMOS.2019.12}, pages = {12:1 -- 12:15}, abstract = {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.}, language = {en} } @misc{Euler, type = {Master Thesis}, author = {Euler, Ricardo}, title = {The Bienstock Zuckerberg Algorithm for the Rolling Stock Rotation Problem}, pages = {73}, abstract = {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.}, language = {en} } @misc{BorndoerferEulerKarbsteinetal., author = {Bornd{\"o}rfer, Ralf and Euler, Ricardo and Karbstein, Marika and Mett, Fabian}, title = {Ein mathematisches Modell zur Beschreibung von Preissystemen im {\"o}V}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70564}, abstract = {Dieses Dokument fasst den Stand der mathematischen Modellierung von Preissystemen des {\"o}V mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen m{\"o}glich, die sich algorithmisch behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Tarifgraphen kann schon w{\"a}hrend einer Routenberechnung der Preis bestimmt werden. Wir beschreiben zun{\"a}chst das Konzept. Die konkrete Realisierung wird im Folgenden beispielhaft an den Tarifsystemen der Verkehrsverb{\"u}nde Warnow, MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erl{\"a}utert. Anschließend folgen {\"U}berlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbund{\"u}bergriffs.}, language = {de} } @misc{EulerBorndoerferStrunketal., author = {Euler, Ricardo and Bornd{\"o}rfer, Ralf and Strunk, Timo and Takkula, Tuomo}, title = {ULD Build-Up Scheduling with Dynamic Batching in an Air Freight Hub}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83482}, abstract = {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 standard MIP solvers 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.}, language = {en} } @inproceedings{EulerBorndoerferStrunketal., author = {Euler, Ricardo and Bornd{\"o}rfer, Ralf and Strunk, Timo and Takkula, Tuomo}, title = {ULD Build-Up Scheduling with Dynamic Batching in an Air Freight Hub}, series = {Operations Research Proceedings 2021}, booktitle = {Operations Research Proceedings 2021}, doi = {10.1007/978-3-031-08623-6_38}, pages = {254 -- 260}, abstract = {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.}, language = {en} } @article{BorndoerferEulerKarbstein2021, author = {Bornd{\"o}rfer, Ralf and Euler, Ricardo and Karbstein, Marika}, title = {Ein Graphen-basiertes Modell zur Beschreibung von Preissystemen im {\"o}ffentlichen Nahverkehr}, series = {HEUREKA 21}, volume = {002/127}, journal = {HEUREKA 21}, publisher = {FGSV}, address = {Stuttgart}, pages = {1 -- 15}, year = {2021}, abstract = {In dieser Arbeit wird ein graphenbasiertes Modell zur Einbindung von Preissystemen des {\"o}ffentlichen Nahverkehrs in Routing-Algorithmen vorgestellt. Jeder Knoten des Graphen repr{\"a}sentiert einen abstrakten Preiszustand einer Route und ist an einen tats{\"a}chlichen Preis gekoppelt. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen m{\"o}glich, diesich algorithmisch behandeln lassen. Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Ticketgraphen kann schon w{\"a}hrend einer Routenberechnung der Preis bestimmt werden. Dies erm{\"o}glicht die Berechnung von preisoptimalen Routen. An den Tarifsystemen der Verkehrsverb{\"u}nde MDV (Mitteldeutscher Verkehrsverbund) und VBB (Verkehrsverbund Berlin-Brandenburg) wird die Konstruktion des Modells detailliert erl{\"a}utert.}, language = {de} } @article{EulerLindnerBorndoerfer, author = {Euler, Ricardo and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {Price optimal routing in public transportation}, series = {EURO Journal on Transportation and Logistics}, 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}, language = {en} } @article{EulerLindnerBorndoerfer, author = {Euler, Ricardo and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {Price Optimal Routing in Public Transportation}, doi = {https://doi.org/10.48550/arXiv.2204.01326}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86414}, 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} } @article{EulerMaristanydelasCasas, author = {Euler, Ricardo and Maristany de las Casas, Pedro}, title = {Labeling Methods for Partially Ordered Paths}, abstract = {The landscape of applications and subroutines relying on shortest path computations continues to grow steadily. This growth is driven by the undeniable success of shortest path algorithms in theory and practice. It also introduces new challenges as the models and assessing the optimality of paths become more complicated. Hence, multiple recent publications in the field adapt existing labeling methods in an ad-hoc fashion to their specific roblem variant without considering the underlying general structure: they always deal with multi-criteria scenarios and those criteria define different partial orders on the paths. In this paper, we introduce the partial order shortest path problem (POSP), a generalization of the multi-objective shortest path problem (MOSP) and in turn also of the classical shortest path problem. POSP captures the particular structure of many shortest path applications as special cases. In this generality, we study optimality conditions or the lack of them, depending on the objective functions' properties. Our final contribution is a big lookup table summarizing our findings and providing the reader an easy way to choose among the most recent multicriteria shortest path algorithms depending on their weight structures. Examples range from time-dependent shortest path and bottleneck path problems to the fuzzy shortest path problem and complex financial weight functions studied in the public transportation community. Our results hold for general digraphs and therefore surpass previous generalizations that were limited to acyclic graphs.}, language = {en} }