@misc{BorndoerferReutherSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Vehicle Rotation Planning for Intercity Railways}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14731}, number = {12-11}, abstract = {This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers.}, language = {en} } @misc{BorndoerferKarbstein, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {A Note on Menger's Theorem for Hypergraphs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14471}, number = {12-03}, abstract = {We prove the companion Theorem to Menger's Theorem for hypergraphs. This result gives rise to a new class of blocking pairs of ideal matrices, that generalize the incidence matrices of cuts and paths.}, language = {en} } @misc{BorndoerferKarbstein, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {A Direct Connection Approach to Integrated Line Planning and Passenger Routing}, series = {ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, volume = {25}, journal = {ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Delling, Daniel and Liberti, Leo}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, issn = {1438-0064}, doi = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2012.47}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15812}, pages = {47 -- 57}, abstract = {The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.}, language = {en} } @misc{BorndoerferSagnolSwarat, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {A Case Study on Optimizing Toll Enforcements on Motorways}, issn = {1438-0064}, doi = {10.4230/OASIcs.SCOR.2012.1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15498}, abstract = {In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.}, language = {en} } @misc{BorndoerferDovicaNowaketal., author = {Bornd{\"o}rfer, Ralf and Dovica, Ivan and Nowak, Ivo and Schickinger, Thomas}, title = {Robust Tail Assignment}, organization = {Zuse-Institut Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11707}, number = {10-08}, abstract = {We propose an efficient column generation method to minimize the probability of delay propagations along aircraft rotations. In this way, delay resistant schedules can be constructed. Computational results for large-scale real-world problems demonstrate substantial punctuality improvements. The method can be generalized to crew and integrated scheduling problems.}, language = {en} } @misc{BorndoerferNeumann, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika}, title = {Models for Line Planning with Transfers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11742}, number = {10-11}, abstract = {We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by "connection capacities" into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results.}, language = {en} } @misc{BorndoerferGroetschelLoebel, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {The Quickest Path to the Goal}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11840}, number = {10-21}, abstract = {We provide an introduction into the mathematics of and with paths. Not on the shortest, but hopefully on an entertaining path!}, language = {en} } @misc{Borndoerfer, author = {Bornd{\"o}rfer, Ralf}, title = {Discrete Optimization in Public Transportation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11207}, number = {08-56}, abstract = {The mathematical treatment of planning problems in public transit has made significant advances in the last decade. Among others, the classical problems of vehicle and crew scheduling can nowadays be solved on a routine basis using combinatorial optimization methods. This is not yet the case for problems that pertain to the design of public transit networks, and for the problems of operations control that address the implementation of a schedule in the presence of disturbances. The article gives a sketch of the state and important developments in these areas, and it addresses important challenges. The vision is that mathematical tools of computer aided scheduling (CAS) will soon play a similar role in the design and operation of public transport systems as CAD systems in manufacturing.}, language = {en} } @misc{BorndoerferCardonha, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Set Partitioning Approach to Shunting}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11326}, number = {09-18}, abstract = {The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems.}, language = {en} } @misc{BorndoerferCardonha, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Binary Quadratic Programming Approach to the Vehicle Positioning Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11242}, number = {09-12}, abstract = {The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view.}, language = {en} } @misc{BorndoerferHoang, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung}, title = {Fair Ticket Prices in Public Transport}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10999}, number = {08-46}, abstract = {Ticket pricing in public transport usually takes a welfare or mnemonics maximization point of view. These approaches do not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and integer programming. An application to pricing railway tickets for the intercity network of the Netherlands demonstrates that, in this sense, prices that are much fairer than standard ones can be computed in this way.}, language = {en} } @misc{BorndoerferScheltenSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Schelten, Uwe and Schlechte, Thomas and Weider, Steffen}, title = {A Column Generation Approach to Airline Crew Scheduling}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8713}, number = {05-37}, abstract = {The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH.}, language = {en} } @misc{BorndoerferLoebelWeider, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7898}, number = {04-14}, abstract = {This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.}, language = {en} } @misc{BorndoerferLoebelWeider, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"O}ffentlichen Nahverkehr}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6773}, number = {02-10}, abstract = {Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im {\"o}ffentlichen Nahverkehr. Der Ansatz zielt auf die Verbesserung des Gesamtwirkungsgrades dieser beiden Planungsschritte und auf die besondere Planungsproblematik im Regionalverkehr. Wir entwickeln dazu mathematische Optimierungstechniken f{\"u}r den Einsatz in den Planungssystemen MICROBUS II und DIVA.}, language = {de} } @misc{BorndoerferGroetschelLoebel, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Der Schnellste Weg zum Ziel}, doi = {10.1007/978-3-322-96366-6_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4209}, number = {SC-99-32}, abstract = {Wir geben eine Einf{\"u}hrung in die Mathematik von und mit Wegen. Nicht auf dem k{\"u}rzesten, aber auf einem hoffentlich kurzweiligen Weg!}, language = {de} } @misc{BorndoerferEisenblaetterGroetscheletal., author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {The Orientation Model for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5627}, number = {TR-98-01}, abstract = {Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem.}, language = {en} }