@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{BorndoerferHeismann, author = {Bornd{\"o}rfer, Ralf and Heismann, Olga}, title = {Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14564}, number = {11-46}, abstract = {Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially.}, language = {en} } @misc{BorndoerferLangenhanLoebeletal., author = {Bornd{\"o}rfer, Ralf and Langenhan, Andreas and L{\"o}bel, Andreas and Schulz, Christof and Weider, Steffen}, title = {Duty Scheduling Templates}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14699}, number = {12-09}, abstract = {We propose duty templates as a novel concept to produce similar duty schedules for similar days of operation in public transit. Duty templates can conveniently handle various types of similarity requirements, and they can be implemented with ease using standard algorithmic techniques. They have produced good results in practice.}, language = {en} } @misc{BorndoerferLoebelReutheretal., author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Rapid Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14728}, number = {12-10}, abstract = {We propose rapid branching (RB) as a general branch-and-bound heuristic for solving large scale optimization problems in traffic and transport. The key idea is to combine a special branching rule and a greedy node selection strategy in order to produce solutions of controlled quality rapidly and efficiently. We report on three successful applications of the method for integrated vehicle and crew scheduling, railway track allocation, and railway vehicle rotation planning.}, language = {en} } @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{BorndoerferHoppmannKarbstein, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {A Configuration Model for the Line Planning Problem}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2013.68}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-41903}, abstract = {We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model.}, language = {en} }