@misc{PfetschBorndoerfer2005, author = {Pfetsch, Marc and Bornd{\"o}rfer, Ralf}, title = {Routing in Line Planning for Public Transportation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8706}, number = {05-36}, year = {2005}, abstract = {The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a network such that a giv en demand can be satisfied. There are two objectives. Passengers want to minimize travel times, the transport company wishes to minimize operating costs. We investigate three variants of a multi-commo dity flow model for line planning that differ with respect to passenger routings. The first model allows arbitrary routings, the second only unsplittable routings, and the third only shortest path rou tings with respect to the network. We compare these models theoretically and computationally on data for the city of Potsdam.}, language = {en} } @misc{BorndoerferGroetschelPfetsch2005, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {A Column-Generation Approach to Line Planning in Public Transport}, doi = {/10.1287/trsc.1060.0161}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8522}, number = {05-18}, year = {2005}, abstract = {The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.}, language = {en} } @misc{BorndoerferGroetschelPfetsch2005, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {Public Transport to the fORe!}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8562}, number = {05-22}, year = {2005}, abstract = {Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question ``What is a good public transport network?.}, language = {en} } @incollection{BorndoerferGroetschelJaeger2008, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Jaeger, Ulrich}, title = {Planungsprobleme im {\"o}ffentlichen Verkehr}, booktitle = {PRODUKTIONSFAKTOR MATHEMATIK - Wie Mathematik Technik und Wirtschaft bewegt}, editor = {Gr{\"o}tschel, Martin and Lucas, Klaus and Mehrmann, Volker}, publisher = {acatech - Deutsche Akademie der Technikwissenschaften und Springer}, pages = {127 -- 153}, year = {2008}, language = {en} } @inproceedings{BorndoerferGroetschelPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {Models for Line Planning in Public Transport}, volume = {600}, booktitle = {Computer-aided Systems in Public Transport (CASPT 2004)}, editor = {Hickman, Mark and Mirchandani, Pitu and Voß, Stefan}, publisher = {Springer-Verlag}, doi = {10.1007/978-3-540-73312-6_18}, pages = {363 -- 378}, year = {2008}, language = {en} } @article{BorndoerferGroetschelPfetsch2007, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {A Column-Generation Approach to Line Planning in Public Transport}, volume = {41}, journal = {Transportation Science (INFORMS)}, number = {1}, doi = {10.1287/trsc.1060.0161}, pages = {123 -- 132}, year = {2007}, language = {en} } @article{BorndoerferKarbsteinPfetsch2012, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Pfetsch, Marc}, title = {Models for Fare Planning in Public Transport}, volume = {160}, journal = {Discrete Applied Mathematics}, number = {18}, doi = {10.1016/j.dam.2012.02.027}, pages = {2591 -- 2605}, year = {2012}, language = {en} } @book{AbbinkBaermannBešinovicetal.2018, author = {Abbink, Erwin and B{\"a}rmann, Andreas and Bešinovic, Nikola and Bohlin, Markus and Cacchiani, Valentina and Caimi, Gabrio and de Fabris, Stefano and Dollevoet, Twan and Fischer, Frank and F{\"u}genschuh, Armin and Galli, Laura and Goverde, Rob M.P. and Hansmann, Ronny and Homfeld, Henning and Huisman, Dennis and Johann, Marc and Klug, Torsten and T{\"o}rnquist Krasemann, Johanna and Kroon, Leo and Lamorgese, Leonardo and Liers, Frauke and Mannino, Carlo and Medeossi, Giorgio and Pacciarelli, Dario and Reuther, Markus and Schlechte, Thomas and Schmidt, Marie and Sch{\"o}bel, Anita and Sch{\"u}lldorf, Hanno and Stieber, Anke and Stiller, Sebastian and Toth, Paolo and Zimmermann, Uwe}, title = {Handbook of Optimization in the Railway Industry}, volume = {268}, editor = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, publisher = {Springer Verlag}, isbn = {978-3-319-72152-1}, doi = {10.1007/978-3-319-72153-8}, year = {2018}, abstract = {This book promotes the use of mathematical optimization and operations research methods in rail transportation. The editors assembled thirteen contributions from leading scholars to present a unified voice, standardize terminology, and assess the state-of-the-art. There are three main clusters of articles, corresponding to the classical stages of the planning process: strategic, tactical, and operational. These three clusters are further subdivided into five parts which correspond to the main phases of the railway network planning process: network assessment, capacity planning, timetabling, resource planning, and operational planning. Individual chapters cover: Simulation Capacity Assessment Network Design Train Routing Robust Timetabling Event Scheduling Track Allocation Blocking Shunting Rolling Stock Crew Scheduling Dispatching Delay Propagation}, language = {en} } @misc{BorndoerferEgererKarbsteinetal.2018, author = {Bornd{\"o}rfer, Ralf and Egerer, Ascan and Karbstein, Marika and Messerschmidt, Ralf and Perez, Marc and Pfisterer, Steven and Strauß, Petra}, title = {Kombil{\"o}sung: Optimierung des Liniennetzes in Karlsruhe}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69677}, year = {2018}, abstract = {Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombil{\"o}sung.}, language = {de} } @misc{BorndoerferKarbstein2013, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {A Primal-Dual Approximation Algorithm for the Steiner Connectivity Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42430}, year = {2013}, abstract = {We extend the primal-dual approximation technique of Goemans and Williamson to the Steiner connectivity problem, a kind of Steiner tree problem in hypergraphs. This yields a (k+1)-approximation algorithm for the case that k is the minimum of the maximal number of nodes in a hyperedge minus 1 and the maximal number of terminal nodes in a hyperedge. These results require the proof of a degree property for terminal nodes in hypergraphs which generalizes the well-known graph property that the average degree of terminal nodes in Steiner trees is at most 2.}, language = {en} } @misc{BorndoerferGroetschelPfetsch2004, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {Models for Line Planning in Public Transport}, doi = {10.1007/978-3-540-73312-6_18}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7854}, number = {04-10}, year = {2004}, abstract = {The \emph{line planning problem} is one of the fundamental problems in strategic planning of public and rail transport. It consists of finding lines and corresponding frequencies in a public transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize its operating cost; the passengers request short travel times. We propose two new multi-commodity flow models for line planning. Their main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically.}, language = {en} } @inproceedings{BorndoerferNeumannPfetsch2009, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Line Planning and Connectivity}, booktitle = {Models and Algorithms for Optimization in Logistics}, number = {09261}, editor = {Barnhart, Cynthia and Clausen, Uwe and Lauther, Ulrich and M{\"o}hring, Rolf}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, address = {Dagstuhl, Germany}, year = {2009}, language = {en} } @incollection{BorndoerferNeumannPfetsch2006, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Optimal Fares for Public Transport}, booktitle = {Operations Research Proceedings 2005}, editor = {Haasis, Hans-Dietrich and Kopfer, Herbert and Sch{\"o}nberger, J{\"o}rn}, publisher = {Springer-Verlag}, pages = {29 -- 36}, year = {2006}, language = {en} } @incollection{Neumann2007, author = {Neumann, Marika}, title = {Fare Planning for Public Transport}, booktitle = {Operations Research Proceedings 2006}, editor = {Waldmann, Karl-Heinz and Stocker, Ulrike}, publisher = {Springer-Verlag}, pages = {61 -- 66}, year = {2007}, language = {en} } @article{Neumann2007, author = {Neumann, Marika}, title = {Mathematische Preisplanung im {\"O}PNV}, journal = {OR News}, number = {30}, pages = {29 -- 31}, year = {2007}, 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} } @phdthesis{Karbstein2013, author = {Karbstein, Marika}, title = {Line Planning and Connectivity}, isbn = {978-3-8439-1062-0}, year = {2013}, abstract = {This thesis introduces the Steiner connectivity problem. It is a generalization of the well known Steiner tree problem. Given a graph G = (V, E) and a subset T ⊆ V of the nodes, the Steiner tree problem consists in finding a cost minimal set of edges connecting all nodes in T . The Steiner connectivity problem chooses, instead of edges, from a given set of paths a subset to connect all nodes in T . We show in the first part of this thesis that main results about complexity, approximation, integer programming formulations, and polyhedra can be generalized from the Steiner tree problem to the Steiner connectivity problem. An example for a straightforward generalization are the Steiner partition inequalities, a fundamental class of facet defining inequalities for the Steiner tree problem. They can be defined for the Steiner connectivity problem in an analogous way as for the Steiner tree problem. An example for a generalization that needs more effort is the definition of a directed cut formulation and the proof that this dominates the canonical undirected cut formulation enriched by all Steiner partition inequalities. For the Steiner connectivity problem this directed cut formulation leads to extended formulations, a concept that is not necessary for the Steiner tree problem. There are also major differences between both problems. For instance, the case T = V for the Steiner connectivity problem is equivalent to a set covering problem and, hence, not a polynomial solvable case as in the Steiner tree problem. The Steiner connectivity problem is not only an interesting generalization of the Steiner tree problem but also the underlying connectivity problem in line planning with inte- grated passenger routing. The integrated line planning and passenger routing problem is an important planning problem in service design of public transport and the topic of the second part. Given is the infrastructure network of a public transport system where the edges correspond to streets and tracks and the nodes correspond to stations/stops of lines. The task is to find paths in the infrastructure network for lines and passengers such that the capacities of the lines suffice to transport all passengers. Existing models in the literature that integrate a passenger routing in line planning either treat transfers in a rudimentary way and, hence, neglect an important aspect for the choice of the pas- senger routes, or they treat transfers in a too comprehensive way and cannot be solved for large scale real world problems. We propose a new model that focuses on direct connections. The attractiveness of transfer free connections is increased by introducing a transfer penalty for each non-direct connection. In this way, a passenger routing is computed that favors direct connections. For the computation of this model we also implemented algorithms influenced by the results for the Steiner connectivity problem. We can compute with our model good solutions that minimize a weighted sum of line operating costs and passengers travel times. These solutions improve the solutions of an existing approach, that does not consider direct connections, by up to 17\%. In contrast to a comprehensive approach, that considers every transfer and for which we could not even solve the root LP within 10 hours for large instances, the solutions of the new model, computed in the same time, are close to optimality (<1\%) or even optimal for real world instances. In a project with the Verkehr in Potsdam GmbH to compute the line plan for 2010 we showed that our approach is applicable in practice and can be used to solve real world problems.}, language = {en} } @article{BorndoerferKarbsteinPfetsch2013, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Pfetsch, Marc}, title = {The Steiner connectivity problem}, volume = {142}, journal = {Mathematical Programming A}, number = {1}, doi = {10.1007/s10107-012-0564-5}, pages = {133 -- 167}, year = {2013}, language = {en} } @article{BorndoerferGroetschelJaeger2010, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and J{\"a}ger, Ulrich}, title = {Planning Problems in Public Transit}, journal = {Production Factor Mathematics}, publisher = {acatech and Springer}, address = {Berlin Heidelberg}, isbn = {978-3-642-11247-8}, doi = {10.1007/978-3-642-11248-5}, pages = {95 -- 122}, year = {2010}, language = {en} } @inproceedings{BorndoerferNeumann2011, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika}, title = {Linienoptimierung - reif f{\"u}r die Praxis?}, booktitle = {Heureka '11 : Optimierung in Verkehr und Transport}, year = {2011}, abstract = {Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege ber{\"u}cksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 f{\"u}r Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es m{\"o}glich, durch Ver{\"a}nderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen {\"u}ber minimale Kosten und Fahrzeiten zu machen.}, language = {de} } @inproceedings{BorndoerferHoppmannKarbstein2013, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {A Configuration Model for the Line Planning Problem}, volume = {33}, booktitle = {ATMOS 2013 - 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Frigioni, Daniele and Stiller, Sebastian}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/OASIcs.ATMOS.2013.68}, pages = {68 -- 79}, year = {2013}, language = {en} } @incollection{BorndoerferHoangKarbsteinetal.2013, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Karbstein, Marika and Koch, Thorsten and Martin, Alexander}, title = {How many Steiner terminals can you connect in 20 years?}, booktitle = {Facets of Combinatorial Optimization; Festschrift for Martin Gr{\"o}tschel}, editor = {J{\"u}nger, Michael and Reinelt, Gerhard}, publisher = {Springer}, doi = {10.1007/978-3-642-38189-8_10}, pages = {215 -- 244}, year = {2013}, language = {en} } @inproceedings{BorndoerferKarbstein2012, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {A Direct Connection Approach to Integrated Line Planning and Passenger Routing}, volume = {25}, booktitle = {ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, editor = {Delling, Daniel and Liberti, Leo}, doi = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2012.47}, pages = {47 -- 57}, year = {2012}, language = {en} } @article{BorndoerferFriedowKarbstein2012, author = {Bornd{\"o}rfer, Ralf and Friedow, Isabel and Karbstein, Marika}, title = {Optimierung des Linienplans 2010 in Potsdam}, volume = {30}, journal = {Der Nahverkehr}, number = {4}, pages = {34 -- 39}, year = {2012}, language = {de} } @article{BorndoerferGroetschelLoebel2010, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {The Quickest Path to the Goal}, journal = {Mathematics Everywhere}, editor = {Aigner, Martin and Behrends, Ehrhard}, publisher = {American Mathematical Society}, address = {Providence, Rhode Iland, USA}, pages = {27 -- 51}, year = {2010}, language = {en} } @article{BorndoerferGroetschelPfetsch2006, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {Public transport to the fORe}, journal = {OR/MS Today}, pages = {30 -- 40}, year = {2006}, 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{BorndoerferHoangKarbsteinetal.2013, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Karbstein, Marika and Koch, Thorsten and Martin, Alexander}, title = {How Many Steiner Terminals Can You Connect in 20 Years?}, issn = {1438-0064}, doi = {10.1007/978-3-642-38189-8_10}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42524}, year = {2013}, abstract = {Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.}, language = {en} } @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} } @misc{BorndoerferGroetschelJaeger2008, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Jaeger, Ulrich}, title = {Planung von {\"o}ffentlichem Personenverkehr}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10744}, number = {08-20}, year = {2008}, abstract = {Millionen von Menschen werden allein in Deutschland t{\"a}glich von Bussen, Bahnen und Flugzeugen transportiert. Der {\"o}ffentliche Personenverkehr ({\"O}V) ist von großer Bedeutung f{\"u}r die Lebensqualit{\"a}t einzelner aber auch f{\"u}r die Leistungsf{\"a}higkeit ganzer Regionen. Qualit{\"a}t und Effizienz von {\"O}V-Systemen h{\"a}ngen ab von politischen Rahmenbedingungen (staatlich geplant, wettbewerblich organisiert) und der Eignung der Infrastruktur (Schienensysteme, Flughafenstandorte), vom vorhandenen Verkehrsangebot (Fahr- und Flugplan), von der Verwendung angemessener Technologien (Informations-, Kontroll- und Buchungssysteme) und dem bestm{\"o}glichen Einsatz der Betriebsmittel (Energie, Fahrzeuge und Personal). Die hierbei auftretenden Entscheidungs-, Planungs- und Optimierungsprobleme sind z.T. gigantisch und "schreien" aufgrund ihrer hohen Komplexit{\"a}t nach Unterst{\"u}tzung durch Mathematik. Dieser Artikel skizziert den Stand und die Bedeutung des Einsatzes von Mathematik bei der Planung und Durchf{\"u}hrung von {\"o}ffentlichem Personenverkehr, beschreibt die bestehenden Herausforderungen und regt zukunftsweisende Maßnahmen an.}, language = {de} } @misc{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Line Connectivity Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10820}, number = {08-31}, year = {2008}, abstract = {This paper introduces the "line connectivity problem", a generalization of the Steiner tree problem and a special case of the line planning problem. We study its complexity and give an IP formulation in terms of an exponential number of constraints associated with "line cut constraints". These inequalities can be separated in polynomial time. We also generalize the Steiner partition inequalities.}, language = {en} } @misc{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Models for Fare Planning in Public Transport}, issn = {1438-0064}, doi = {10.1016/j.dam.2012.02.027}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10708}, number = {08-16}, year = {2008}, abstract = {The optimization of fare systems in public transit allows to pursue objectives such as the maximization of demand, revenue, profit, or social welfare. We propose a non-linear optimization approach to fare planning that is based on a detailed discrete choice model of user behavior. The approach allows to analyze different fare structures, optimization objectives, and operational scenarios involving, e.g., subsidies. We use the resulting models to compute optimized fare systems for the city of Potsdam, Germany.}, language = {en} } @misc{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Angebotsplanung im {\"o}ffentlichen Nahverkehr}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10555}, number = {08-04}, year = {2008}, abstract = {Die Angebotsplanung im {\"o}ffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen f{\"u}r die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenh{\"a}nge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abh{\"a}ngigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.}, language = {de} } @misc{BorndoerferLiebchen2007, author = {Bornd{\"o}rfer, Ralf and Liebchen, Christian}, title = {When Periodic Timetables are Suboptimal}, organization = {DFG Reseach Center Matheon "Mathematics for Key Technologies"}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9151}, number = {07-29}, year = {2007}, abstract = {The timetable is the essence of the service offered by any provider of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the timetable has a major impact on both operating costs and on passenger comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two strategies with respect to vehicle operation costs. It turns out that for short time horizons, periodic timetabling can be suboptimal; for sufficiently long time horizons, however, periodic timetabling can always be done in an optimal way'.}, language = {en} } @misc{BorndoerferNeumannPfetsch2005, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Fare Planning for Public Transport}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8541}, number = {05-20}, year = {2005}, abstract = {In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments.}, 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} } @phdthesis{Borndoerfer2010, author = {Bornd{\"o}rfer, Ralf}, title = {Mathematical Optimization and Public Transportation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13613}, school = {Zuse Institute Berlin (ZIB)}, year = {2010}, abstract = {This cumulative thesis collects the following six papers for obtaining the habilitation at the Technische Universit{\"a}t Berlin, Fakult{\"a}t II - Mathematik und Naturwissenschaften: (1) Set packing relaxations of some integer programs. (2) Combinatorial packing problems. (3) Decomposing matrices into blocks. (4) A bundle method for integrated multi-depot vehicle and duty scheduling in public transit. (5) Models for railway track allocation. (6) A column-generation approach to line planning in public transport. Some changes were made to the papers compared to the published versions. These pertain to layout unifications, i.e., common numbering, figure, table, and chapter head layout. There were no changes with respect to notation or symbols, but some typos have been eliminated, references updated, and some links and an index was added. The mathematical content is identical. The papers are about the optimization of public transportation systems, i.e., bus networks, railways, and airlines, and its mathematical foundations, i.e., the theory of packing problems. The papers discuss mathematical models, theoretical analyses, algorithmic approaches, and computational aspects of and to problems in this area. Papers 1, 2, and 3 are theoretical. They aim at establishing a theory of packing problems as a general framework that can be used to study traffic optimization problems. Indeed, traffic optimization problems can often be modelled as path packing, partitioning, or covering problems, which lead directly to set packing, partitioning, and covering models. Such models are used in papers 4, 5, and 6 to study a variety of problems concerning the planning of line systems, buses, trains, and crews. The common aim is always to exploit as many degrees of freedom as possible, both at the level of the individual problems by using large-scale integer programming techniques, as well as on a higher level by integrating hitherto separate steps in the planning process.}, 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} } @inproceedings{BorndoerferNeumannPfetsch2009, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Line Connectivity Problem}, booktitle = {Operations Research Proceedings 2008}, editor = {Fleischmann, Bernhard and Borgwardt, Karl and Klein, Robert and Tuma, Axel}, publisher = {Springer-Verlag}, pages = {557 -- 562}, year = {2009}, language = {en} } @book{Borndoerfer2010, author = {Bornd{\"o}rfer, Ralf}, title = {Mathematical Optimization and Public Transportation}, publisher = {TU Berlin}, year = {2010}, language = {en} } @inproceedings{TorresTorresBorndoerferetal.2008, author = {Torres, Luis Miguel and Torres, Ramiro and Bornd{\"o}rfer, Ralf and Pfetsch, Marc}, title = {Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System}, booktitle = {ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Fischetti, Matteo and Widmayer, Peter}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, address = {Dagstuhl, Germany}, year = {2008}, language = {en} } @inproceedings{PfetschBorndoerfer2006, author = {Pfetsch, Marc and Bornd{\"o}rfer, Ralf}, title = {Routing in Line Planning for Public Transportation}, booktitle = {Operations Research Proceedings 2005}, editor = {Haasis, Hans-Dietrich}, publisher = {Springer-Verlag}, pages = {405 -- 410}, year = {2006}, language = {en} } @inproceedings{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Angebotsplanung im {\"o}ffentlichen Nahverkehr}, booktitle = {HEUREKA'08}, publisher = {FGSV Verlag}, year = {2008}, language = {en} } @inproceedings{BorndoerferLiebchen2008, author = {Bornd{\"o}rfer, Ralf and Liebchen, Christian}, title = {When Periodic Timetables are Suboptimal}, booktitle = {Operations Research Proceedings 2007}, editor = {Kalcsics, J{\"o}rg and Nickel, Stefan}, publisher = {SPRINGER}, pages = {449 -- 454}, year = {2008}, 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} } @misc{BorndoerferGroetschelLoebel2010, 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}, year = {2010}, 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{BorndoerferNeumann2010, 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}, year = {2010}, 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{BorndoerferNeumann2010, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika}, title = {Linienoptimierung - reif f{\"u}r die Praxis?}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11832}, number = {10-20}, year = {2010}, abstract = {Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege ber{\"u}cksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 f{\"u}r Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es m{\"o}glich, durch Ver{\"a}nderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen {\"u}ber minimale Kosten und Fahrzeiten zu machen.}, language = {de} }