@article{Karbstein2014, author = {Karbstein, Marika}, title = {Ohne Umsteigen ans Ziel}, volume = {52}, journal = {OR News}, pages = {12 -- 14}, year = {2014}, abstract = {Die Anforderungen an das Liniennetz eines Verkehrsunternehmens sind vielf{\"a}ltig: kurze Fahrzeiten, viele Direktverbindungen und geringe Kosten. Mathematische Optimierungsmethoden k{\"o}nnen die Planung von Liniennetzen unterst{\"u}tzen und beste Kompromisse bzgl. aller Anforderungen berechnen.}, language = {de} } @inproceedings{Karbstein2016, author = {Karbstein, Marika}, title = {Integrated Line Planning and Passenger Routing: Connectivity and Transfers}, booktitle = {Operations Research Proceedings 2014}, doi = {10.1007/978-3-319-28697-6_37}, pages = {263 -- 269}, year = {2016}, abstract = {The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbsteinetal.2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and L{\"o}bel, Fabian}, title = {The Modulo Network Simplex with Integrated Passenger Routing}, booktitle = {Operations Research Proceedings 2016}, year = {2016}, abstract = {Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.}, language = {en} } @misc{BorndoerferHoppmannKarbsteinetal.2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and L{\"o}bel, Fabian}, title = {The Modulo Network Simplex with Integrated Passenger Routing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60319}, year = {2016}, abstract = {Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.}, 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{BorndoerferFriedowKarbstein2012, author = {Bornd{\"o}rfer, Ralf and Friedow, Isabel and Karbstein, Marika}, title = {Optimierung des Linienplans 2010 in Potsdam}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14486}, number = {12-04}, year = {2012}, abstract = {Im Zuge der {\"U}bernahme von 6 Linien der Havelbus Verkehrsgesellschaft mbH durch die ViP Verkehr in Potsdam GmbH ergab sich 2009 die Notwendigkeit der Entwicklung eines neuen Linien- und Taktplans f{\"u}r das Jahr 2010. Das Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin (ZIB) entwickelt in einem Projekt des DFG-Forschungszentrums Matheon ein Verfahren zur mathematischen Linienoptimierung. Dieses Tool wurde bei der Optimierung des ViP Linienplans 2010 in einer projektbegleitenden Studie eingesetzt, um Alternativen bei verschiedenen Planungs- und Zielvorgaben auszuloten. In dem Artikel wird eine Auswertung der Ergebnisse mit dem Verkehrsanalysesystem Visum der PTV AG beschrieben. Die Auswertungen best{\"a}tigen, dass mit Hilfe von mathematischer Optimierung eine weitere Verk{\"u}rzung der Reisezeit um 1\%, eine als um 6\% verk{\"u}rzt empfundene Reisezeit, 10\% weniger Fahrzeit im Fahrzeug und eine gleichzeitige Kostenreduktion um 5\% m{\"o}glich sind.}, language = {de} } @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} } @article{BorndoerferHoppmannKarbstein2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Passenger routing for periodic timetable optimization}, journal = {Public Transport}, publisher = {Springer-Verlag Berlin Heidelberg}, doi = {10.1007/s12469-016-0132-0}, year = {2016}, abstract = {The task of periodic timetabling is to determine trip arrival and departure times in a public transport system such that travel and transfer times are minimized. This paper investigates periodic timetabling models with integrated passenger routing. We show that different routing models can have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems by integrating passenger routing.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Separation of Cycle Inequalities for the Periodic Timetabling Problem}, volume = {57}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, doi = {10.4230/LIPIcs.ESA.2016.21}, year = {2016}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.}, language = {en} } @article{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Metric inequalities for routings on direct connections with application to line planning}, volume = {18}, journal = {Discrete Optimization}, pages = {56 -- 73}, 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 well-known feasibility condition for arc capacities in ordinary multi-commodity flows. The condition can be expressed in terms of a class of metric inequalities for routings on direct connections. We illustrate the concept on the example of the line planning problem in public transport and present an application to large-scale real-world problems.}, language = {en} }