@misc{BeckenbachBorndoerfer2015, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {A Hall Condition for Normal Hypergraphs}, issn = {1438-0064}, doi = {10.1016/j.disc.2018.06.013}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56175}, year = {2015}, abstract = {Conforti, Cornu{\´e}jols, Kapoor, and Vusković gave a Hall-type condition for the non-existence of a perfect matching in a balanced hypergraph. We generalize this result to the class of normal hypergraphs.}, 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} } @inproceedings{BorndoerferHoppmannKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Timetabling and Passenger Routing in Public Transport}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, year = {2015}, abstract = {The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.}, language = {en} } @misc{BorndoerferSagnolSchlechteetal.2013, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar}, title = {Optimal Toll Enforcement - an Integration of Vehicle Routing and Duty Rostering}, issn = {1438-0064}, doi = {10.1007/s10479-016-2152-1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-45107}, year = {2013}, 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, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. 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 paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method.}, language = {en} } @inproceedings{BorndoerferReutherSchlechte2014, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem}, volume = {42}, booktitle = {14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, doi = {10.4230/OASIcs.ATMOS.2014.79}, pages = {79 -- 91}, year = {2014}, 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{BorndoerferLoebelReutheretal.2012, 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}, year = {2012}, 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{BorndoerferHeismann2012, author = {Bornd{\"o}rfer, Ralf and Heismann, Olga}, title = {The Hypergraph Assignment Problem}, issn = {1438-0064}, doi = {10.1016/j.disopt.2014.11.002}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14822}, year = {2012}, abstract = {The hypergraph assignment problem (HAP) is the generalization of assignments from directed graphs to directed hypergraphs. It serves, in particular, as a universal tool to model several train composition rules in vehicle rotation planning for long distance passenger railways. We prove that even for problems with a small hyperarc size and hypergraphs with a special partitioned structure the HAP is NP-hard and APX-hard. Further, we present an extended integer linear programming formulation which implies, e. g., all clique inequalities.}, language = {en} } @misc{BorndoerferReutherSchlechteetal.2012, 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}, year = {2012}, 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{BorndoerferLangenhanLoebeletal.2012, 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}, year = {2012}, 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{BorndoerferGroetschelLoebel1995, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Alcuin's Transportation Problems and Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1932}, number = {SC-95-27}, year = {1995}, abstract = {The need to solve {\it transportation problems\/} was and still is one of the driving forces behind the development of the mathematical disciplines of graph theory, optimization, and operations research. Transportation problems seem to occur for the first time in the literature in the form of the four ''River Crossing Problems'' in the book Propositiones ad acuendos iuvenes. The {\it Propositiones\/} ---the oldest collection of mathematical problems written in Latin--- date back to the \$8\$th century A.D. and are attributed to Alcuin of York, one of the leading scholars of his time, a royal advisor to Charlemagne at his Frankish court. Alcuin's river crossing problems had no impact on the development of mathematics. However, they already display all the characteristics of today's large-scale real transportation problems. From our point of view, they could have been the starting point of combinatorics, optimization, and operations research. We show the potential of Alcuin's problems in this respect by investigating his problem~18 about a wolf, a goat and a bunch of cabbages with current mathematical methods. This way, we also provide the reader with a leisurely introduction into the modern theory of integer programming.}, language = {en} }