TY - CHAP A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc ED - Barnhart, Cynthia ED - Clausen, Uwe ED - Lauther, Ulrich ED - Möhring, Rolf T1 - Line Planning and Connectivity T2 - Models and Algorithms for Optimization in Logistics Y1 - 2009 IS - 09261 PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany CY - Dagstuhl, Germany ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc ED - Haasis, Hans-Dietrich ED - Kopfer, Herbert ED - Schönberger, Jörn T1 - Optimal Fares for Public Transport T2 - Operations Research Proceedings 2005 Y1 - 2006 UR - {http://opus.kobv.de/zib/volltexte/2005/869/} SP - 29 EP - 36 PB - Springer-Verlag ER - TY - CHAP A1 - Neumann, Marika ED - Waldmann, Karl-Heinz ED - Stocker, Ulrike T1 - Fare Planning for Public Transport T2 - Operations Research Proceedings 2006 Y1 - 2007 UR - {http://opus.kobv.de/zib/volltexte/2009/1160/} SP - 61 EP - 66 PB - Springer-Verlag ER - TY - JOUR A1 - Neumann, Marika T1 - Mathematische Preisplanung im ÖPNV JF - OR News Y1 - 2007 IS - 30 SP - 29 EP - 31 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 - JOUR A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Jäger, Ulrich T1 - Planning Problems in Public Transit JF - Production Factor Mathematics Y1 - 2010 SN - 978-3-642-11247-8 U6 - https://doi.org/10.1007/978-3-642-11248-5 SP - 95 EP - 122 PB - acatech and Springer CY - Berlin Heidelberg ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Neumann, Marika T1 - Linienoptimierung - reif für die Praxis? T2 - Heureka '11 : Optimierung in Verkehr und Transport N2 - Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege berü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ü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öglich, durch Veränderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen über minimale Kosten und Fahrzeiten zu machen. Y1 - 2011 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 -