In der Linienplanung sollen Linien (Linienführung und Frequenzen) in einem gegebenen Netz geplant werden, so dass die Nachfrage (gegeben durch eine Quelle-Ziel-Matrix) befördert werden kann. Die Zielfunktion versucht einen Ausgleich zwischen Qualität und Kosten zu finden. Wir haben ein Wege-basiertes Mehrgüterflussmodell entwickelt, das Passagierflüsse und Linienwege miteinander koppelt (Borndörfer, Grötschel und Pfetsch 2004, Borndörfer, Grötschel und Pfetsch 2005). Das Modell hat Eigenschaften, die vorher noch nicht in diesem Zusammenhang untersucht wurden, nämlich die dynamische Generierung von Linien und eine freie Wegesuche der Passagiere innerhalb des berechneten Liniensystems. Die Literatur betrachtet hauptsächlich Linienplanung für den Bahnverkehr. In den meisten dieser Ansätze werden Passagierwege a priori durch ein Verfahren namens System-Split festgelegt und Linien werden aus einer vorherberechneten Menge ausgewählt.

Unsere mathematischen Ergebnisse analysieren die Komplexität des Modells: Die Lösung der LP-Relaxierung ist NP-schwer, die Erzeugung der Passagierwege kann in polynomialer Zeit durchgeführt werden, aber die Erzeugung der Linienwege ist ein längste Wege-Problem. Wir haben jedoch bewiesen, dass der Fall von logarithmischen Linienlängen in polynomialer Zeit durch einen derandomisierten Färbungsansatz behandelt werden kann.

Auf der algorithmischen Seite haben wir einen Spaltengenerierungsansatz entwickelt, der auf exakter Enumeration von Linienwegen basiert. Unsere Implementierung kann die Optimallösung der LP-Relaxierung von Linienplanungsproblemen für das gesamte ÖPNV-Netz von Potsdam (mit 410 Knoten und 891 Strecken) in weniger als einer Stunde berechnen. Diese Instanzen sind deutlich größer und komplexer als Netze die in der Literatur behandelt wurden.

Zur Zeit arbeiten wir an Methoden, um ganzzahlige Lösungen für das Linienplanungsproblem von guter Qualität zu erzeugen. Wir stehen in regelmäßigem Austausch mit unseren Kooperationspartnern ViP Potsdam GmbH und IVU Traffic Technologies AG, um die praktische Anwendbarkeit unserer Linienpläne auszuloten.

Alte Linien in Potsdam	Berechnete Linien
Die Bilder wurden mit JavaView (Projekt F4) erzeugt.

Beispiel: Das linke Bild oben zeigt das Liniennetz von Potsdam des Jahres 1998. Die Dicke der Kanten ist proportional zur Frequenz der Linien. Die folgende Farbkodierung wurde benutzt: Blau = Tram, Violett = Stadtbus, Braun = Regionalbus. Die Verkehrssysteme Regionalzug, S-Bahn und Fähre sind nicht dargestellt, weil diese nicht von unseren Kooperationspartnern betrieben werden. Das rechte Bild zeigt das Resultat unserer Optimierung.

Die Aufgabe der Preisplanung ist der Entwurf eines Preissystems für verschiedene Fahrkartentypen, so dass die Einnahmen eines Nahverkehrsunternehmens maximiert werden. Die Fahrkarten können zum Beispiel einen Basispreis und einen Kilometerpreis enthalten (ähnlich der deutschen Bahn-Card). Die Preise beeinflussen die Passagiernachfrage zwischen verschiedenen Punkten im Netz, welche wiederum die Einnahmen bestimmt. Nach unserer Kenntnis ist bisher kein Optimierungsansatz für eine solche Preisplanung in der Literatur untersucht worden. Wir haben ein neues nichtlineares Optimierungsmodell für dieses Problem entworfen, dass auf einer Nachfragfunktion basiert, die aus einem Logit-artigen diskreten Entscheidungsmodell resultiert (Borndörfer, Neumann und Pfetsch 2005). Durch Anwendung von Standard-Software haben wir optimale Preise für das niederländische Intercitynetz berechnet, wobei mehrere Fahrkartentypen für den öffentlichen Verkehr und die Alternative motorisierter Individualverkehr möglich sind.

Beispiel: Es gibt drei Alternativen: Standardfahrkarte, Bahn-Card und Auto. Für eine Standardfahrkarte muss ein Kilometerpreis bezahlt werden (X-Achse/Euro). Um die Bahn-Card benutzen zu können, muss ein Basispreis (Y-Achse/Euro) und ein um 50% reduzierter Kilometerpreis bezahlt werden. Der Preis zur Benutzung des Autos beinhaltet einen Grundpreis von 100 Euro und einen Kilometerpreis von 0,1 Euro/km. Die unten stehenden Bilder zeigen die aus unserem Modell resultierende Einnahmefunktion.

3D-Plot der Einnahmefunktion	Kontourplot der Einnahmefunktion

• Poster (05/2005) [ps.gz]

• Ralf Borndörfer, Martin Grötschel, Marc E. Pfetsch. Models for Line Planning in Public Transport. Forschungsbericht 04–10, ZIB, 2004. Presented at CASPT 2005.
• Ralf Borndörfer, Martin Grötschel, Marc E. Pfetsch. A Path-Based Model for Line Planning in Public Transport. Forschungsbericht 05–18, ZIB, 2005. To appear in Transportation Science.
• Ralf Borndörfer, Marika Neumann, Marc E. Pfetsch. Fare Planning in Public Transport. Forschungsbericht 05–20, ZIB, 2005.
• Ralf Borndörfer, Martin Grötschel, Marc E. Pfetsch. Public transport to the fORe. OR/MS Today, 2(33), 2006.
• Ralf Borndörfer, Marika Neumann, Marc E. Pfetsch. Optimal Fares for Public Transport. Forschungsbericht 05–35, ZIB, 2005. Ralf Borndörfer, Marika Neumann, Marc E. Pfetsch. Optimal Fares for Public Transport. Forschungsbericht 05–35, ZIB, 2005. To appear in Operations Research Proceedings 2005.
• Marc E. Pfetsch, Ralf Borndörfer. Routing in Line Planning for Public Transport. Forschungsbericht 05–36, ZIB, 2005. To appear in Operations Research Proceedings 2005.
• Marika Neumann. Mathematische Preisplanung im ÖPNV. Diplomarbeit, TU Berlin, 2005.
• William Wieprecht. Mathematische Modellierung von Nahverkehrssystemen. Diplomarbeit, TU Berlin, 2003.
• Rüdiger Stephan. Polytopes Associated with Length-Restricted Directed Circuits. Diplomarbeit, TU Berlin, 2005.