@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} } @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{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{BorndoerferGrimmReutheretal.2019, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Optimization of handouts for rolling stock rotations}, journal = {Journal of Rail Transport Planning \& Management}, number = {10}, doi = {10.1016/j.jrtpm.2019.02.001}, pages = {1 -- 8}, year = {2019}, abstract = {A railway operator creates (rolling stock) rotations in order to have a precise master plan for the operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply traverses a set of operational days while covering trips of the timetable. As it is well known, the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging and still a topical research subject. Nevertheless, we study a completely different but strongly related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In our industrial application at DB Fernverkehr AG, the handout is exactly as important as the rotation itself. Moreover, it turns out that also other European railway operators use exactly the same methodology (but not terminology). Since a rotation can have many handouts of different quality, we show how to compute optimal ones through an integer program (IP) by standard software. In addition, a construction as well as an improvement heuristic are presented. Our computational results show that the heuristics are a very reliable standalone approach to quickly find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a computational comparison to the IP approach.}, language = {en} } @article{BeckenbachBorndoerfer2018, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {Hall's and Kőnig's theorem in graphs and hypergraphs}, volume = {341}, journal = {Discrete Mathematics}, number = {10}, doi = {10.1016/j.disc.2018.06.013}, pages = {2753 -- 2761}, year = {2018}, abstract = {We investigate the relation between Hall's theorem and Kőnig's theorem in graphs and hypergraphs. In particular, we characterize the graphs satisfying a deficiency version of Hall's theorem, thereby showing that this class strictly contains all Kőnig-Egerv{\´a}ry graphs. Furthermore, we give a generalization of Hall's theorem to normal hypergraphs.}, language = {en} } @article{SagnolBarnerBorndoerferetal.2018, author = {Sagnol, Guillaume and Barner, Christoph and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Mathes and Spies, Claudia and Wernecke, Klaus}, title = {Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations}, volume = {271}, journal = {European Journal of Operational Research}, number = {2}, doi = {10.1016/j.ejor.2018.05.022}, pages = {420 -- 435}, year = {2018}, abstract = {The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution, and a fixed assignment of jobs to machines must be computed. We propose a cutting-plane approach to solve the robust counterpart of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities. The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions. We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which only approximation approaches were known. Our model can be extended to balance the load over several planning periods in a rolling horizon. We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that: (i) our approach performs well compared to a previous model that ignored the distribution of case durations; (ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost; (iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available. Finally, we draw a number of managerial implications from these observations.}, language = {en} } @article{BorndoerferGrimmReutheretal.2017, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Template-based Re-optimization of Rolling Stock Rotations}, journal = {Public Transport}, publisher = {Springer}, doi = {10.1007/s12469-017-0152-4}, pages = {1 -- 19}, year = {2017}, abstract = {Rolling stock, i.e., the set of railway vehicles, is among the most expensive and limited assets of a railway company and must be used efficiently. We consider in this paper the re-optimization problem to recover from unforeseen disruptions. We propose a template concept that allows to recover cost minimal rolling stock rotations from reference rotations under a large variety of operational requirements. To this end, connection templates as well as rotation templates are introduced and their application within a rolling stock rotation planning model is discussed. We present an implementation within the rolling stock rotation optimization framework rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe.}, language = {en} } @article{BorndoerferKlugLamorgeseetal.2017, author = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, title = {Recent success stories on integrated optimization of railway systems}, volume = {74}, journal = {Transportation Research Part C: Emerging Technologies}, number = {1}, doi = {10.1016/j.trc.2016.11.015}, pages = {196 -- 211}, year = {2017}, abstract = {Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain developing mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice (e.g. Cacchiani et al., 2014; Bornd{\"o}rfer et al., 2010), with a few notable exceptions. In this paper we address three individual success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will discuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that mathematical optimization can support the planning of railway resources. Thus, mathematical models and optimization can lead to a greater efficiency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.}, language = {en} } @article{BorndoerferHoppmannKarbstein2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Passenger routing for periodic timetable optimization}, journal = {Public Transport}, publisher = {Springer-Verlag Berlin Heidelberg}, doi = {10.1007/s12469-016-0132-0}, year = {2016}, abstract = {The task of periodic timetabling is to determine trip arrival and departure times in a public transport system such that travel and transfer times are minimized. This paper investigates periodic timetabling models with integrated passenger routing. We show that different routing models can have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems by integrating passenger routing.}, language = {en} } @article{BorndoerferSagnolSchlechteetal.2016, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar}, title = {Optimal duty rostering for toll enforcement inspectors}, volume = {252(2)}, journal = {Annals of Operations Research}, edition = {252}, publisher = {Springer US}, doi = {10.1007/s10479-016-2152-1}, pages = {383 -- 406}, year = {2016}, abstract = {We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, we developed a personalized crew rostering model, to schedule the crews of the tours. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The main focus of this paper extends our previous publications on how different requirements for the rostering can be modeled in detail. The second focus is on a bi-criteria analysis of the planning problem to find the balance between the control quality and the roster acceptance. Finally, computational results on real-world instances show the practicability of our method and how different input parameters influence the problem complexity.}, language = {en} } @article{BorndoerferFuegenschuhKlugetal.2016, author = {Bornd{\"o}rfer, Ralf and F{\"u}genschuh, Armin and Klug, Torsten and Schang, Thilo and Schlechte, Thomas and Sch{\"u}lldorf, Hanno}, title = {The Freight Train Routing Problem for Congested Railway Networks with Mixed Traffic}, volume = {50}, journal = {Transportation Science}, number = {2}, doi = {10.1287/trsc.2015.0656}, pages = {408 -- 423}, year = {2016}, abstract = {We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that the sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. In this context, macroscopic refers to an aggregation of complex and large real-world structures into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We provide a mixed-integer nonlinear programming (MINLP) formulation for the FTRP, which is a multicommodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities originate from an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model (MILP) by piecewise linear approximation. The latter is solved by a state-of-the art MILP solver for various real-world test instances.}, language = {en} } @article{BeckenbachBorndoerferKnobenetal.2015, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf and Knoben, Loes and Kretz, David and Uetz, Marc J.}, title = {The S-Bahn Challenge in Berlin}, journal = {OR News}, number = {53}, pages = {10 -- 14}, year = {2015}, language = {en} } @article{BorndoerferHeismann2015, author = {Bornd{\"o}rfer, Ralf and Heismann, Olga}, title = {The hypergraph assignment problem}, volume = {15}, journal = {Discrete Optimization}, doi = {10.1016/j.disopt.2014.11.002}, pages = {15 -- 25}, year = {2015}, language = {en} } @article{BlancoBorndoerferBrueckneretal.2015, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Br{\"u}ckner, Michael and Hoang, Nam-Dung and Schlechte, Thomas}, title = {On the Path Avoiding Forbidden Pairs Polytope}, volume = {50}, journal = {Electronic Notes in Discrete Mathematics}, doi = {10.1016/j.endm.2015.07.057}, pages = {343 -- 348}, year = {2015}, abstract = {Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair.}, language = {en} } @article{BorndoerferReutherSchlechteetal.2016, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Waas, Kerstin and Weider, Steffen}, title = {Integrated Optimization of Rolling Stock Rotations for Intercity Railways}, volume = {50}, journal = {Transportation Science}, number = {3}, doi = {10.1287/trsc.2015.0633}, pages = {863 -- 877}, year = {2016}, abstract = {This paper proposes a highly integrated solution approach for rolling stock planning problems in the context of long distance passenger traffic between cities. The main contributions are a generic hypergraph-based mixed-integer programming model for the considered rolling stock rotation problem and an integrated algorithm for its solution. The newly developed algorithm is able to handle a large spectrum of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacities, and regularity aspects. We show that our approach has the power to produce rolling stock rotations that can be implemented in practice. In this way, the rolling stock rotations at the largest German long distance operator Deutsche Bahn Fernverkehr AG could be optimized by an automated system utilizing advanced mathematical programming techniques.}, language = {en} } @article{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Neue Planungsinstrumente nutzen: Das Verkehrsangebot verbessern und Kosten sparen}, volume = {68}, journal = {Verkehr und Technik}, number = {7}, pages = {239 -- 243}, year = {2015}, abstract = {Wir illustrieren anhand des Liniennetzes der Stadt Potsdam das Potenzial mathematischer Methoden der Angebotsplanung. Wir zeigen, dass das "bestm{\"o}gliche" Verkehrsangebot stark von planerischen Vorgaben beeinflusst wird, mit denen man die Erreichung unterschiedlicher und teilweise gegenl{\"a}ufiger Ziele steuern kann. Die Komplexit{\"a}t des Systems f{\"u}hrt zum Auftreten von R{\"u}ckkoppelungseffekten, die man nicht mit Hilfe von Daumenregeln beherrschen kann. Vielmehr ist der Einsatz moderner Planungsverfahren in einer interdisziplin{\"a}ren Zusammenarbeit von politischen Entscheidungstr{\"a}gern, Verkehrsingenieuren und Mathematikern notwendig, um die aktuellen Herausforderungen in der Verkehrsplanung zu meistern. Der Artikel dokumentiert einen Beitrag zum 7. {\"O}PNV Innovationskongress des Ministeriums f{\"u}r Verkehr und Infrastruktur des Landes Baden-W{\"u}rttemberg, der vom 9.-11. M{\"a}rz 2015 in Freiburg stattfand.}, language = {de} } @article{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Metric inequalities for routings on direct connections with application to line planning}, volume = {18}, journal = {Discrete Optimization}, pages = {56 -- 73}, year = {2015}, abstract = {We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the well-known feasibility condition for arc capacities in ordinary multi-commodity flows. The condition can be expressed in terms of a class of metric inequalities for routings on direct connections. We illustrate the concept on the example of the line planning problem in public transport and present an application to large-scale real-world problems.}, language = {en} } @article{BorndoerferBuwayaSagnoletal.2015, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Network spot-checking games: Theory and application to toll enforcing in transportation networks}, volume = {65}, journal = {Networks}, publisher = {Wiley Periodicals, Inc.}, doi = {10.1002/net.21596}, pages = {312 -- 328}, year = {2015}, abstract = {We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of arcs to be controlled. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium (SSE) is more relevant for this problem and we give a mixed integer programming (MIP) formulation for this problem. We show that the computation of such an equilibrium is NP-hard. More generally, we prove that it is NP-hard to compute a SSE in a polymatrix game, even if the game is pairwise zero-sum. Then, we give some bounds on the price of spite, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we report computational experiments on instances constructed from real data, for an application to the enforcement of a truck toll in Germany. These numerical results show the efficiency of the proposed methods, as well as the quality of the bounds derived in this article.}, language = {en} } @article{BorndoerferDittbrennerLangenhanetal.2014, author = {Bornd{\"o}rfer, Ralf and Dittbrenner, Bastian and Langenhan, Andreas and Seidl, Stephan and Weider, Steffen}, title = {Integrierte Dienst- und Dienstreihenfolgeplanung zur Erh{\"o}hung der Fahrerzufriedenheit}, journal = {Straßenverkehrstechnik}, number = {9}, pages = {583 -- 591}, year = {2014}, language = {de} }