Obgleich Optimierungsverfahren für den Entwurf des ÖV-Angebots seit mehr als 40 Jahren entwickelt werden, haben bisher nur Verfahren der Umlauf- und Dienstplanung den Weg in die Praxis der Angebotsplanung gefunden. Dagegen sind bei der Erstellung von Linien und Fahrplänen rechnergestützte Entwurfsverfahren weiterhin die Standardmethode in der ÖV-Angebotsplanung. Um die Anforderungen der Planungspraxis besser erfüllen zu können, werden in diesem Beitrag planerische und algorithmische Lösungen für eine Testinstanz erzeugt und miteinander verglichen. Der Vergleich soll dann in nachfolgenden Schritten genutzt werden, um die Optimierungsverfahren weiter zu verbessern.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einleitung

Das Verkehrsangebot im öffentlichen Verkehr (ÖV) hat die primäre Aufgabe, Fahrgäste zu befördern. Der ÖV soll darüber hinaus eine Alternative zum Pkw anbieten, da er verglichen mit dem Pkw auf einem Fahrweg gleicher Breite deutlich mehr Menschen als der Pkw befördern kann und ab einem durchschnittlichen Auslastungsgrad der Sitzplätze von rund 40% einen niedrigeren spezifischen Energieverbrauch pro Personenkilometer aufweist. Diese positiven Eigenschaften des ÖV dienen als eine Rechtfertigung öffentlicher Zuschüsse für den ÖV. Da bei einem Ausbau des ÖV die Kosten in der Regel stärker steigen als die Erlöse, müssen bei einer integrierten Planung im öffentlichen Verkehr die Wirkungen auf die Fahrgäste und die Wirkungen auf die Betreiber gleichermaßen berücksichtigt werden. Daraus ergibt sich die übergeordnete Fragestellung, die den vorliegenden Beitrag motiviert: Wie entwirft man ein möglichst gutes Angebot im öffentlichen Verkehr?

Zur Lösung dieser Fragestellung verfolgen Vertreter der Verkehrsplanung und der angewandten Mathematik bzw. des Operations Research unterschiedliche Ansätze:

- Verkehrsplaner nutzen Verfahren, die als Intuitivverfahren bezeichnet werden können und auf der planerischen Erfahrung aufbauen. Diese Vorgehensweise für den Entwurf des Verkehrsangebots im öffentlichen Verkehr ist u.a. in [3] und [6] beschrieben. In der Planungspraxis kommen häufig rechnergestützte Intuitivverfahren ([4], [16]) zum Einsatz, bei denen der Planer oder die Planerin das Angebot entwirft und der Rechner die Wirkungen einer Lösung auf die Fahrgäste und Betreiber mit einem Wirkungsmodell berechnet. Die Wirkungen auf die Fahrgäste werden mit Verkehrsnachfragemodellen relativ detailliert berechnet. Betriebliche Wirkungen werden in einfachen Modellen aus den Einsatzkilo- metern und Einsatzstunden abgeleitet, in komplexeren Modellen werden Fahrzeugum- läufe berücksichtigt. Um möglichst gute Lösungen zu finden, wurden für einzelne Frage- stellungen (Haltestellenstandorte, Haltestellenabstände, Takt/Fahrzeugfolgezeit, Abstand paralleler Linien, Hierarchisierung der Linien, Liniennetze) Regeln entwickelt, in denen die planerische Erfahrung systematisiert wird (z.B. [4] und [3]).

- Mathematiker formulieren die Entwurfsaufgabe als Optimierungsproblem, bei der eine Zielfunktion optimiert wird. Auf diese Weise wird der Lösungsraum systematisch abgesucht, so dass die Lösung nicht von der Erfahrung eines Planers, sondern von der Formulierung des Problems und der verwendeten Zielfunktion abhängig ist. Um viele Lösungen testen zu können, werden die Wirkungen auf Fahrgäste und Betreiber mit einfachen Wirkungsmodellen berechnet. Eine Übersicht über Modelle zur Liniennetzplanung findet sich in [11], [1], [13] und [2].

Obgleich Optimierungsverfahren für den Entwurf des ÖV-Angebots seit mehr als 40 Jahren entwickelt werden, haben bisher nur Verfahren der Umlauf- und Dienstplanung den Weg in die Praxis der Angebotsplanung gefunden. Beim Entwurf von Linien und Fahrplänen sind rechnergestützte Entwurfsverfahren weiterhin die Standardmethode bei der ÖV-Angebotsplanung. In der DFG-Forschergruppe “Integrierte Planung im öffentlichen Verkehr” haben sich Vertreter der Mathematik, der Informatik und des Verkehrswesens mit dem Ziel zusammengefunden, Methoden der mathematischen Optimierung für die Zwecke der ÖV-Angebotsplanung so zu erweitern, dass die Anforderungen der Planungspraxis besser erfüllt werden können. Dieser Beitrag berichtet über ein Teilprojekt, das auf die Schritte Liniennetzplanung, Fahrplanung und Umlaufplanung fokussiert ist. Ein wesentlicher Forschungsansatz in diesem Teilprojekt besteht darin, dass für eine gegebene Aufgabenstellung, d.h. für eine gegebene Siedlungsstruktur und ein gegebenes Verkehrswegenetz, planerische und algorithmische Lösungen erzeugt und miteinander verglichen werden. Der Vergleich soll dann in nachfolgenden Schritten genutzt wer- den, um die Optimierungsverfahren zu verbessern.

Tabelle 1: Kenngrößen des Verkehrsangebots

2 Kenngrößen, Parameter und Variablen eines Verkehrsangebots

Um die Qualität einer Lösung nachweisen zu können, müssen die Wirkungen eines ÖV-Angebotes ermittelt und bewertet werden. Wichtige Kriterien, nach denen ein ÖV-Angebot von den Fahrgästen und den Betreibern beurteilt wird, sind in Tabelle 1 zusammengestellt. Die benutzerbezogenen Kenngrößen beinhalten Aussagen über die Qualität des Verkehrsangebotes, die Kenngrößen der Betreiber umfassen den Aufwand zur Erbringung des Verkehrsangebotes und die Kenngrößen der Allgemeinheit beschreiben sekundäre Wirkungen eines Verkehrsangebots. Die Kenngrößen eines Verkehrsangebots ergeben sich aus den Variablen und Parametern eines Verkehrsangebots. Parameter umfassen alle externen Eingangsgrößen für die Planung, die im Planungsprozess nicht verändert werden können. Bei einer ÖV-Angebotsplanung sind u.a. die folgenden Parameter vorgegeben:

- Bevölkerungs- und Siedlungsstruktur

- Verkehrsangebot der anderen Verkehrsmodi

- Präferenzen der Verkehrsteilnehmer (Mobilitätsverhaltensparameter)

- Verkehrswegenetz, das von ÖV-Fahrzeugen genutzt werden kann

- Eigenschaften der Fahrzeuge (Kapazität, Verbrauch)

- Regeln für den Betrieb (z.B. Fahrerpausen, Mindestwendezeiten)

- Kostensätze für den Betrieb (Fahrzeuge, Personal, Betriebsmittel)

Die Variablen eines Verkehrsangebots umfassen die Größen, die im Rahmen der Planung festgelegt werden. Wesentliche Variablen eines ÖV-Angebots sind:

- Anzahl und Lage der Haltestellen

- Anzahl der Linien und Verlauf der Linienwege

- Fahrzeiten zwischen Haltestellen und Haltezeiten

- Abfahrtszeiten an den Haltestellen

- Fahrzeugfolgezeit bzw. Takt

- Fahrzeugtyp bzw. Fahrzeuggröße

Einige der Variablen sind dabei nur innerhalb gewisser Grenzen veränderbar. Das gilt insbesondere für die Fahr- und Haltezeit, bei der natürlich tageszeitabgängige Mindestzeiten eingehalten werden müssen und es damit nur um die Festlegung von Pufferzeiten geht.

Die Abgrenzung zwischen Parametern und Variablen kann von der Aufgabenstellung abhängen. So können Fahrpreise entweder aus einem Tarifmodell als Parameter vorgegeben oder innerhalb der Planung festgelegt werden. Außerdem kann die Verkehrsnachfrage eine unveränderliche Eingangsgröße für die Angebotsplanung sein oder von der Qualität des Verkehrsangebots und damit von der Lösung der Planungsaufgabe abhängen.

3 Beschreibung Testinstanz

In diesem Beitrag sollen planerische und algorithmische Lösungen beispielhaft für eine Testinstanz verglichen werden. Dabei wird von folgenden Annahmen ausgegangen:

Verkehrswegenetz: Gegegeben sei das in Abbildung 1a dargestellte Rasternetz mit 25 vorgegebenen Haltestellen. Die Strecken des Netzes haben alle eine einheitliche Länge von 2 km. Für die Fahrzeit der Busse zwischen den Haltestellen wird eine mittlere Fahrgeschwindigkeit inkl. Haltestellenaufenthaltszeit von 20 km/h angenommen, so dass die Fahrzeit zwischen zwei Haltestellen 6 Minuten beträgt.

Verkehrsnachfrage: Die Verkehrsnachfrage wurde mit einem Verkehrsnachfragemodell ermittelt, dass zwei Modi (Pkw und ÖV) und vier Aktivitätenpaare (Wohnen-Arbeit, Arbeit-Wohnen, Wohnen-Sonstiges, Sonstiges-Wohnen) unterscheidet. Es werden die Wege von 30.000 Erwerbstätigen modelliert, die in 25 Verkehrszellen wohnen. Jede Verkehrszelle ist genau einer Haltestelle zugeordnet, so dass die Verkehrsteilnehmer keine Haltestellenwahlentscheidungen treffen können. Die Nachfrage wird für jede Stunde des Tages berechnet, Grundlage der Linienplanung ist die ÖV-Verkehrsnachfrage in der morgendlichen Hauptverkehrszeit. Sie umfasst insgesamt 2.531 Fahrten. Bild 1b zeigt den Quell- und Zielverkehr für jede Verkehrszelle und die Streckenbelastungen, die sich bei einer Bestwegumlegung ergeben. Für Relationen mit mehr als einer Route haben alle Routen die gleiche Fahrzeit. Der jeweils gewählte kürzeste Weg hängt in diesen Fällen von der Nummerierung der Strecken ab.

Bild 1: Streckennetz und Verkehrsnachfrage der Testinstanz

Fahrzeuge: Es steht ein Fahrzeugtyp mit einer Gesamtkapazität von 70 Plätzen zur Verfügung. Die Kosten für ein Fahrzeug inkl. Fahrer betragen 50e/h und 1,50e/km. Ein- und Aussetzfahrten zu Depots werden nicht berücksichtigt.

Angebotsqualität: Um die Angebotsqualität zu quantifizieren, wird die Fahrzeit im Fahrzeug, die Umsteigewartezeit und die Umsteigehäufigkeit herangezogen. Ein Umstieg wird zusätzlich mit einem Zeitzuschlag von 5 Minuten bewertet. Zu- und Abgangszeit werden nicht herangezogen, da sie bei gegebenen Haltestellen und gegebener Zuordnung zu den Haltestellen nicht beeinflussbar sind. Die auf diese Weise gewichtete Zeit wird als empfundene Reisezeit bezeichnet. Für jeden Umsteigevorgang wird eine Mindestumsteigegehzeit von 3 Minuten angenommen.

4 Vorgehensweise bei der Angebotserstellung

4.1 Planerische Vorgehensweise

Für die Testinstanz werden zwei planerische Lösungen P_1 und P_2 entwickelt, die in Abbildung 2a und. 3a dargestellt sind. Die Vorgehensweise bei der Erstellung der beiden planerischen Lösung lässt sich vereinfacht wie folgt beschreiben:

1. Festlegung eines Systemtakts: Um einen merkbaren Fahrplan und regelmäßige Anschlüsse zwischen den Linien anbieten zu können, wird aus der Nachfrage ein Systemtakt (Grundtakt) abgeleitet. Für die Testinstanz wird ein 20-Minutentakt (Frequenz = 3) gewählt. Bei diesem Systemtakt gewährleisten Linienlängen von 6 und 8 Strecken eine geringe Standzeit bei einer linienreinen Umlaufbildung.

2. Festlegung eines Linienplans: Beiden planerischen Lösungen liegt die Idee eines zentralen Umsteigeknotens im Zentrum (Knoten 303) zugrunde. Die Lösung P_1 baut auf einer Stammachse auf, was zu einer achsensymmetrischen Lösung führt. Bei Lösung P_2 sind vier Linien punktsymmetrisch. Aus Kapazitätsgründen ist in beiden Lösungen eine Verstärkerlinie (B6 bzw. B3) erforderlich.

3. Fahr- und Umlaufplanung: Ausgangspunkt der Fahrplanung sind linienreine Fahrzeugumläufe. Für jede Linie ergibt sich so bei gegebener Linienlänge und gegebenem Takt eine minimale Fahrzeugzahl mit den zugehörigen Kosten. Nun wird der Fahrplan manuell so angepasst, dass die minimale Fahrzeuganzahl erhalten bleibt und die mittlere empfundene Reisezeit reduziert wird. Bei der Fahrplanung helfen Bildfahrpläne und schematische Taktfahrpläne, die Ankunfts- und Abfahrtszeiten am Umsteigeknoten zu visualisieren. Nach jeder Änderung werden die Kenngrößen Kosten, empfundene Reisezeit, sowie maximale Auslastung mit einer Umlegung und einer Umlaufbildung ermittelt. Im Projekt erfolgt die Berechnung mit dem Planungsprogramm PTV-Visum ([19]).

4.2 Algorithmische Vorgehensweise

Für die Erstellung der algorithmischen Lösungen werden die in der Software-Bibliothek LinTim ([9], [17]) gesammelten Optimierungsroutinen zur Planung des öffentlichen Verkehrs genutzt. Dabei ergibt sich folgender Ablauf:

1. Erstellen eines Linienpools: Linienplanungsverfahren benötigen eine Auswahl an potentiellen Linien, den sogenannten Linienpool. Als Linienpool kann man eine Menge an manuell erstellten Linien wählen. Zur automatischen Erzeugung eines Linienpools stellt LinTim eine in [8] entwickelte Methode bereit. Hierfür werden iterativ Linien erstellt, bis die Nachfrage bedient werden kann. Diese Linien basieren auf den gegebenen Streckenbelastungen im Netzwerk und dem Quell- bzw. Zielverkehr für jede Verkehrszelle. Die Streckenbelastungen werden aus den planerischen Lösungen abgeleitet und dienen als Startlösung für die Linienpoolerstellung.

2. Berechnung eines Linienplans mit Frequenzen: Einen Überblick über verschiedene Methoden zur Linienplanung gibt [13]. In der vorliegenden Arbeit wurde ein ganzzahliges Programm mit einer Kosten-Zielfunktion verwendet, das garantiert, dass die Nachfrage abgedeckt wird.

3. Fahrplanung: Ein Überblick über verschiedene Fahrplanungsmethoden kann z.B. in [12] gefunden werden. Für die vorliegenden Berechnungen wird ein PESP-Modell auf Basis eines Ereignis-Aktivitäts-Netzwerks gelöst, das die Reisezeit der Passagiere in einem periodischen Fahrplan minimiert. Dazu wird die Modulo-Simplex Heuristik aus [10] verwendet.

4. Umlaufplanung: [7] gibt einen Überblick über verschiedene Umlaufplanungsmodelle. Für diese Arbeit wird eine in [18] implementierte Methode verwenden, die auf einem Flussproblem basiert und die Summe aus Fahrzeugkosten und Leerkilometern minimiert. Der entstehende Umlaufplan ist im allgemeinen nicht linienrein, sondern erlaubt, dass ein Fahrzeug mehrere Linien bedient.
Als Ergebnis dieses Vorgehens erhält man ein Verkehrsangebot bestehend aus einem Linienplan, einem Fahrplan und einem dazu passenden Umlaufplan. Zur Bewertung dieser Pläne werden die in Abschnitt 2 erläuterten Kenngrößen ermittelt: die durchschnittliche empfundene Reisezeit der Passagiere auf Grundlage einer Bestweg-Umlegung sowie die sich aus der Anzahl der Fahrzeuge, der gesamten Fahrtzeit und der gefahrenen Kilometer ergebenden Kosten des Verkehrsangebots. Mit Hilfe dieser Kenngrößen werden automatisch erzeugte Lösungen bewertet und mit den planerisch erzeugten Lösungen verglichen.

5 Ergebnisse

5.1 Beschreibung der Lösungen

Für die in Abschnitt 3 beschriebene Testinstanz werden die beiden planerischen Lösungen P_1 und P_2 mit folgenden automatisiert erstellten Lösungen verglichen. Diese sind nach dem in Abschnitt 4.2 beschriebenen Vorgehen erstellt und unterscheiden sich durch den jeweils zugrunde gelegten Linienpool und den Grad der Automatisierung.

- P_1 und P_2 - Planerische Lösungen: Dargestellt in Abbildung 2a bzw. 3a.

- A_1_1 und A_2_1 - Planerisches Linienkonzept + LinTim: Hier werden der Linienplan und die Frequenzen der entsprechenden planerischen Lösung übernommen, der Fahrplan und der Umlaufplan werden mit LinTim erstellt.

- A_1_2 und A_2_2 - Planerischer Pool + LinTim: Hier werden nur die Linien der jeweiligen planerischen Lösung übernommen und als Linienpool verwendet; die Frequenzen, der Fahrplan und der Umlaufplan werden durch LinTim erstellt. Die Ergebnisse sind in Abbildung 2b bzw 3b dargestellt.

- A_1_3 und A_2_3 - Gerader Pool + LinTim: Der Linienpool für diese Lösung besteht aus den zehn horizontalen und vertikalen Linien durch den Grid Graphen. Alle Pläne werden durch LinTim erstellt. Die sich ergebenden Linien sind in Abbildung 2c bzw 3c dargestellt.

- A_1_4 und A_2_4 - LinTim-Pool + LinTim: Diese Lösung wird vollautomatisch durch Lin- Tim erzeugt. Das schließt das Auffinden eines Linienpools durch LinTim mit ein. Die Er- gebnisse werden in Abbildung 2d bzw 3d dargestellt.

- A_1_5 und A_2_5 - LinTim-Pool und Planerischer Pool + LinTim: In dieser Lösung werden dem von LinTim erstellten Linienpool noch die Linien aus der planerischen Lösung zugefügt, Linienplan, Fahrplan und Umlaufplan werden durch LinTim erstellt. Die Ergebnisse sind in Abbildung 2e bzw 3e dargestellt.

5.2 Bewertung der Lösungen

Die sich ergebenden Lösungen werden untereinander und mit der grundliegenden planerischen Lösung anhand ihrer Kenngrößen Kosten und empfundene Reisezeit (siehe Abschnitt 2) bewertet und in den Abbildungen 4a und 4b dargestellt. Die mittlere empfundene Reisezeit der dargestellten Lösungen liegt zwischen 18 und 26 Minuten. Bei einer für den Fahrgast optimalen Lösung, in der jeder Fahrgast auf direktem Weg ohne Umstieg befördert wird, würde die mittlere empfundene Reisezeit 15,4 Minuten betragen. Die Kosten für solch ein Angebot würden bei 24.600 Euro/h liegen, also eine ungefähre Steigerung um den Faktor 12 im Vergleich zu den Besten hier vorgestellten Lösungen. Dafür müssten über 300 Fahrzeuge vorgehalten werden, die auf den meisten Relationen lediglich ein Fahrt pro Stunde anbieten.

Bild 2: Linienwege der Lösungen basierend auf P_1

Bild 3: Linienwege der Lösungen basierend auf P_2

Bild 4: Kenngrößen der Lösungen

Tabelle 2: Kenngrößen der Lösungen

Betrachtet man die Auswirkung der Optimierungsalgorithmen auf die Fahr- und Umlaufplanung, so lässt sich zunächst feststellen, dass der planerisch gefundene Umlaufplan für den Fahrplan bereits optimal ist. Hier konnte in keiner planerischen Lösung eine Verbesserung erreicht wer- den. Hält man von P_2 nur die Linien und ihre Frequenzen fest, kann die Fahrplanerstellung mit LinTim durch eine zusätzliche Synchronisierung der Taktung eine Verbesserung der empfundenen Reisezeit erreichen (A_2_1). Ein darauf aufbauender Umlaufplan hat allerdings deutlich höhere Kosten, da die Umläufe nun schlechter synchronisiert sind als in der planerischen Lösung.

Für P_1 ist eine solche Verbesserung nicht so einfach möglich, eine Verbesserung der empfundenen Reisezeit tritt hier erst nach zusätzlicher Anpassung der Frequenzen auf. Dies führt dann aber auch zu einem Umlaufplan mit geringeren Kosten als bei P_1.

Der Grund liegt darin, dass die in der Optimierung gefundene Lösung niedrigere Frequenzen wählt als in der planerischen Lösung (siehe auch Abbildung 2b), die gerade noch für den Transport der Fahrgäste ausreichen und durch Synchronisierung der Umstiege eine bessere empfundene Reisezeit für die Passagiere im Vergleich zur planerischen Lösung erreicht.

Die weiteren Lösungen zeigen, dass der Einfluss des zugrunde gelegten Linienpools auf die Erstellung des Linienplans, des Fahrplans und des Umlaufplans signifikant ist. Wählt man als Linienpool ausschließlich die Menge der geraden Linien, so ergeben sich die in den Abbildungen 2c/3c dargestellten Lösungen A_1_3/A_2_3, die entweder in der empfundenen Reisezeit oder in den Kosten schlechter abschneidet als alle anderen Lösungen. Der Grund ist die beschränkte Auswahl an potentiellen Linien. Ob diese für die Passagiere gut geeignet sind, hängt von den Startbelastungen der Kanten ab. Wenn P_1 als Ausgangspunkt genutzt wird, sind die Belastungen so verteilt, dass 6 Linien zum Erreichen der Kapazitätsziele ausreichen. Dies führt daraufhin zu einer kostengünstigen Lösung, die allerdings keine guten Passagierkennzahlen aufweist. Das umgekehrte Bild tritt bei P_2 als Ausgangspunkt auf, da hier alle 10 Linien eingerichtet werden müssen. Dies führt zu einer besseren Abdeckung für die Passagiere, die aber sehr teuer ist. Es muss also bereits bei der Erstellung des Linienpools im ersten Schritt, des in Abschnitt 4 beschriebenen Prozesses, Aufmerksamkeit geschenkt werden.

Dies wird in den beiden verbliebenen Lösungsansätzen umgesetzt. Hier wird mit Hilfe von Lin-Tim ein Linienpool erzeugt, der anschließend noch um die Linien aus der planerischen Lösung ergänzt wird. Für beide Pools werden durch LinTim automatisch Linienplan, Fahrplan und Umlaufplan erstellt. Da der Linienpool ohne Hinsicht auf Kosten erzeugt wird, entstehen hier in beiden Fällen Lösungen, die verhältnismäßig teuer sind. Dafür kann im Fall von A_2_4 aber auch eine gute empfundene Reisezeit erreicht werden.

Ergänzt man den LinTim Pool noch um die Linien aus der planerischen Lösung, so erhält man in beiden Fällen Lösungen (A_1_5 und A_2_5), welche die Lösung des Vorschrittes (A_1_4 und A_2_4) hinsichtlich beider Zielfunktionen verbessern kann. Die größere Auswahl an Linien erlaubt einen Linienplan, der sowohl einen guten Fahrplan als auch einen guten Umlaufplan ermöglicht. Diese Lösung weist in beiden Szenarios die niedrigste empfundene Reisezeit und geringe Kosten auf. Sie liegt für beide Ausgangssituationen auf der Pareto-Front der Lösungen, d.h. es gibt keine Lösung, die in beiden Zielfunktionen besser ist. Allerdings treten in dieser Lösung sehr unterschiedliche Frequenzen der Linien auf, sie ist also weit von einem in der Verkehrsplanung üblichen Systemtakt entfernt.

Sowohl bei der Erstellung der planerischen als auch der algorithmischen Lösung findet nach der Angebotserstellung eine erneute Umlegung statt, so dass Änderungen des Angebots auf die Routenwahl wirken. In der planerischen Lösung werden diese Änderungen in der Angebotserstellung berücksichtigt und die Lösung entsprechend angepasst. In dem fertig erstellten Verkehrsangebot treten also weder auf Strecken- noch auf Fahrplanebene Überlastungen auf.

Dies muss für die algorithmisch gefundene Lösung nicht gelten. Die Optimierungsalgorithmen finden eine Lösung, die für die Ausgangssituation optimal ist, sich daraufhin ändernde Routen werden in der aktuellen Studie aber nicht berücksichtigt. Damit ist die gefundene Lösung zwar zulässig bezüglich der ursprünglichen Routen, eine Erfüllung der Kapazitäten ist für die neu gewählten Wege aber weder auf Strecken- noch auf Fahrplanebene garantiert. Bei der algorithmischen Lösung treten daher auf einzelnen Fahrplanfahrten Überlastungen auf. Für die Lösungen A_1_4 und A_2_4 gilt dies sogar auf Streckenebene.

Die Berücksichtigung der neuen Wege direkt bei der Erstellung von Linien- und Fahrplänen ist ein aktuelles Forschungsthema. Erste Ansätze dazu lassen sich z.B. in [5] und [15] finden.

6 Fazit und Ausblick

In der vorliegenden Untersuchung wurde anhand einer einfachen Testinstanz gezeigt,

a) dass eine planerische Lösung durch Optimierungsroutinen verbessert werden kann, die eine bessere Synchronisation erreichen und sparsamere Frequenzen nutzen,
b) dass es möglich ist, Lösungen mit vergleichbarer Qualität auch vollautomatisch zu erzeugen,
c) dass algorithmische Lösungen einer Rückkopplung mit der Umlegung bedürfen, um Kapazitätsüberschreitungen auszuschließen, und
d) dass die besten Ergebnisse durch ein Zusammenspiel von Planung und Optimierung erzielt werden, nämlich wenn man die Linien aus der planerischen Lösung mit automatisch erzeugten Linien zusammenlegt, um den Linienpool für die Optimierung zu bilden.

Es ist zu bemerken, dass die betrachteten Kennzahlen nicht die einzigen Kriterien zur Beurteilung der Qualität einer Lösung sein können. So zeichnet sich die planerische Lösung gegenüber der algorithmischen Lösung durch ein symmetrisches Liniennetz mit weniger Linien aus, was die Übersichtlichkeit verbessert. Außerdem erleichtert die Anwendung eines Systemtakts die Merkbarkeit des Fahrplans.

Das beschriebene Vorgehen soll auf zusätzliche Randbedingungen (z.B. maximal 2 Frequenzen), weitere Testinstanzen und schließlich auf größere Beispiele aus der Praxis in der Region Stuttgart erweitert werden. Unter anderem soll untersucht werden, wie sich Linienstrukturen optimaler Lösungen bei wachsenden Netzen oder Nachfrageverlagerungen verändern, und in wie weit der in Abschnitt 4 beschriebene sequentielle Ablauf des Planungsprozesses durch eine integrierte Lösung verbessert werden kann, siehe dazu die in [14] beschriebene Vorgehensweise. Es sollen außerdem weitere Verfahren für das Passagierrouting untersucht werden, die eine genauere Berechnung der Kennzahl Reisezeit ermöglichen könnten. Hier gibt es Abweichungen bei den Ergebnissen von LinTim und Visum. In stark ausgelasteten Netzen muss die Umlegung so erweitert werden, dass Kapazitäten bei der Routen- und Verbindungswahl berücksichtigt werden.

7 Literatur

7.1 Bücher

[1]    ALT, B. Investigation of space-time structures in public transport networks and their optimization. PhD thesis, ETH Zürich, 2010.

[2]    BORNDÖRFER, R. Mathematical Optimization and Public Transportation. Habilitation, Technische Universität Berlin, 2010.

[3]    KIRCHHOFF, P. Städtische Verkehrsplanung: Konzepte, Verfahren, Maßnahmen. Teubner Verlag, 2002.

[4]    KRUG, S. Ein interaktives Programmsystem zur Angebotsplanung für den liniengebundenen öffentlichen Personennahverkehr. PhD thesis, Technische Universität Braunschweig, 1987.

[5]    SCHMIDT, M. Integrating Routing Decisions in Public Transportation Problems, vol. 89 of Optimization and Its Applications. Springer, 2014.

[6]    VUCHIC, V. Urban Transit: Operations, Planning and Economics, 1 ed. John Wiley & Sons, Inc., Hoboken, New Jersey, 2005.

7.2 Zeitschriftenartikel

[7]    BUNTE, S., AND KLIEWER, N. An Overview on Vehicle Scheduling Models. Public Transport 1, 4 (2009), 299–317.

[8]    GATTERMANN, P., HARBERING, J., AND SCHÖBEL, A. Line Pool Generation. Public Transport (2016). accepted.

[9]    GOERIGK, M., SCHACHTEBECK, M., AND SCHÖBEL, A. Evaluating line concepts using travel times and robustness: Simulations with the lintim toolbox. Public Transport 5, 3 (2013).

[10]    GOERIGK, M., AND SCHÖBEL, A. Improving the Modulo Simplex Algorithm for Large-Scale Periodic Timetabling. Computers and Operations Research 40, 5 (2013), 1363–1370.

[11]    KARAKOSTAS, G., AND KOLLIOPOULOS, S. Stackelberg strategies for selfish routing in general multicommodity networks. Algorithmica 53, 1 (2009), 132–153.

[12]    LIEBCHEN, C. Periodic Timetable Optimization in Public Transport. Springer, 2007.

[13]    SCHÖBEL, A. Line Planning in Public Transportation: Models and Methods. OR Spectrum 34, 3 (2012), 491–510.

[14]    SCHÖBEL, A. An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation. Transportation Research C 74 (2017), 348–365.

7.3 Beiträge aus Tagungsbänden

[15]    GATTERMANN, P., GROSSMANN, P., NACHTIGALL, K., AND SCHÖBEL, A. Integrating Passengers’ Routes in Periodic Timetabling: A SAT approach. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016) (2016), vol. 54, pp. 1–15.

7.4 Schriftenreihen

[16]    FRIEDRICH, M. Rechnergestütztes Entwurfsverfahren für den ÖPNV im ländlichen Raum. Schriftenreihe des Lehrstuhls für Verkehrs- und Stadtplanung, Technische Universität München 5 (1994).
7.5.    Sonstiges

[17]    GATTERMANN, P., HARBERING, J., SCHIEWE, A., AND SCHÖBEL, A. LinTim - Integrated Optimization in Public Transportation. Homepage.
See http://lintim.math.uni-goettingen.de/.

[18]    UFFMANN, A. Das Kanalmodell zur Effizienzsteigerung in der Fahrzeugumlaufplanung. Diplomarbeit (2010). Fakultät für Mathematik und Informatik, Georg August Universität Göttingen.

Miscellaneous

[19]    PTV GROUP. PTV Visum. Homepage. See http://vision-traffic.ptvgroup.com/de/produkte/ptv-visum/.