@article{BorndoerferHoppmannKarbsteinetal.2020, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and Lindner, Niels}, title = {Separation of cycle inequalities in periodic timetabling}, journal = {Discrete Optimization}, number = {35}, doi = {10.1016/j.disopt.2019.100552}, pages = {100552}, year = {2020}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.}, language = {en} } @article{BorndoerferLindnerRoth2020, author = {Bornd{\"o}rfer, Ralf and Lindner, Niels and Roth, Sarah}, title = {A Concurrent Approach to the Periodic Event Scheduling Problem}, journal = {Journal of Rail Transport Planning \& Management}, number = {15}, issn = {2210-9706}, doi = {10.1016/j.jrtpm.2019.100175}, pages = {100175}, year = {2020}, abstract = {We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.}, language = {en} } @article{MaristanydelasCasasSedenoNodaBorndoerfer2025, author = {Maristany de las Casas, Pedro and Sede{\~n}o-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {New Dynamic Programming Algorithm for the Multiobjective Minimum Spanning Tree Problem}, volume = {173}, journal = {Computers \& Operations Research}, arxiv = {http://arxiv.org/abs/2306.16203}, doi = {10.1016/j.cor.2024.106852}, pages = {106852}, year = {2025}, abstract = {The Multiobjective Minimum Spanning Tree (MO-MST) problem is a variant of the Minimum Spanning Tree problem, in which the costs associated with every edge of the input graph are vectors. In this paper, we design a new dynamic programming MO-MST algorithm. Dynamic programming for a MO-MST instance leads to the definition of an instance of the One-to-One Multiobjective Shortest Path (MOSP) problem and both instances have equivalent solution sets. The arising MOSP instance is defined on a so called transition graph. We study the original size of this graph in detail and reduce its size using cost dependent arc pruning criteria. To solve the MOSP instance on the reduced transition graph, we design the Implicit Graph Multiobjective Dijkstra Algorithm (IG-MDA), exploiting recent improvements on MOSP algorithms from the literature. All in all, the new IG-MDA outperforms the current state of the art on a big set of instances from the literature. Our code and results are publicly available.}, language = {en} } @article{GrimmHoogervorstBorndoerfer2025, author = {Grimm, Boris and Hoogervorst, Rowan and Bornd{\"o}rfer, Ralf}, title = {A Comparison of Two Models for Rolling Stock Scheduling}, volume = {59}, journal = {Transportation Science}, number = {5}, arxiv = {http://arxiv.org/abs/2312.09697}, doi = {10.1287/trsc.2024.0505}, year = {2025}, abstract = {A major step in the planning process of passenger railway operators is the assignment of rolling stock, that is, train units, to the trips of the timetable. A wide variety of mathematical optimization models have been proposed to support this task, which we discuss and argue to be justified in order to deal with operational differences between railway operators, and hence different planning requirements, in the best possible way. Our investigation focuses on two commonly used models, the composition model and the hypergraph model, that were developed for Netherlands Railways (NS) and DB Fernverkehr AG (DB), respectively. We compare these models in two distinct problem settings, an NS setting and DB-light setting and consider different model variants to tune the models to these settings. We prove that in both of these settings, the linear programming bounds of the two models are equally strong as long as a number of reasonable assumptions are met. However, through a numerical evaluation on NS and DB-light instances, we show that the numerical performance of the models strongly depends on the instances. Although the composition model is the most compact and fastest model for the NS instances, an adjusted version of this model grows quickly for the DB-light instances and is then outperformed by the considered hypergraph model variants. Moreover, we show that a depot-extended version of the hypergraph model is able to combine strengths of both models and show good performance on both the NS and DB-light instances.}, language = {en} } @article{MaristanydelasCasasSedenoNodaBorndoerferetal.2025, author = {Maristany de las Casas, Pedro and Sede{\~n}o-Noda, Antonio and Bornd{\"o}rfer, Ralf and Huneshagen, Max}, title = {K-Shortest Simple Paths Using Biobjective Path Search}, volume = {17}, journal = {Mathematical Programming Computation}, arxiv = {http://arxiv.org/abs/2309.10377}, doi = {10.1007/s12532-025-00276-0}, pages = {349 -- 384}, year = {2025}, abstract = {In this paper we introduce a new algorithm for the k-Shortest Simple Paths (K-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick (2012) that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.}, language = {en} } @misc{BorndoerferDenissenHelleretal.2021, author = {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 Schlechte, Thomas and S{\"o}hlke, Andreas and Steadman, William}, title = {Microscopic Timetable Optimization for a Moving Block System}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82547}, year = {2021}, 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{EulerBorndoerferStrunketal.2021, 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}, year = {2021}, 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{LoebelBorndoerferWeider2025, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Non-linear Battery Behavior in Electric Vehicle Scheduling Problems}, booktitle = {Operations Research Proceedings 2023. OR 2023.}, editor = {Voigt, Guido and Fliedner, Malte and Haase, Knut and Br{\"u}ggermann, Wolfgang and Hoberg, Kai and Meissner, Joern}, publisher = {Springer Nature Switzerland}, address = {Cham}, isbn = {9783031584046}, issn = {2731-040X}, doi = {10.1007/978-3-031-58405-3_53}, pages = {415 -- 421}, year = {2025}, abstract = {The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve.}, language = {en} } @inproceedings{EulerBorndoerferPuchertetal.2024, author = {Euler, Ricardo and Bornd{\"o}rfer, Ralf and Puchert, Christian and Takkula, Tuomo}, title = {ULD Build-Up Scheduling with Logic-Based Benders Decomposition}, volume = {14742}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, doi = {10.1007/978-3-031-60597-0_17}, pages = {259 -- 276}, year = {2024}, abstract = {We study a complex planning and scheduling problem arising from the build-up process of air cargo pallets and containers, collectively referred to as unit load devices (ULD), in which ULDs must be assigned to workstations for loading. Since air freight usually becomes available gradually along the planning horizon, ULD build-ups must be scheduled neither too early to avoid underutilizing ULD capacity, nor too late to avoid resource conflicts with other flights. Whenever possible, ULDs should be built up in batches, thereby giving ground handlers more freedom to rearrange cargo and utilize the ULD's capacity efficiently. The resulting scheduling problem has an intricate cost function and produces large time-expanded models, especially for longer planning horizons. We propose a logic-based Benders decomposition approach that assigns batches to time intervals and workstations in the master problem, while the actual schedule is decided in a subproblem. By choosing appropriate intervals, the subproblem becomes a feasibility problem that decomposes over the workstations. Additionally, the similarity of many batches is exploited by a strengthening procedure for no-good cuts. We benchmark our approach against a time-expanded MIP formulation from the literature on a publicly available data set. It solves 15\% more instances to optimality and decreases run times by more than 50\% in the geometric mean. This improvement is especially pronounced for longer planning horizons of up to one week, where the Benders approach solves over 50\% instances more than the baseline}, 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}, 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} } @misc{MaristanydelasCasasSedenoNodaBorndoerfer2021, author = {Maristany de las Casas, Pedro and Sedeno-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {An Improved Multiobjective Shortest Path Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79712}, year = {2021}, abstract = {We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes the minimal complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm \emph{Multiobjective Dijkstra Algorithm} (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins', which we improved using new data structures and pruning techniques. On average, the MDA is \$\times2\$ to \$\times9\$ times faster on all used graph types. On some instances the speedup reaches an order of magnitude.}, language = {en} } @misc{PrauseBorndoerferGrimmetal.2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating the RSRP with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89531}, year = {2023}, abstract = {We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.}, language = {en} } @misc{LoebelBorndoerferWeider2024, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Electric Bus Scheduling with Non-Linear Charging, Power Grid Bottlenecks, and Dynamic Recharge Rates}, arxiv = {http://arxiv.org/abs/2407.14446}, year = {2024}, abstract = {Public transport operators are gradually electrifying their bus fleets, predominantly with battery-powered drive trains. These buses commonly have to be scheduled to recharge in-service, which gives rise to a number of challenges. A major problem is that the relationship between charging time and replenished driving range is non-linear, which is often approximately modeled. We examine the associated approximation error and show how it can result in a gross over- or underestimation of the fleet size. Moreover, we demonstrate that commonly used piecewise linear underestimations of the charge curve do not result in an underestimation of the predicted charge states in electric vehicle scheduling and routing models. Furthermore, since power grid upgrades are currently not keeping up with an ever growing electricity demand, operators are introducing active charge management tools to dynamically adjust the charging speed depending on the amount of available energy. It is therefore imperative to extend electric bus scheduling models to account for these developments. We propose a novel mixed-integer programming formulation for the electric bus scheduling problem featuring an improved approximation of the non-linear battery charging behavior as well as dynamic recharge speeds to accommodate grid load limits. The idea is to linearly interpolate what we call the charge increment function, which is closely related to the derivative of the commonly used charge curve. This provides very good error control and integrates easily into integer programming models. We demonstrate the practical usefulness of our model on a diverse library of real-life instances.}, language = {en} } @inproceedings{BorndoerferLoebelLoebeletal.2024, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and L{\"o}bel, Fabian and Weider, Steffen}, title = {Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach}, volume = {123}, booktitle = {24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2024.11}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-211992}, pages = {11:1 -- 11:16}, year = {2024}, abstract = {Attractive and cost-efficient public transport requires solving computationally difficult optimization problems from network design to crew rostering. While great progress has been made in many areas, new requirements to handle increasingly complex constraints are constantly coming up. One such challenge is a new type of resource constraints that are used to deal with the state-of-charge of battery-electric vehicles, which have limited driving ranges and need to be recharged in-service. Resource constrained vehicle scheduling problems can classically be modelled in terms of either a resource constrained (multi-commodity) flow problem or in terms of a path-based set partition problem. We demonstrate how a novel integrated version of both formulations can be leveraged to solve resource constrained vehicle scheduling with replenishment in general and the electric bus scheduling problem in particular by Lagrangian relaxation and the proximal bundle method.}, language = {en} } @article{PrauseBorndoerfer2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {An Iterative Refinement Approach for the Rolling Stock Rotation Problem with Predictive Maintenance}, arxiv = {http://arxiv.org/abs/2404.08367}, year = {2024}, abstract = {The rolling stock rotation problem with predictive maintenance (RSRP-PdM) involves the assignment of trips to a fleet of vehicles with integrated maintenance scheduling based on the predicted failure probability of the vehicles. These probabilities are determined by the health states of the vehicles, which are considered to be random variables distributed by a parameterized family of probability distribution functions. During the operation of the trips, the corresponding parameters get updated. In this article, we present a dual solution approach for RSRP-PdM and generalize a linear programming based lower bound for this problem to families of probability distribution functions with more than one parameter. For this purpose, we define a rounding function that allows for a consistent underestimation of the parameters and model the problem by a state-expanded event-graph in which the possible states are restricted to a discrete set. This induces a flow problem that is solved by an integer linear program. We show that the iterative refinement of the underlying discretization leads to solutions that converge from below to an optimal solution of the original instance. Thus, the linear relaxation of the considered integer linear program results in a lower bound for RSRP-PdM. Finally, we report on the results of computational experiments conducted on a library of test instances.}, language = {en} } @article{PrauseBorndoerferGrimmetal.2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating rolling stock rotations with integrated predictive maintenance}, volume = {30}, journal = {Journal of Rail Transport Planning \& Management}, doi = {10.1016/j.jrtpm.2024.100434}, pages = {100434}, year = {2024}, abstract = {We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for six instances derived from real-world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.}, language = {en} } @article{SahinDigehsaraBorndoerfer2021, author = {Sahin, Guvenc and Digehsara, Amin Ahmadi and Bornd{\"o}rfer, Ralf}, title = {Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation}, volume = {96}, journal = {Open Access Series in Informatics (OASIcs), 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)}, doi = {10.4230/OASIcs.ATMOS.2021.17}, pages = {17:1 -- 17:6}, year = {2021}, abstract = {In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.}, language = {en} } @article{BorndoerferDaneckerWeiser2021, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {A Discrete-Continuous Algorithm for Free Flight Planning}, volume = {14}, journal = {Algorithms}, number = {1}, publisher = {MDPI}, issn = {1438-0064}, doi = {10.3390/a14010004}, pages = {4}, year = {2021}, abstract = {We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.}, language = {en} } @misc{PrauseBorndoerfer2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91734}, year = {2023}, abstract = {We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM.}, language = {en} } @misc{LoebelBorndoerferWeider2023, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Non-Linear Battery Behavior in Electric Vehicle Scheduling Problems}, issn = {1438-0064}, doi = {10.1007/978-3-031-58405-3_53}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92441}, year = {2023}, abstract = {The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve.}, language = {en} } @article{BorndoerferEsserFrankenbergeretal.2021, author = {Bornd{\"o}rfer, Ralf and Eßer, Thomas and Frankenberger, Patrick and Huck, Andreas and Jobmann, Christoph and Krostitz, Boris and Kuchenbecker, Karsten and Moorhagen, Kai and Nagl, Philipp and Peterson, Michael and Reuther, Markus and Schang, Thilo and Schoch, Michael and Sch{\"u}lldorf, Hanno and Sch{\"u}tz, Peter and Therolf, Tobias and Waas, Kerstin and Weider, Steffen}, title = {Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization}, volume = {51}, journal = {Informs Journal on Applied Analytics}, number = {1}, doi = {10.1287/inte.2020.1069}, pages = {42 -- 62}, year = {2021}, abstract = {Deutsche Bahn (DB) operates a large fleet of rolling stock (locomotives, wagons, and train sets) that must be combined into trains to perform rolling stock rotations. This train composition is a special characteristic of railway operations that distinguishes rolling stock rotation planning from the vehicle scheduling problems prevalent in other industries. DB models train compositions using hyperarcs. The resulting hypergraph models are ad-dressed using a novel coarse-to-fine method that implements a hierarchical column genera-tion over three levels of detail. This algorithm is the mathematical core of DB's fleet em-ployment optimization (FEO) system for rolling stock rotation planning. FEO's impact within DB's planning departments has been revolutionary. DB has used it to support the company's procurements of its newest high-speed passenger train fleet and its intermodal cargo locomotive fleet for cross-border operations. FEO is the key to successful tendering in regional transport and to construction site management in daily operations. DB's plan-ning departments appreciate FEO's high-quality results, ability to reoptimize (quickly), and ease of use. Both employees and customers benefit from the increased regularity of operations. DB attributes annual savings of 74 million euro, an annual reduction of 34,000 tons of CO2 emissions, and the elimination of 600 coupling operations in cross-border operations to the implementation of FEO.}, language = {en} } @article{SahinAhmadiBorndoerferetal.2020, author = {Sahin, Guvenc and Ahmadi, Amin and Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Multi-period line planning with resource transfers}, volume = {119}, journal = {Transportation Research Part C: Emerging Technologies}, doi = {10.1016/j.trc.2020.102726}, pages = {102726}, year = {2020}, abstract = {Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.}, language = {en} } @inproceedings{LoebelBorndoerferWeider2023, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, doi = {10.4230/OASIcs.ATMOS.2023.15}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-187765}, pages = {15:1 -- 15:6}, year = {2023}, abstract = {The ongoing electrification of logistics systems and vehicle fleets increases the complexity of associated vehicle routing or scheduling problems. Battery-powered vehicles have to be scheduled to recharge in-service, and the relationship between charging time and replenished driving range is non-linear. In order to access the powerful toolkit offered by mixed-integer and linear programming techniques, this battery behavior has to be linearized. Moreover, as electric fleets grow, power draw peaks have to be avoided to save on electricity costs or to adhere to hard grid capacity limits, such that it becomes desirable to keep recharge rates dynamic. We suggest a novel linearization approach of battery charging behavior for vehicle scheduling problems, in which the recharge rates are optimization variables and not model parameters.}, 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{EulerMaristanydelasCasasBorndoerfer2024, author = {Euler, Ricardo and Maristany de las Casas, Pedro and Bornd{\"o}rfer, Ralf}, title = {Logic-Constrained Shortest Paths for Flight Planning}, arxiv = {http://arxiv.org/abs/2412.13235}, year = {2024}, abstract = {The Logic-Constrained Shortest Path Problem (LCSP) combines a one-to-one shortest path problem with satisfiability constraints imposed on the routing graph. This setting arises in flight planning, where air traffic control (ATC) authorities are enforcing a set of traffic flow restrictions (TFRs) on aircraft routes in order to increase safety and throughput. We propose a new branch and bound-based algorithm for the LCSP. The resulting algorithm has three main degrees of freedom: the node selection rule, the branching rule and the conflict. While node selection and branching rules have been long studied in the MIP and SAT communities, most of them cannot be applied out of the box for the LCSP. We review the existing literature and develop tailored variants of the most prominent rules. The conflict, the set of variables to which the branching rule is applied, is unique to the LCSP. We analyze its theoretical impact on the B\&B algorithm. In the second part of the paper, we show how to model the Flight Planning Problem with TFRs as an LCSP and solve it using the branch and bound algorithm. We demonstrate the algorithm's efficiency on a dataset consisting of a global flight graph and a set of around 20000 real TFRs obtained from our industry partner Lufthansa Systems GmbH. We make this dataset publicly available. Finally, we conduct an empirical in-depth analysis of node selection rules, branching rules and conflicts. Carefully choosing an appropriate combination yields an improvement of an order of magnitude compared to an uninformed choice.}, language = {en} } @article{MaristanydelasCasasSedenoNodaBorndoerfer2021, author = {Maristany de las Casas, Pedro and Sedeno-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {An Improved Multiobjective Shortest Path Algorithm}, volume = {135}, journal = {Computers \& Operations Research}, doi = {10.1016/j.cor.2021.105424}, year = {2021}, abstract = {We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes a minimum complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm Multiobjective Dijkstra Algorithm (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins, which we improved using new data structures and pruning techniques. On average, the MDA is 2 to 9 times faster on all used graph types. On some instances the speedup reaches an order of magnitude.}, 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} } @article{MaristanydelasCasasBorndoerferKrausetal.2021, author = {Maristany de las Casas, Pedro and Bornd{\"o}rfer, Ralf and Kraus, Luitgard and Sede{\~n}o-Noda, Antonio}, title = {An FPTAS for Dynamic Multiobjective Shortest Path Problems}, volume = {14}, journal = {Algorithms}, number = {2}, doi = {https://doi.org/10.3390/a14020043}, pages = {1 -- 22}, year = {2021}, abstract = {The Dynamic Multiobjective Shortest Path problem features multidimensional costs that can depend on several variables and not only on time; this setting is motivated by flight planning applications and the routing of electric vehicles. We give an exact algorithm for the FIFO case and derive from it an FPTAS for both, the static Multiobjective Shortest Path (MOSP) problems and, under mild assumptions, for the dynamic problem variant. The resulting FPTAS is computationally efficient and beats the known complexity bounds of other FPTAS for MOSP problems.}, 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} } @inproceedings{EulerBorndoerferStrunketal.2022, 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}, booktitle = {Operations Research Proceedings 2021}, doi = {10.1007/978-3-031-08623-6_38}, pages = {254 -- 260}, year = {2022}, 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{MaristanydelasCasasKrausSedenoNodaetal.2023, author = {Maristany de las Casas, Pedro and Kraus, Luitgard and Sedeno-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {Targeted multiobjective Dijkstra Algorithm}, volume = {82}, journal = {Networks}, number = {3}, arxiv = {http://arxiv.org/abs/2110.10978}, doi = {10.1002/net.22174}, pages = {277 -- 298}, year = {2023}, abstract = {We introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. It is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. For any explored subpath, a label setting MOSP algorithm decides whether the subpath can be discarded or must be stored as part of the output. A major design choice is how to store subpaths from the moment they are first explored until the mentioned final decision can be made. The T-MDA combines the polynomially bounded size of the priority queue used in the MDA and alazy management of paths that are not in the queue. The running time bounds from the MDA remain valid. In practice, the T-MDA outperforms known algorithms from the literature and the increased memory consumption is negligible. In this paper, we benchmark the T-MDA against an improved version of the state of the art NAMOA∗drOne-to-One MOSP algorithm from the literature on a standard testbed.}, language = {en} } @inproceedings{MasingLindnerBorndoerfer2022, author = {Masing, Berenike and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {Optimal Line Plans in the Parametric City and the Impact of In-Motion Costs}, booktitle = {Operations Research Proceedings 2021}, editor = {Trautmann, Norbert and Dr{\"a}gi, Mario}, publisher = {Springer, Cham}, isbn = {978-3-031-08623-6}, doi = {10.1007/978-3-031-08623-6_44}, pages = {295 -- 301}, year = {2022}, abstract = {Line planning in public transport involves determining vehicle routes and assigning frequencies of service such that travel demands are satisfied. We evaluate how line plans, which are optimal with respect to in-motion costs (IMC), the objective function depending purely on arc-lengths for both user and operator costs, performs with respect to the value of resources consumed (VRC). The latter is an elaborate, socio-economic cost function which includes discomfort caused by delay, boarding and alighting times, and transfers. Even though discomfort is a large contributing factor to VRC and is entirely disregarded in IMC,  we observe that the two cost functions are qualitatively comparable.}, language = {en} } @inproceedings{BlancoBorndoerferMaristanydelasCasas2022, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Maristany de las Casas, Pedro}, title = {An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles}, volume = {106}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, doi = {10.4230/OASIcs.ATMOS.2022.1}, pages = {1:1 -- 1:15}, year = {2022}, abstract = {The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A∗ heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances.}, language = {en} } @article{MasingLindnerBorndoerfer2022, author = {Masing, Berenike and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {The price of symmetric line plans in the Parametric City}, volume = {166}, journal = {Transportation Research Part B: Methodological}, doi = {10.1016/j.trb.2022.10.009}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88613}, pages = {419 -- 443}, year = {2022}, abstract = {We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. We prove that the symmetry gap is small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations.}, language = {de} } @inproceedings{GrimmBorndoerferBushe2023, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Bushe, Julian}, title = {Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {https://doi.org/10.4230/OASIcs.ATMOS.2023.13}, pages = {13:1 -- 13:15}, year = {2023}, abstract = {The fundamental task of every passenger railway operator is to offer an attractive railway timetable to the passengers while operating it as cost efficiently as possible. The available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating costs are minimum. This so-called Rolling Stock Rotation Problem (RSRP) is well studied in the literature. In this paper we consider an acyclic version of the RSRP that includes vehicle maintenance. As the latter is an important aspect, maintenance services have to be planned simultaneously to ensure the rotation's feasibility in practice. Indeed, regular maintenance is important for the safety and reliability of the rolling stock as well as enforced by law in many countries. We present a new integer programming formulation that links a hyperflow to model vehicle compositions and their coupling decisions to a set of path variables that take care of the resource consumption of the individual vehicles. To solve the model we developed different column generation algorithms which are compared to each other as well as to the MILP flow formulation of [Ralf Bornd{\"o}rfer et al., 2016] on a test set of real world instances.}, language = {en} } @inproceedings{BorndoerferGrimmSchade2023, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Schade, Stanley}, title = {A Robustness Analysis of Long Distance Train Crew Schedules in Germany}, volume = {CCC 1}, booktitle = {Proceedings Of The Fifth Iinternational Conference On Railway Technology: Research, Development and Maintenance}, issn = {2753-3239}, doi = {10.4203/ccc.1.23.17}, year = {2023}, abstract = {Nowadays railway networks are highly complex and often very fragile systems. A wide variety of individual operations that influence each other have to go hand in hand to end up with a smoothly and efficiently running system. Many of these operations suffer from uncertainty as trains could be delayed, the signaling system be disrupted or scheduled crews could be ill. Usually these opartions could be organized hierarchically from long term strategical decisions to real time decision management. Each stage in the hierarchy defines a different mathematical optimization problem, which is solved sequentially. At every stage the knowledge about preceding or succeeding planning stages may vary and also the interaction between two stages in this chain of problems may vary from almost no interaction to highly dependent situations. This paper deals with a topic that is an example for the latter case, namely the interaction between vehicle schedules, vehicle punctuality, and crew schedules. To reduce the number of potential rescheduling actions we developed a software tool in cooperation with our practical partner DB Fernverkehr AG (DBF) to predict a certain set of critical crew schedules. This tool evaluates, predicts, and determines "bottlenecks" in the crew schedule in the sense of potentially required rescheduling actions due to likely delays. The approach was tested on real life crew and train timetable data of DBF and can be regarded as the computation of key performance indicators, which is often desired. For our experiments we had access to the operated timetable and crew schedule of DBF for periods of two and six weeks in 2019.}, language = {en} } @inproceedings{LoebelLindnerBorndoerfer2020, author = {L{\"o}bel, Fabian and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing}, booktitle = {Operations Research Proceedings 2019}, editor = {Neufeld, Janis S. and Buscher, Udo and Lasch, Rainer and M{\"o}st, Dominik and Sch{\"o}nberger, J{\"o}rn}, publisher = {Springer International Publishing}, address = {Cham}, isbn = {978-3-030-48438-5}, doi = {https://doi.org/10.1007/978-3-030-48439-2_92}, pages = {757 -- 763}, year = {2020}, abstract = {The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.}, language = {en} } @inproceedings{PrauseBorndoerfer2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {A Bayesian Rolling Horizon Approach for Rolling Stock Rotation Planning with Predictive Maintenance}, volume = {123}, booktitle = {24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)}, doi = {10.4230/OASIcs.ATMOS.2024.13}, pages = {13:1 -- 13:19}, year = {2024}, abstract = {We consider the rolling stock rotation planning problem with predictive maintenance (RSRP-PdM), where a timetable given by a set of trips must be operated by a fleet of vehicles. Here, the health states of the vehicles are assumed to be random variables, and their maintenance schedule should be planned based on their predicted failure probabilities. Utilizing the Bayesian update step of the Kalman filter, we develop a rolling horizon approach for RSRP-PdM, in which the predicted health state distributions are updated as new data become available. This approach reduces the uncertainty of the health states and thus improves the decision-making basis for maintenance planning. To solve the instances, we employ a local neighborhood search, which is a modification of a heuristic for RSRP-PdM, and demonstrate its effectiveness. Using this solution algorithm, the presented approach is compared with the results of common maintenance strategies on test instances derived from real-world timetables. The obtained results show the benefits of the rolling horizon approach.}, language = {en} }