@misc{SchenkerBorndoerferSkutella2016, author = {Schenker, Sebastian and Bornd{\"o}rfer, Ralf and Skutella, Martin}, title = {A novel partitioning of the set of non-dominated points}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61286}, year = {2016}, abstract = {We consider a novel partitioning of the set of non-dominated points for general multi-objective integer programs with \$k\$ objectives. The set of non-dominated points is partitioned into a set of non-dominated points whose efficient solutions are also efficient for some restricted subproblem with one less objective; the second partition comprises the non-dominated points whose efficient solutions are inefficient for any of the restricted subproblems. We show that the first partition has the nice property that it yields finite rectangular boxes in which the points of the second partition are located.}, language = {en} } @misc{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Metric Inequalities for Routings on Direct Connections with Application in Line Planning}, issn = {1438-0064}, doi = {10.1016/j.disopt.2015.07.004}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53507}, 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 feasibility condition for arc capacities in ordinary multi-commodity flows. The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.}, language = {en} } @misc{BorndoerferHoppmannKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Timetabling and Passenger Routing in Public Transport}, journal = {Appeard in: Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55305}, 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{BorndoerferKarbstein2014, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Metric Inequalities for Routings on Direct Connections}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-44219}, year = {2014}, 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 show that the concept of metric inequalities to characterize capacities that support a multi-commodity flow can be generalized to deal with direct connections.}, language = {en} } @misc{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}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-50270}, year = {2014}, abstract = {Wir stellen einen mathematischen Optimierungsansatz zur integrierten Dienst- und Dienstreihenfolgeplanung im {\"o}ffentlichen Nahverkehr vor, mit dem sich bei konstanten Personalkosten die Fahrerzufriedenheit deutlich steigern l{\"a}sst.}, language = {de} } @misc{HeismannBorndoerfer2014, author = {Heismann, Olga and Bornd{\"o}rfer, Ralf}, title = {A Generalization of Odd Set Inequalities for the Set Packing Problem}, issn = {1438-0064}, doi = {10.1007/978-3-319-07001-8_26}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51010}, year = {2014}, abstract = {The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.}, language = {en} } @misc{BorndoerferHoppmannKarbstein2013, 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}, year = {2013}, 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} } @misc{BorndoerferHeismann2012, 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}, year = {2012}, 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{BorndoerferKarbstein2012, 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}, year = {2012}, 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{BorndoerferKarbstein2012, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {A Direct Connection Approach to Integrated Line Planning and Passenger Routing}, 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}, year = {2012}, 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} }