@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} } @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} } @misc{BorndoerferGroetschelJaeger2009, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Jaeger, Ulrich}, title = {Planning Problems in Public Transit}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11252}, number = {09-13}, year = {2009}, abstract = {Every day, millions of people are transported by buses, trains, and airplanes in Germany. Public transit (PT) is of major importance for the quality of life of individuals as well as the productivity of entire regions. Quality and efficiency of PT systems depend on the political framework (state-run, market oriented) and the suitability of the infrastructure (railway tracks, airport locations), the existing level of service (timetable, flight schedule), the use of adequate technologies (information, control, and booking systems), and the best possible deployment of equipment and resources (energy, vehicles, crews). The decision, planning, and optimization problems arising in this context are often gigantic and "scream" for mathematical support because of their complexity. This article sketches the state and the relevance of mathematics in planning and operating public transit, describes today's challenges, and suggests a number of innovative actions. The current contribution of mathematics to public transit is — depending on the transportation mode — of varying depth. Air traffic is already well supported by mathematics. Bus traffic made significant advances in recent years, while rail traffic still bears significant opportunities for improvements. In all areas of public transit, the existing potentials are far from being exhausted. For some PT problems, such as vehicle and crew scheduling in bus and air traffic, excellent mathematical tools are not only available, but used in many places. In other areas, such as rolling stock rostering in rail traffic, the performance of the existing mathematical algorithms is not yet sufficient. Some topics are essentially untouched from a mathematical point of view; e.g., there are (except for air traffic) no network design or fare planning models of practical relevance. PT infrastructure construction is essentially devoid of mathematics, even though enormous capital investments are made in this area. These problems lead to questions that can only be tackled by engineers, economists, politicians, and mathematicians in a joint effort. Among other things, the authors propose to investigate two specific topics, which can be addressed at short notice, are of fundamental importance not only for the area of traffic planning, should lead to a significant improvement in the collaboration of all involved parties, and, if successful, will be of real value for companies and customers: • discrete optimal control: real-time re-planning of traffic systems in case of disruptions, • model integration: service design in bus and rail traffic. Work on these topics in interdisciplinary research projects could be funded by the German ministry of research and education (BMBF), the German ministry of economics (BMWi), or the German science foundation (DFG).}, language = {en} } @misc{BorndoerferNeumannPfetsch2009, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Steiner Connectivity Problem}, issn = {1438-0064}, doi = {10.1007/s10107-012-0564-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11171}, number = {09-07}, year = {2009}, abstract = {The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role.}, language = {en} } @misc{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 (Extended Abstract)}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11076}, number = {08-53}, year = {2008}, abstract = {Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.}, language = {en} } @misc{TorresTorresBorndoerferetal.2008, author = {Torres, Luis Miguel and Torres, Ramiro and Bornd{\"o}rfer, Ralf and Pfetsch, Marc}, title = {On the Line Planning Problem in Tree Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11069}, number = {08-52}, year = {2008}, abstract = {We introduce an optimization model for the line planning problem in a public transportation system that aims at minimizing operational costs while ensuring a given level of quality of service in terms of available transport capacity. We discuss the computational complexity of the model for tree network topologies and line structures that arise in a real-world application at the Trolebus Integrated System in Quito. Computational results for this system are reported.}, language = {en} } @misc{Borndoerfer2009, author = {Bornd{\"o}rfer, Ralf}, title = {Discrete Optimization in Public Transportation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11207}, number = {08-56}, year = {2009}, abstract = {The mathematical treatment of planning problems in public transit has made significant advances in the last decade. Among others, the classical problems of vehicle and crew scheduling can nowadays be solved on a routine basis using combinatorial optimization methods. This is not yet the case for problems that pertain to the design of public transit networks, and for the problems of operations control that address the implementation of a schedule in the presence of disturbances. The article gives a sketch of the state and important developments in these areas, and it addresses important challenges. The vision is that mathematical tools of computer aided scheduling (CAS) will soon play a similar role in the design and operation of public transport systems as CAD systems in manufacturing.}, language = {en} } @misc{Neumann2009, author = {Neumann, Marika}, title = {Fare Planning for Public Transport}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11144}, number = {09-04}, year = {2009}, abstract = {In this paper we investigate the fare planning model for public transport, which consists in designing a system of fares maximizing the revenue. We discuss a discrete choice model in which passengers choose between different travel alternatives to express the demand as a function of fares. Furthermore, we give a computational example for the city of Potsdam and discuss some theoretical aspects.}, language = {en} } @misc{Kinder2008, type = {Master Thesis}, author = {Kinder, Mathias}, title = {Models for Periodic Timetabling}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10887}, school = {Zuse Institute Berlin (ZIB)}, year = {2008}, abstract = {We investigate the computation of periodic timetables for public transport by mixed integer programming. After introducing the problem, we describe two mathematical models for periodic timetabling, the PERIODIC EVENT SCHEDULING PROBLEM (PESP) and the QUADRATIC SEMI-ASSIGNMENT PROBLEM. Specifically, we give an overview of existing integer programming (IP) formulations for both models. An important contribution of our work are new IP formulations for the PESP based on time discretization. We provide an analytical comparison of these formulations and describe different techniques that allow a more efficient solution by mixed integer programming. In a preliminary computational study, on the basis of standard IP solvers, we compare different formulations for computing periodic timetables. Our results justify a further investigation of the time discretization approach. Typically the timetable is optimized for the current traffic situation. The main difficulty with this approach is that after introducing the new timetable the passengers' travel behavior may differ from that assumed for the computation. Motivated by this problem, we examine an iterative timetabling procedure that is a combination of timetable computation and passenger routing. We discuss the algorithmic issues of the passenger routing and study properties of the computed timetables. Finally, we confirm our theoretical results on the basis of an own implementation.}, language = {en} } @misc{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}, organization = {ZIB}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10869}, number = {08-35}, year = {2008}, abstract = {Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.}, language = {en} } @misc{BorndoerferNeumannPfetsch2005, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Optimal Fares for Public Transport}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8698}, number = {05-35}, year = {2005}, abstract = {The \emph{fare planning problem} for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a d iscrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands.}, language = {en} } @misc{Hoppmann2014, type = {Master Thesis}, author = {Hoppmann, Heide}, title = {A Configuration Model for the Line Planning Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51610}, pages = {108}, year = {2014}, abstract = {In this thesis we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations are combinatorial building blocks of primal solutions; they rule out the "capacity numerics" and make the problem purely combinatorial. The concept of configurations can also be adapted to other capacitated network design problems. The configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, multicover, and MIR inequalities. These theoretical findings can be confirmed in computations, however, the enormous number of configurations can blow up the formulation for large instances. We propose a mixed model that enriches the standard model by a judiciously chosen subset of configurations that provide a good compromise between model strength and size. Computational results for large-scale line planning problems are presented.}, language = {en} } @misc{GroetschelBorndoerfer2014, author = {Gr{\"o}tschel, Martin and Bornd{\"o}rfer, Ralf}, title = {Mathematik im Verkehr}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-50287}, year = {2014}, abstract = {Nach einem kurzen Abriss {\"u}ber die Bedeutung des Verkehrssektors als eine wichtige Schl{\"u}sseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik f{\"u}r Verkehr und Transport. Wir spekulieren dann {\"u}ber zuk{\"u}nftige Entwicklungen, insbesondere im Bereich des {\"o}ffentlichen Personenverkehrs, und begr{\"u}nden, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bew{\"a}ltigt werden k{\"o}nnen. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. {\"U}beralterung in Europa oder dynamische Trends zu Megast{\"a}dten in Entwicklungsl{\"a}ndern, sich {\"a}ndernde Lebens- und Produktionsverh{\"a}ltnisse, stark wachsender Bedarf nach Mobilit{\"a}t und enormes Anwachsen der Komplexit{\"a}t der Verkehrsplanung und -durchf{\"u}hrung, machen einen verst{\"a}rkten Zugriff auf mathematische Modellierung, Simulation und Optimierung notwendig. Diese Entwicklung stellt sowohl große Herausforderungen an die Mathematik, wo vielfach noch keine geeigneten Methoden vorhanden sind, als auch an die Praktiker im Bereich von Verkehr und Transport, die sich mit neuen Planungs- und Steuerungstechnologien befassen und diese effizient einsetzen m{\"u}ssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein.}, language = {de} } @misc{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Neue Planungsinstrumente nutzen: Das Verkehrsangebot verbessern und Kosten sparen}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55439}, 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} } @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} } @misc{Karbstein2014, author = {Karbstein, Marika}, title = {Integrated Line Planning and Passenger Routing: Connectivity and Transfers}, issn = {1438-0064}, doi = {10.1007/978-3-319-28697-6_37}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52986}, year = {2014}, 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} } @article{SahinAhmadiBorndoerferetal.2020, author = {Sahin, Guvenc and Ahmadi, Amin and Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Multi-period line planning with resource transfers}, volume = {119}, journal = {Transportation Research Part C: Emerging Technologies}, doi = {10.1016/j.trc.2020.102726}, pages = {102726}, year = {2020}, abstract = {Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.}, language = {en} }