@misc{BorndoerferHoppmannKarbsteinetal., author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and Lindner, Niels}, title = {Separation of Cycle Inequalities in Periodic Timetabling}, issn = {1438-0064}, doi = {https://doi.org/10.1016/j.disopt.2019.100552}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69746}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algo- rithm for cycle inequalities, and we give 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} } @misc{BorndoerferKarbsteinLiebchenetal., author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels}, title = {A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2018.16}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69688}, abstract = {We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [9], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.}, language = {en} } @misc{BorndoerferKarbsteinMehrgardtetal., author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Mehrgardt, Julika and Reuther, Markus and Schlechte, Thomas}, title = {The Cycle Embedding Problem}, issn = {1438-0064}, doi = {10.1007/978-3-319-28697-6_65}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52788}, abstract = {Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.}, language = {en} } @misc{BorndoerferKlugLamorgeseetal., 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 Optimization of Railway Systems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53726}, 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 cus- tomers 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 devel- oping 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, with a few notable exceptions. In this paper we address three 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 dis- cuss 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 math- ematical optimization can support the planning of rolling stock resources. Thus, mathematical models and optimization can lead to a greater effi- ciency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.}, language = {en} } @misc{BorndoerferLindnerRoth, author = {Bornd{\"o}rfer, Ralf and Lindner, Niels and Roth, Sarah}, title = {A Concurrent Approach to the Periodic Event Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71907}, 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} } @misc{BorndoerferMehrgardtReutheretal., author = {Bornd{\"o}rfer, Ralf and Mehrgardt, Julika and Reuther, Markus and Schlechte, Thomas and Waas, Kerstin}, title = {Re-optimization of Rolling Stock Rotations}, issn = {1438-0064}, doi = {10.1007/978-3-319-07001-8_8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42569}, abstract = {The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, i.e., vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites. We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG.}, language = {en} } @misc{BorndoerferOmontSagnoletal., author = {Bornd{\"o}rfer, Ralf and Omont, Bertrand and Sagnol, Guillaume and Swarat, Elmar}, title = {A Stackelberg game to optimize the distribution of controls in transportation networks}, issn = {1438-0064}, doi = {10.1007/978-3-642-35582-0_17}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14995}, abstract = {We propose a game theoretic model for the spatial distribution of inspectors on a transportation network. The problem is to spread out the controls so as to enforce the payment of a transit toll. We formulate a linear program to find the control distribution which maximizes the expected toll revenue, and a mixed integer program for the problem of minimizing the number of evaders. Furthermore, we show that the problem of finding an optimal mixed strategy for a coalition of \$N\$ inspectors can be solved efficiently by a column generation procedure. Finally, we give experimental results from an application to the truck toll on German motorways.}, language = {en} } @misc{BorndoerferReutherSchlechte, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51009}, abstract = {We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.}, language = {en} } @misc{BorndoerferReutherSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schulz, Christof and Swarat, Elmar and Weider, Steffen}, title = {Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56070}, abstract = {Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.}, language = {en} } @misc{BorndoerferReutherSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {A Hypergraph Model for Railway Vehicle Rotation Planning}, issn = {1438-0064}, doi = {/10.4230/OASIcs.ATMOS.2011.146}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-32746}, number = {11-36}, abstract = {We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.}, language = {en} } @misc{BorndoerferSagnolSchwartz, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schwartz, Stephan}, title = {An Extended Network Interdiction Problem for Optimal Toll Control}, issn = {1438-0064}, doi = {10.1016/j.endm.2016.03.040}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55405}, abstract = {We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.}, language = {en} } @misc{BorndoerferSchwartzSurau, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Vertex Covering with Capacitated Trees}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82616}, abstract = {The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs. Our focus is on the solution of the pricing problem which turns out to be a variant of the NP-hard Maximum Weight Connected Subgraph Problem. We compare different formulations to handle connectivity, and find that a single-commodity flow formulation performs best. This is notable since the respective literature seems to have dismissed this formulation. We improve it to a new coarse-to-fine flow formulation that is theoretically and computationally superior, especially for large instances with many vertices of degree 2 like highway networks, where it provides a speed-up factor of 10 over the non-flow-based formulations. We also propose a preprocessing method that exploits a median property of weight constrained subgraphs, a primal heuristic, and a local search heuristic. In an extensive computational study we evaluate the presented connectivity formulations on different classes of instances, and demonstrate the effectiveness of the proposed enhancements. Their speed-ups essentially multiply to an overall factor of 20. Overall, our approach allows the reliabe solution of instances with several hundreds of nodes in a few minutes. These findings are further corroborated in a comparison to existing districting models on a set of test instances from the literature.}, language = {en} } @inproceedings{BorndoerferSchwartzSurau, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Finding Minimum Balanced Separators - an Exact Approach}, series = {Operations Research Proceedings 2021}, booktitle = {Operations Research Proceedings 2021}, issn = {1438-0064}, doi = {https://doi.org/10.1007/978-3-031-08623-6_24}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83138}, pages = {154 -- 159}, abstract = {Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances.}, language = {en} } @misc{BorndoerferSchwartzSurau, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-84427}, language = {en} } @misc{BortolettoLindner, author = {Bortoletto, Enrico and Lindner, Niels}, title = {Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92315}, abstract = {The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.}, language = {en} } @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} } @misc{BreuerBussieckCaoetal., author = {Breuer, Thomas and Bussieck, Michael and Cao, Karl-Kien and Cebulla, Felix and Fiand, Frederik and Gils, Hans Christian and Gleixner, Ambros and Khabi, Dmitry and Koch, Thorsten and Rehfeldt, Daniel and Wetzel, Manuel}, title = {Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_85}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66183}, abstract = {Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.}, language = {en} } @misc{BreugemBorndoerferSchlechteetal., author = {Breugem, Thomas and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Schulz, Christof}, title = {A Three-Phase Heuristic for Cyclic Crew Rostering with Fairness Requirements}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74297}, abstract = {In this paper, we consider the Cyclic Crew Rostering Problem with Fairness Requirements (CCRP-FR). In this problem, attractive cyclic rosters have to be constructed for groups of employees, considering multiple, a priori determined, fairness levels. The attractiveness follows from the structure of the rosters (e.g., sufficient rest times and variation in work), whereas fairness is based on the work allocation among the different roster groups. We propose a three-phase heuristic for the CCRP-FR, which combines the strength of column generation techniques with a large-scale neighborhood search algorithm. The design of the heuristic assures that good solutions for all fairness levels are obtained quickly, and can still be further improved if additional running time is available. We evaluate the performance of the algorithm using real-world data from Netherlands Railways, and show that the heuristic finds close to optimal solutions for many of the considered instances. In particular, we show that the heuristic is able to quickly find major improvements upon the current sequential practice: For most instances, the heuristic is able to increase the attractiveness by at least 20\% in just a few minutes.}, language = {en} } @misc{BroseFuegenschuhGausemeieretal., author = {Brose, Achim and F{\"u}genschuh, Armin and Gausemeier, Pia and Vierhaus, Ingmar and Seliger, G{\"u}nther}, title = {A System Dynamic Enhancement for the Scenario Technique}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18150}, abstract = {The Scenario Technique is a strategic planning method that aims to describe and analyze potential developments of a considered system in the future. Its application consists of several steps, from an initial problem analysis over an influence analysis to projections of key factors and a definition of the scenarios to a final interpretation of the results. The technique itself combines qualitative and quantitative methods and is an enhancement of the standard Scenario Technique. We use the numerical values gathered during the influence analysis, and embed them in a System Dynamics framework. This yields a mathematically rigorous way to achieve predictions of the system's future behavior from an initial impulse and the feedback structure of the factors. The outcome of our new method is a further way of projecting the present into the future, which enables the user of the Scenario Technique to obtain a validation of the results achieved by the standard method.}, language = {en} } @misc{Buwaya, type = {Master Thesis}, author = {Buwaya, Julia}, title = {Optimizing control in a transportation network when users may choose their OD-path}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42330}, school = {Zuse Institute Berlin (ZIB)}, pages = {81}, abstract = {This thesis represents a game-theoretic investigation of the allocation of inspectors in a transportation network, comparing Nash and Stackelberg equilibrium strategies to a strategy in which inspections are conducted proportionally to the traffic volume. It contains specifications for the integration of space and time dependencies and extensive experimental tests for the application on the transportation network of German motorways using real data. Main results are that - although the formulated spot-checking game is not zero-sum - we are able to compute a Nash equilibrium using linear programming and secondly, that experimental results yield that a Nash equilibrium strategy represents a good trade-off for the Stackelberg equilibrium strategy between efficiency of controls and computation time.}, language = {en} }