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 - THES A1 - Hoppmann, Heide T1 - A Configuration Model for the Line Planning Problem N2 - 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. N2 - Das Linienplanungsproblem ist ein wichtiges Teilproblem der Angebotsplanung im öffentlichen Nahverkehr. Dabei werden Routen und Betriebsfrequenzen von Linien in einem gegebenen Infrastrukturnetzwerk gesucht, sodass ein gegebener Beförderungsbedarf gedeckt wird und die Kosten minimal sind. Praktische Ansätze zum Lösen dieser Probleme beruhen auf ganzzahliger Programmierung. Ein Schwachpunkt klassischer Modelle ist, dass schon kleine Änderungen der Eingabeparameter eine Vergrößerung oder Verkleinerung der Menge der zulässigen fraktionalen Lösungen bewirken können, auch wenn die Menge der ganzzahligen Lösungen unverändert bleibt. Wir betrachten in dieser Arbeit einen neuen kombinatorischen Ansatz, welcher die Möglichkeiten den Bedarf auf einer Verbindung im Netzwerk mit Frequenzen zu überdecken mit Hilfe von diskreten "Konfigurationen" beschreibt und dieses Problem eliminiert. Um die Vorteile dieses Konfigurationsmodells aufzuzeigen, vergleichen wir es mit einem klassischen Ansatz, den wir Standardmodell nennen. Wir zeigen, dass das Konfigurationsmodell mehrere facettendefinierende Ungleichungen des Standardmodells impliziert: Setcover-, symmetrische Band-, Multicover- und MIR-Ungleichungen. Diese theoretischen Ergebnisse können wir mit Rechenergebnissen bestätigen. Um die Anzahl dieser Variablen auch für große Instanzen zu beschränken, schlagen wir ein weiteres Modell vor, welches nur eine Teilmenge der Konfigurationsvariablen enthält. Dieses stellt sich als ein sehr guter Kompromiss zwischen der Größe und der Stärke des Modells heraus. Da das Linienplanungsproblem eine Spezialisierung des Netzwerkdesignproblems ist, können unsere Methoden auch auf andere Problemklassen übertragen werden. Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51610 ER - TY - GEN A1 - Grötschel, Martin A1 - Borndörfer, Ralf T1 - Mathematik im Verkehr N2 - Nach einem kurzen Abriss über die Bedeutung des Verkehrssektors als eine wichtige Schlüsseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik für Verkehr und Transport. Wir spekulieren dann über zukünftige Entwicklungen, insbesondere im Bereich des öffentlichen Personenverkehrs, und begründen, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bewältigt werden können. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. Überalterung in Europa oder dynamische Trends zu Megastädten in Entwicklungsländern, sich ändernde Lebens- und Produktionsverhältnisse, stark wachsender Bedarf nach Mobilität und enormes Anwachsen der Komplexität der Verkehrsplanung und -durchführung, machen einen verstä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üssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein. T3 - ZIB-Report - 14-03 KW - Optimierung KW - öffentlicher Verkehr Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-50287 SN - 1438-0064 ER - TY - GEN A1 - Karbstein, Marika T1 - Integrated Line Planning and Passenger Routing: Connectivity and Transfers 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. T3 - ZIB-Report - 14-42 KW - line planning, transfers,Steiner connectivity problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52986 SN - 1438-0064 ER -