TY - JOUR A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Pfetsch, Marc T1 - Models for Fare Planning in Public Transport JF - Discrete Applied Mathematics Y1 - 2012 U6 - https://doi.org/10.1016/j.dam.2012.02.027 VL - 160 IS - 18 SP - 2591 EP - 2605 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Lindner, Niels T1 - Separation of cycle inequalities in periodic timetabling JF - Discrete Optimization N2 - Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem. Y1 - 2020 U6 - https://doi.org/10.1016/j.disopt.2019.100552 IS - 35 SP - 100552 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Liebchen, Christian A1 - Lindner, Niels T1 - A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable N2 - We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [9], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same. T3 - ZIB-Report - 18-38 KW - Vehicle scheduling KW - Periodic timetabling KW - Bipartite matching Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69688 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Egerer, Ascan A1 - Karbstein, Marika A1 - Messerschmidt, Ralf A1 - Perez, Marc A1 - Pfisterer, Steven A1 - Strauß, Petra T1 - Kombilösung: Optimierung des Liniennetzes in Karlsruhe N2 - Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung. T3 - ZIB-Report - 18-45 KW - ÖPNV KW - Linienplanung Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69677 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - A Primal-Dual Approximation Algorithm for the Steiner Connectivity Problem N2 - 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. T3 - ZIB-Report - 13-54 KW - Primal-Dual Approximation KW - Steiner Connectivity Problem KW - Degree Property KW - Hypergraph Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42430 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Mehrgahrdt, Julika A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - The Cycle Embedding Problem T2 - Operations Research Proceedings 2014 N2 - Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-28697-6_65 SP - 465 EP - 472 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Liebchen, Christian A1 - Lindner, Niels T1 - A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable T2 - 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018) N2 - We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [9], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same. Y1 - 2018 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2018.16 VL - 65 SP - 16:1 EP - 16:15 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Euler, Ricardo A1 - Karbstein, Marika A1 - Mett, Fabian T1 - Ein mathematisches Modell zur Beschreibung von Preissystemen im öV N2 - Dieses Dokument fasst den Stand der mathematischen Modellierung von Preissystemen des öV mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Tarifgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Wir beschreiben zunächst das Konzept. Die konkrete Realisierung wird im Folgenden beispielhaft an den Tarifsystemen der Verkehrsverbünde Warnow, MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erläutert. Anschließend folgen Überlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbundübergriffs. T3 - ZIB-Report - 18-47 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70564 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Lindner, Niels T1 - Separation of Cycle Inequalities in Periodic Timetabling N2 - Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algo- rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem. T3 - ZIB-Report - 18-16 KW - Periodic timetabling KW - Cycle inequality KW - Change-cycle inequality Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69746 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - Metric Inequalities for Routings on Direct Connections N2 - 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. T3 - ZIB-Report - 14-04 KW - metric inequalities KW - direct connection KW - multi-commodity flow problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44219 SN - 1438-0064 ER - TY - THES A1 - Karbstein, Marika T1 - Line Planning and Connectivity N2 - 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. Y1 - 2013 UR - www.zib.de/karbstein/scplpp.pdf SN - 978-3-8439-1062-0 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Pfetsch, Marc T1 - The Steiner connectivity problem JF - Mathematical Programming A Y1 - 2013 U6 - https://doi.org/10.1007/s10107-012-0564-5 VL - 142 IS - 1 SP - 133 EP - 167 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika ED - Frigioni, Daniele ED - Stiller, Sebastian T1 - A Configuration Model for the Line Planning Problem T2 - ATMOS 2013 - 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems Y1 - 2013 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2013.68 VL - 33 SP - 68 EP - 79 PB - Schloss Dagstuhl--Leibniz-Zentrum für Informatik ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Karbstein, Marika A1 - Koch, Thorsten A1 - Martin, Alexander ED - Jünger, Michael ED - Reinelt, Gerhard T1 - How many Steiner terminals can you connect in 20 years? T2 - Facets of Combinatorial Optimization; Festschrift for Martin Grötschel Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38189-8_10 SP - 215 EP - 244 PB - Springer ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Karbstein, Marika ED - Delling, Daniel ED - Liberti, Leo T1 - A Direct Connection Approach to Integrated Line Planning and Passenger Routing T2 - ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems Y1 - 2012 U6 - https://doi.org/http://dx.doi.org/10.4230/OASIcs.ATMOS.2012.47 VL - 25 SP - 47 EP - 57 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Friedow, Isabel A1 - Karbstein, Marika T1 - Optimierung des Linienplans 2010 in Potsdam JF - Der Nahverkehr Y1 - 2012 VL - 30 IS - 4 SP - 34 EP - 39 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - A Configuration Model for the Line Planning Problem N2 - 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. T3 - ZIB-Report - 13-40 KW - combinatorial optimization KW - polyhedral combinatorics KW - line planning Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-41903 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Karbstein, Marika A1 - Koch, Thorsten A1 - Martin, Alexander T1 - How Many Steiner Terminals Can You Connect in 20 Years? N2 - 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. T3 - ZIB-Report - 13-57 KW - Steiner tree KW - Steiner connectivity KW - Steiner tree packing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42524 SN - 1438-0064 ER - TY - JOUR A1 - Karbstein, Marika T1 - Ohne Umsteigen ans Ziel JF - OR News N2 - Die Anforderungen an das Liniennetz eines Verkehrsunternehmens sind vielfältig: kurze Fahrzeiten, viele Direktverbindungen und geringe Kosten. Mathematische Optimierungsmethoden können die Planung von Liniennetzen unterstützen und beste Kompromisse bzgl. aller Anforderungen berechnen. Y1 - 2014 VL - 52 SP - 12 EP - 14 ER - TY - CHAP A1 - Karbstein, Marika T1 - Integrated Line Planning and Passenger Routing: Connectivity and Transfers T2 - Operations Research Proceedings 2014 N2 - 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. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-28697-6_37 SP - 263 EP - 269 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Löbel, Fabian T1 - The Modulo Network Simplex with Integrated Passenger Routing T2 - Operations Research Proceedings 2016 N2 - 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. Y1 - 2016 ER -