Die Synchronisierung von Fahrplänen verschiedener Anbieter im öffentlichen Nahverkehr ist ein schwieriges Abstimmungsproblem. Bisherige Verfahren optimieren die Fahrpläne einzelner Verkehrsunternehmen, aber gerade in regionalen Gebieten mit nicht getakteten Fahrplänen besteht noch ein großes Abstimmungspotential zwischen den verschiedenen Unternehmen. Mit Hilfe einer adäquaten Modellierung und mathematischen Methoden liefern wir einen Ansatz, der die Anschlussqualität für die Fahrgäste verbessert.

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

1 Einleitung

Der Bedarf der Fahrplansynchronisierung im öffentlichen Nahverkehr entsteht, wenn mehrere verschiedene Unternehmen innerhalb eines Verkehrsgebietes operieren (siehe [1], [2], [3] und [4]). Die internen Fahrpläne der einzelnen Unternehmen sind gut synchronisiert, aber gerade an wichtigen Umsteigepunkten wie Hauptbahnhöfen ist großer Optimierungsspielraum vorhanden. Durch die vielen Umsteigemöglichkeiten, die alle jeweils ein eigenes Optimierungsziel darstellen, ist das Problem stark mehrkriteriell. Bei der Verbesserung von Anschlüssen muss also immer das Netzwerk als Ganzes betrachtet werden, ohne dabei die einzelnen Anschlüsse aus den Augen zu verlieren.

Ziel der Fahrplansynchronisierung ist es, durch kleine Veränderungen der Abfahrtszeiten der einzelnen Linien bessere Umsteigemöglichkeiten für die Fahrgäste zu schaffen. „Besser” entspricht hier nicht einer Minimierung der Wartezeit, da kurze Wartezeiten das Risiko mit sich bringen, bei einer Verspätung den geplanten Anschluss zu verpassen. Unser Ziel ist es Wartezeiten zu erzeugen die „komfortabel” sind, nicht zu kurz aber auch nicht zu lang. Das Problem zeichnet sich vor allem durch seinen globalen Charakter aus; Verbesserungen der Anschlüsse an einem Punkt im System führen häufig zu Verschlechterungen von anderen Anschlüssen.

Der Abstimmungsprozess beinhaltet die Kooperation und Kommunikation von verschiedenen Akteuren innerhalb eines Netzes. Dies sind meist Verkehrsunternehmen, deren Fokus zunächst auf dem eigenen Netz liegt. Ein global guter Fahrplan ist aber für alle Teilnehmer von Vorteil, daher ist ein gemeinsamer Abstimmungsprozess sinnvoll. Hierfür werden sowohl eine geeignete Modellierung als auch mathematische Optimierungstechniken benötigt. Über eine entsprechende Software-Plattform werden diese den Unternehmen zur Verfügung gestellt.

Dieser Artikel liefert zunächst eine Einführung in die Problemstellung der Fahrplansynchronisierung. Anschließend stellen wir die von uns angewandten mathematischen Optimierungstechniken vor. Neben einer Erweiterung der Verfahren um die Umlaufplanung, präsentieren wir noch eine mögliche Einbettung des Konzepts in die derzeitigen Prozesse der Fahrplanabstimmung. Die Arbeit ist eine Erweiterung der auf der Heureka ’08 vorgestellten Ergebnisse (siehe [5]).

2 Problembeschreibung und Modellierung

2.1 Ausgangslage

Innerhalb einer Region obliegt es meist dem Verkehrsverbund für eine gute Abstimmung der Fahrpläne zu sorgen. Hierbei gilt es, die Pläne der einzelnen Verkehrsunternehmen (z.B. Bahn, Regionalbusse, Stadtbusse) so aneinander anzupassen, dass die Passagiere möglichst komfortabel ihr Reiseziel erreichen. Ein Problem bei diesem Prozess ist, dass Änderungen oft nicht wirtschaftlich sind, da die neu erstellten Fahrpläne die firmeninternen Randbedingungen (wie etwa die begrenzte Anzahl an Fahrzeugen im Fuhrpark) nicht erfüllen. Des Weiteren übersteigt die Menge der zu überblickenden Informationen häufig das Maß, das von Menschen noch manuell bewältigt werden kann.

Eine Konsequenz dieser Problematik ist, dass der Verbesserungsspielraum bei der Abstimmung im öffentlichen Verkehr oft nicht richtig ausgenutzt wird. Es fehlt an unterstützenden Modellen und einer entsprechenden Software, die den Verkehrsplaner während des Planungsprozesses optimal assistieren. Ein weiteres Problem ergibt sich aus dem sehr kurzen Zeitraum, der für den Abstimmungsprozess zur Verfügung steht. Die einzelnen Unternehmen erstellen individuell für sich gut abgestimmte Fahrpläne, die dann an den Verkehrsverbund geschickt werden. Dieser hat daraufhin nur wenig Zeit, um nach guten Kompromissen zu suchen.

Das Ziel unserer Arbeit ist es, mit mathematischen Modellen die Umsteigesituation im öffentlichen Nahverkehr möglichst adäquat darzustellen und mit Hilfe von Optimierungsalgorithmen gute Lösungsvorschläge für Verbesserungen zu entwickeln. Einerseits kann somit der Optimierungsspielraum des Gesamtsystems besser ausgeschöpft werden. Andererseits ergibt sich die Möglichkeit den gemeinsamen Abstimmungszeitraum zu verlängern, da die Modellierungs- und Bewertungsverfahren frühzeitig als Kommunikationsmittel zwischen den Verkehrsunternehmen während der Planungsphase dienen können.

2.2 Modellierung der Problemstellung

Die Linien, also die Routen auf denen ÖPNV-Fahrzeuge im Verkehrsverbund fahren, sind das Kernelement eines Fahrplans. Eine Linie besteht dabei aus mehreren Fahrten, die den Touren der einzelnen Fahrzeuge entsprechen. Die Fahrten sind definiert durch die Zeitpunkte der Ankunft bzw. Abfahrt an den einzelnen Haltestellen.

Ein weiterer wichtiger Aspekt ist die Auswahl der betrachteten Umsteigepunkte. Hierbei ist es nicht sinnvoll alle Haltestellen im Netz zu analysieren, da einerseits die Datenmenge unüberschaubar wäre und andererseits der Fokus der Kunden beim Umsteigen im Allgemeinen auf die wichtigen Umsteigepunkte beschränkt ist. Die Kunden im ÖPNV sehen Haltestellen außerdem nicht zwangsläufig als isoliert an. Stattdessen werden häufig kurze Strecken zwischen nahegelegenen Haltestellen zu Fuß zurückgelegt um eine gute Verbindung zu erhalten. Daher betrachten wir nicht einzelne Haltestellen, sondern so genannte Netzknoten. Diese fassen eine oder mehrere Haltestellen in Laufreichweite zu einem gemeinsamen Umsteigepunkt zusammen.

Als Freiheitsgrade für die Veränderung der gegebenen Fahrpläne erlauben wir kleine zeitliche Änderungen („Shifts“) an den Abfahrtszeiten der einzelnen Linien. Ein Shift von +3 Minuten bedeutet hierbei, dass alle Fahrzeuge der betreffenden Linie ihre Fahrten drei Minuten später beginnen. Ziel dieser Änderungen ist es nicht einen komplett neuen Fahrplan zu erstellen, sondern den gegebenen Fahrplan mit gezielten Eingriffen zu verbessern.

Neben der Modellierung der Infrastruktur ist auch eine geeignete Projekthierarchie wichtig. Für eine Region mit ausgewählten Netzknoten wird zunächst ein Projekt definiert. Hierbei wird festgelegt, welche Linien und Netzknoten betrachtet werden sollen. Es ist dabei nicht sinnvoll, alle Wochentage bzw. alle Tageszeiten gleichzeitig zu untersuchen, da die Fahrgastströme zum Beispiel vormittags (stadteinwärts) und abends (stadtauswärts) sehr unterschiedlich sein können. Daher enthält jedes Projekt verschiedene Planungen, also Festlegungen von betrachteten Zeitintervallen. Eine Planung beinhaltet alle relevanten Fahrten innerhalb des Zeitintervalls und wird auf die Ziele des Verkehrsplaners durch eine Gewichtung der Anschlüsse und spezielle Randbedingungen eingestellt. Jede dieser Planungen enthält wiederum einen oder mehrere Planungsstände, die den einzelnen Verbesserungsvorschlägen (also Shift-Kombinationen) entsprechen. Die Struktur einer Projekthierarchie ist in Bild 1 dargestellt.

Bild 1: Schematische Darstellung einer Projekthierarchie

Ein weiterer wichtiger Punkt bei der Modellierung von öffentlichen Nahverkehrssystemen ist, dass es nicht ausreicht das Netzwerk nur auf einer Systemebene zu betrachten. Ein neuer Fahrplanvorschlag, der das Netz global stark verbessert, ist oft nicht akzeptabel, wenn dabei einige wichtige Anschlüsse verloren gehen. Daher ist es nötig dem Verkehrsplaner alle relevanten Informationen auf verschiedenen Ebenen zur Verfügung zu stellen, damit er die Auswirkungen von geplanten Veränderungen im Auge behalten kann. Die durch unser Konzept abgedeckten Ebenen sind:

- eine globale Betrachtung die das Netz als Ganzes umfasst,

- eine Betrachtung auf der Ebene der einzelnen Netzknoten,

- die Umsteigemöglichkeiten zwischen zwei Linien an einem Netzknoten,

- die detaillierte Darstellung der einzelnen Anschlüsse.

Diese Betrachtungsweise erlaubt es dem Verkehrsplaner das gesamte Netz zu überblicken ohne dabei die wichtige Detailsicht auf die einzelnen Anschlüsse zu verlieren. Durch die hierarchische Anordnung können ungünstige Abstimmungen schnell aufgespürt und auf Verbesserungspotential analysiert werden. Dies ist sowohl zur Bewertung von neu entwickelten Fahrplänen als auch zur Analyse des Ist-Fahrplans sehr hilfreich.

2.3 Bewertung der Anschlussqualität

Wie man die Anschlussqualität bewertet ist eine der grundlegenden Fragestellungen bei der Fahrplansynchronisierung. Für unsere Bewertungsfunktion nutzen wir die Wartezeit des Fahrgastes an der Haltestelle bevor er in sein Zielfahrzeug einsteigt. Diese Wartezeit unterteilen wir in fünf Klassen, die in Bild 2 dargestellt sind. Neben den intuitiven Bereichen „Risiko“, „Komfort“ und „Geduld“ betrachten wir außerdem noch kurze negative Wartezeiten, die so genannten „Beinahe“-Anschlüsse. Diese zeichnen sich dadurch aus, dass sie einerseits für den Kunden eine sehr unbefriedigende Situation darstellen, andererseits aber schon durch kleine Änderungen in real existierende Anschlüsse umgewandelt werden können. Deswegen bieten die Beinahe-Anschlüsse einen ersten Ansatzpunkt um eine bessere Synchronisierung zu erzeugen.

Bild 2: Unterteilung der Wartezeit in verschiedene Intervalle

Ordnet man den verschiedenen Intervallen Strafwerte zu (ein geringer Strafwert bei Komfort, ein hoher Wert bei Beinahe), erhält man eine Treppenfunktion. Mit geeigneten Glättungsverfahren kann man auf diese Weise eine kontinuierliche Funktion erzeugen, die den einzelnen Wartezeiten einen zugehörigen Strafpunktewert zuweist (siehe [5]).

Um zwischen wichtigen und weniger wichtigen Anschlüssen zu unterscheiden, bewerten wir die Anschlüsse mit Prioritäten, A (wichtig), B (normal) oder C (unwichtig). Diese Einstufung kann man auch bei Bedarf durch zuvor ermittelte Fahrgastzahlen ersetzen. Die Bewertung der einzelnen Anschlüsse wird durch den Verkehrsplaner ausgeführt, der somit sein Expertenwissen in die Modellierung einfließen lassen kann.

3 Optimierungsansatz

Das Optimierungsproblem für die Anschlusssynchronisierung im öffentlichen Nahverkehr zeichnet sich durch seinen mehrkriteriellen Charakter aus. Hierbei müssen die gegenläufigen Ziele der Verkehrsplaner berücksichtigt werden. Durch die starke Vernetztheit der Fahrpläne und die nicht-linearen Zielfunktionen ergibt sich somit eine sehr anspruchsvolle mathematische Fragestellung. Diese lösen wir durch eine Kombination aus Metaheuristiken, die in der Lage sind schnell qualitativ hochwertige Lösungen zu generieren, und exakten mathematischen Verfahren, die die Qualität der Lösungen durch die Berechnung von unteren Schranken validieren.

3.1 Zielfunktionen und Randbedingungen

Die Ergebnisse der Optimierung lassen sich generell durch zwei Faktoren beeinflussen. Die Zielfunktionen steuern das Verhalten der Optimierungsalgorithmen, indem sie eine Art
„Richtung“ im Lösungsraum vorgeben. Randbedingungen hingegen sind fixe Eigenschaften der Problemstellung, die den Suchraum einschränken.

Die Ziele der Verkehrsplaner lassen sich in drei Bereiche unterteilen:

- Verbessere die gemittelte Anschlussqualität im betrachteten Gebiet, bzw. maximiere die globale Kundenzufriedenheit.

- Verhindere zu starke lokale Verschlechterungen bei den neu generierten Plänen, bzw. minimiere die Unzufriedenheit der Kunden über die geplanten Änderungen.

 - Erhalte die Struktur der etablierten Fahrpläne; Fahrpläne sollen durch kleine Änderungen synchronisiert und nicht neu geplant werden.

Die genaue Struktur der Zielfunktionen kann dabei individuell mit den Verkehrsplanern abgestimmt werden. Es ist jedoch nicht sinnvoll mehr als eine Zielfunktion aus einem Bereich zu wählen, da das Lösen der Optimierungsaufgabe mit steigender Anzahl der Zielfunktionen schwieriger wird. Sollen für die Ergebnisse der metaheuristischen Verfahren verifizierende Schranken bestimmt werden, so ist es wichtig, dass die einzelnen Funktionen maximal quadratisch von den Variablen der Linien abhängen.

In die Randbedingungen gehen hingegen Einschränkungen ein, die aufgrund von physikalischen Gegebenheiten nicht veränderbar sind (z.B. wenn ein Zug nicht früher abfahren kann, weil die Schienen durch einen Fernzug belegt sind) oder die vom Verkehrsplaner als nicht änderbare Umsteigesituationen gekennzeichnet werden. Letzteres kann zum Beispiel eine Umsteigemöglichkeit für Schüler sein oder ein gut synchronisierter Treffpunkt von mehreren Bussen. Für die mathematische Umsetzbarkeit dieser Randbedingungen sollten diese Formulierungen auch maximal quadratisch von den Variablen der Linien abhängen, damit die Metaheuristiken effizient die ausgeschlossenen Gebiete im Suchraum vermeiden können.

3.2 Lösung mit Metaheuristiken

Für die Optimierung der Umsteigebeziehungen haben wir drei verschiedene Metaheuristiken verwendet. Dies sind ein Ameisenalgorithmus, ein genetischer Algorithmus und ein Simulated Annealing Ansatz. Alle drei Verfahren wurden für verschiedene Probleminstanzen mit unterschiedlichen Randbedingungen und jeweils drei Zielfunktionen getestet. Als Ergebnis liefern die Algorithmen eine Approximation der drei-dimensionalen Pareto-Menge (also der Menge der nicht dominierten Lösungen).

Eine detaillierte Beschreibung der verschiedenen Ansätze und ein Vergleich ihrer Effizienz präsentieren wir in [6]. Fazit der Berechnungen ist, dass sich alle drei Verfahren ähnlich verhalten und dass sich die Ergebnisse deutlich durch einen hybriden Ansatz mit einem Local Search Algorithmus verbessern lassen. Bei Problemstellungen mit einer größeren Anzahl an Randbedingungen, also in den Fällen wo es den Algorithmen schwer fällt überhaupt Lösungen zu finden, zeigt sich ein Vorteil der Ameisenalgorithmen. Dies ist dadurch zu erklären, dass das Verfahren konstruktiv ist und nicht von zuvor berechneten Startlösungen abhängt.

Offen bleibt bei dem Ansatz mit Metaheuristiken aber die Güte der berechneten Approximation, da die Algorithmen keine Qualitätsgarantie beinhalten. Eine Lösung dieses Problems wird im folgenden Abschnitt vorgestellt.

3.3 Mathematische Formulierung des Problems

Um die Qualität der berechneten Lösungsalternativen abschätzen zu können, setzen wir mathematische Verfahren der linearen und der ganzzahligen Optimierung ein.

3.3.1 Exakte Verfahren

Das Fahrplansynchronisierungsproblem lässt sich als ganzzahliges Programm formulieren. Die Formulierung (siehe (1)) entspricht dem so genannten Quadratischen Semi-Assignment Problem (QSAP) für das bekannt ist, dass es NP-schwer ist. Die Schwierigkeit entsteht durch den quadratischen Teil der Zielfunktion.

Formel (1) siehe PDF.

Bezogen auf das hier vorgestellte Problem entspricht eine Variable xij der Entscheidung, ob Linie i der Shift j zugeordnet wird (xij =1) oder nicht (xij =0). Die Anzahl der Linien ist m und die Anzahl der möglichen Shifts für Linie i ist ni. Die Koeffizienten der Zielfunktion (bij bzw. cijkl) beschreiben die Qualität der Umsteigemöglichkeit zwischen den verschiedenen Linien.

Mit Hilfe von Linearisierungstechniken kann man die Formulierung in ein gemischt- ganzzahliges lineares Programm umwandeln. Hierfür werden die Produkte von Entscheidungsvariablen in der Zielfunktion durch neue, nicht ganzzahlige Variablen ersetzt.

Durch das Hinzufügen von Constraints bleibt die ursprüngliche Struktur der Lösungen erhalten. Die so entstehende Formulierung lässt sich mit gängigen Lösungsverfahren lösen.

Ein Problem an dieser Herangehensweise ist, dass die Komplexität des Problems sehr lange Rechenzeiten mit sich bringt. Selbst bei relativ kleinen Problemgrößen mit ca. 30 Linien treten für die optimale Lösung eines einkriteriellen Problems Rechenzeiten von mehreren Tagen auf. Dies ist in der Praxis nicht akzeptabel, da für die Bewertung einer mehrkriteriellen Lösungsmenge, wie sie in unserem Fall vorliegt, mehrere dieser Berechnungen nötig sind.

Eine alternative Lösungsstrategie ist daher, auf die Exaktheit der Lösungen zu verzichten und stattdessen untere Schranken zur Bewertung der Lösungsqualität zu bestimmen.

3.3.2 Bestimmung unterer Schranken

Eine bekannte Technik zur Bestimmung unterer Schranken für ein QSAP ist die Aufhebung der Ganzzahligkeit der Entscheidungsvariablen. Das so entstehende lineare Programm (siehe (2)) hat Laufzeiten von unterhalb von einer Minute für 30 Linien.

Formel (2) siehe PDF.

Bei dieser Formulierung ergibt sich aber das Problem, dass die erzielten Schranken nicht gut genug für die Validierung der Ergebnisse der Metaheuristiken sind.

Für das verwandte Quadratische Assignment Problem (QAP) erzielt die „Reformulation Linearization Technique“ gute Lösungen. Hierbei werden durch das stufenweise Hinzufügen weiterer Variablen und neuer Nebenbedingungen stärkere Formulierungen generiert. Verwendet man diese Technik für das QSAP, so erhält man Lösungen die zwar immer noch nicht exakt sind, aber sie liefern als Ergebnis bessere Schranken als das in (2) formulierte lineare Programm.

In [7] erweitern wir diese Technik durch ein Verfahren, das die sehr restriktive stufenweise Verbesserung der Formulierung durch eine neue Technik ersetzt. Hierbei werden nur jene Variablen zu einer neuen Formulierung hinzufügt, die nötig sind um die Strukturen aufzulösen, die für eine schlechte Lösungsqualität verantwortlich sind.

Mit solch einer Methode zur Bestimmung unterer Schranken kann man die Qualität einer mehrdimensionalen Lösungsmenge untersuchen (siehe Bild 3). Um die für die Bewertung benötigten Hyperebenen zu bestimmen, werden die in den Metaheuristiken genutzten Zielfunktionen mit Hilfe von Gewichten zu einer neuen Funktion zusammengefasst. Diese wird dann als Zielfunktion für das relaxierte lineare Programm verwendet.

Bild 3: Lösungen des Fahrplansynchronisierungsproblems (dargestellt durch Punkte) und untere Schranken (dargestellt als Geraden). Die x-Achse zeigt die Qualität der Fahrpläne (je geringer der Wert, desto besser der Fahrplan), die y-Achse stellt die Menge der Änderungen am ursprünglichen Fahrplan dar. Das linke Bild zeigt ein kleines Beispiel (9 Linien), das rechte Bild ein größeres Beispiel (31 Linien).

Rechenergebnisse basierend auf realen Testszenarien zeigen, dass die durch die Metaheuristiken erzielten Approximationen der Pareto-Menge eine sehr gute Lösungsqualität aufweisen.

4 Einbeziehung der Umlaufplanung

Wenn man die Startzeiten aller Fahrten einer Linie oder insbesondere die Startzeit einzelner Fahrten verschiebt, gefährdet man die ursprünglichen Umläufe. Man muss also im Zuge der Anschlussqualitätsverbesserung die Fahrbarkeit des entwickelten Fahrplans im Auge behalten. Das bedeutet in erster Linie, dass die benötigte Flottengröße nicht steigen sollte. Wir müssen die Startzeiten unserer Fahrten nun also so wählen, dass wir sowohl möglichst viele gute Anschlüsse erhalten, als auch möglichst wenige Fahrzeuge benötigen.

Da wir für die Bestimmung der Umlaufsequenzen in ungetakteten Fahrplänen die einzelnen Fahrgastfahrten betrachten müssen statt nur ganze Linien, ist es notwendig einige Einschränkungen vorzunehmen:

Zum einen gehen wir zunächst davon aus, dass alle Busse identisch sind, d. h. wir betrachten nur den so genannten Ein-Depot-Fall. Weiterhin betrachten wir nicht zwangsläufig die Auswirkung der Verschiebungen auf alle Fahrtkombinationen, sondern gehen davon aus, dass es eine vordefinierte Menge Χ⊆Τ×Τ an Fahrtpaaren gibt, für die wir die Anschlussqualität maximieren wollen. T bezeichnet hier die Menge aller Fahrgastfahrten. Wir reduzieren die Menge der betrachteten Fahrtpaare zum Beispiel um alle Paare, die auch in der bestmöglichen Verschiebung keinerlei Umstiege ermöglichen können, da sie zeitlich zu weit entfernt liegen. Außerdem fallen noch alle Fahrtpaare weg, deren Linienpaare irrelevant für die Anschlussqualität sind.

Wir erstellen ein Flussnetzwerk, das alle Verbindungsmöglichkeiten von Fahrten durch Leerfahrten (Deadheads) oder Wartezeiten an der Haltestelle durch Kantenverbindungen repräsentiert. Jede Fahrt i wird dabei durch n_i Knoten dargestellt, wovon jeder einen möglichen Shift darstellt (Bild 4).

Bild 4: Beispiel für einen Ausschnitt aus einem Graphen mit 3 Fahrten mit jeweils 2 bzw. 3 Shifts. Hier gibt es keine Shiftmöglichkeit bei der man alle Fahrten mit einem Umlauf abfahren kann.

Alle Shiftknoten erhalten eine eingehende Kante von einem Depotstartknoten und eine ausgehende Kante in einen Depotendknoten. Darüber hinaus wird noch eine Rücklaufkante vom Depotendknoten zum Depotstartknoten eingefügt. Diese Kante repräsentiert den Einsatz eines neuen Fahrzeugs und wird daher mit den Fixkosten eines Busses bestraft. Alle anderen Kanten können nach Belieben durch Fahrtzeitkosten oder ähnliches gewichtet werden. Die Menge aller Kanten im Graph bezeichnen wir mit A, die Menge aller Knoten mit V.

Die Kantenanzahl kann deutlich reduziert werden, wenn man transitive Strukturen ausnutzt und Kombinationen über Wartezeitkanten ermöglicht (vgl. [8]).

Als ganzzahliges Programm (IP) formuliert erhalten wir dann das folgende Modell:

Formel (3) siehe PDF.
 
Hierbei ist t die Anzahl der Fahrgastfahrten und xij  ist genau dann 1, wenn die Fahrt i dem Shift j zugeordnet wird, za ist genau dann 1, wenn die Kante a in der Lösung enthalten ist. Die erste Nebenbedingung sichert wieder, dass für jede Fahrt genau ein Shift ausgewählt wird. Die zweite Bedingung ist die Flusserhaltungsgleichung, wobei z(δ+(u)) die Werte aller von u ausgehenden Kanten summiert. Die dritte Nebenbedingung sichert einerseits, dass wir für unseren Fluss nur gewählte Shifts verwenden; gleichzeitig bedingt sie aber auch, dass der Fluss alle Fahrten genau einmal enthält.

Man beachte, dass die Koeffizienten q hier einer Belohnungsfunktion für gesicherte Anschlüsse entsprechen, während w der Kostenfunktion auf den Kanten entspricht.

Selbst wenn man die Anschlussqualität vernachlässigt und nur maximal 2 Shifts pro Fahrt zulässt, ist dieses Problem schon NP-schwer und da man jede „Set Cover“-Probleminstanz als ein solches Umlaufproblem auffassen kann, und „Set Cover“ unter der Bedingung P ≠ NP nicht besser als logarithmisch approximiert werden kann, gilt dies folglich auch für das Umlaufproblem in variablen Fahrplänen (siehe z. B. [9]). Dies gilt auch dann noch, wenn außer der Flottengröße keine weiteren Kosten berücksichtigt werden. Dagegen ist das reine Umlaufproblem mit nur einem Shift pro Fahrt im Ein-Depot-Fall durch einen Minimale- Kosten-Fluss-Algorithmus in polynomialer Laufzeit lösbar.

Das Modell lässt sich leicht durch weitere Spezifikationen erweitern, so können z. B. Fahrten einer Gruppe (Linie) auf den gleichen Shift fixiert werden. Da alle Verschiebungen diskret sind, können im Gegensatz zu kontinuierlichen Modellen beliebige Shifts ausgeschlossen werden.

Mit steigender Anzahl von Fahrten und Shifts kann dieses Modell von gängigen Solvern nicht mehr effizient berechnet werden. Daher haben wir eine Reihe von Approximationsalgorithmen und Heuristiken sowohl für die Teilprobleme Umlaufplanung und Anschlussqualitätsmaximierung in variablen Fahrplänen als auch für das integrierte Problem untersucht (siehe [9]). Besonders vielversprechend im Hinblick auf die praktische Anwendbarkeit ist ein dynamischer Programmierungsansatz:

Wir starten mit einer vorgegebenen Umlaufsequenz. Diese könnte zum Beispiel dem aktuell realisierten Umlaufplan entsprechen. Dort kann der Planer die Fahrten auch in mehrere Depotgruppen gliedern und dienstplanungsrelevante Entscheidungen für die Fahrtenverknüpfung treffen. Das Problem ist nun die einzelnen Fahrten so zu verschieben, dass die Umsteigequalität maximiert wird ohne dass die Sequenz ungültig wird.

Bild 5: Die untere Fahrtenfolge ist aktuell ausgewählt, während die obere (und alle anderen) fixiert werden. Jedem variablen Shift wird nun der Profit zugeordnet, den er gegenüber der aktuellen Auswahl aller umlauffremden Fahrten erhält zuzüglich des maximalen Profits seines direkten Vorgängers.

Dieses Problem ist auch dann schon NP-schwer, wenn man nur maximal zwei mögliche Shifts pro Fahrt anbietet. Wir gehen im Folgenden davon aus, dass die für die Anschlussqualität betrachteten Fahrtenpaare immer in zwei verschiedenen Umläufen vorkommen. Unser Ansatz fixiert nun immer alle Umläufe bis auf einen. Für den verbliebenen Umlauf (in Bild 5 wäre dies der untere) kann man nun für jeden Shiftknoten die Gesamtbelohnung bezüglich aller anderen gewählten Shifts berechnen. Dann bestimmt man rekursiv von der ersten bis zur letzten Fahrt für jeden Shift den Vorgänger der den Profit maximiert. Dabei können auch Kosten für die Verbindungen zwischen zwei Fahrten mit eingerechnet werden. Shiftknoten die keinen Vorgänger haben können entfernt werden. Der Shift der letzten Fahrt, der den größten Profit hat, sowie iterativ seine Vorgänger, werden gewählt.

Dieser Algorithmus läuft linear bezüglich der Anzahl der Shiftknoten eines Umlaufs. Man kann nun zum Beispiel zufällig immer einen Umlauf auswählen und dessen Shifts lokal optimieren oder man untersucht iterativ alle Fahrten nacheinander.

5 Lösungsansatz für Fahrplanabstimmungsprozesse

Der vorgestellte Ansatz zur Fahrplansynchronisierung entfaltet seinen Nutzen durch die Integration in die Planungsprozesse des ÖPNV, die stark dezentral organisiert sind. Verkehrsunternehmen oder -verbünde entwickeln Fahrpläne für ihr eigenes städtisches oder regionales Netz. Zum Fahrplanwechsel im Dezember, aber auch unterjährig, werden Anpassungen vorgenommen. Dabei werden in der Regel nennenswerte Anstrengungen unternommen, die Schnittstellen zu benachbarten Verkehrsnetzen im Auge zu behalten und, soweit möglich, gute Anschlüsse herzustellen. Fahrplankonzepte werden per E-Mail ausgetauscht, Fahrplankonferenzen dienen zur Kommunikation von geplanten Änderungen, Genehmigungsstellen prüfen insbesondere die resultierende Anschlussqualität.

Aufgrund der Dezentralität der Planungsprozesse sieht unser Ansatz die Bereitstellung einer Fahrplanabstimmungsplattform vor. Sie ist durch eine zentrale Speicherung von Fahrplankonzepten mit dezentralem Zugriff gekennzeichnet. Dabei geht die Plattform aber weit über einen unternehmensübergreifenden Dokumentenserver hinaus. Kern ist vielmehr die Hinterlegung von gemeinsam entwickelten regionalen Anschlussqualitätsmodellen. Sie bauen auf dem in Abschnitt 2.3 vorgestellten Konzept der Wartezeitklassen „Komfort“, „Risiko“, „Beinahe“ usw. auf und beinhalten eine Priorisierung von Anschlüssen und Anschlussgruppen gemäß einer ABC-Gewichtung. Der Nutzen der Plattform entfaltet sich aus dem Zusammenspiel von hochgeladenen Angebotskonzepten mit den hinterlegten Anschlussqualitätsmodellen. Die Bewertung, wie gut Fahrplankonzepte zusammenpassen, wird von der Plattform geleistet und kann von allen berechtigten Nutzern unmittelbar zur Optimierung und zur verbesserten Abstimmung der Angebotskonzepte genutzt werden.

Die Vorteile einer solchen Fahrplanabstimmungsplattform sind vielfältig:

- Der Prozess der Fahrplansynchronisierung über Teilnetze hinweg wird strukturiert. Der Versand von Konzepten als E-Mail-Anhang in wechselnden Formaten (Excel, PDF,…) entfällt. Stattdessen werden Planungsstände auf die Plattform hochgeladen, die auf dem VDV 452 Standarddatenformat aufbauen.

- Der Abgleich von regionalen Teilfahrplänen im Hinblick auf ihre „Passgenauigkeit“ an Anschlusspunkten wird durch die hinterlegten Anschlussqualitätsmodelle drastisch vereinfacht und ist mit besserer Qualität möglich. Dies minimiert die Gefahr, dass etwas übersehen wird.

- Die Kommunikation der Verkehrsplaner untereinander und mit den Genehmigungsstellen erfolgt über die Plattform. Sie beinhaltet eine Funktion um Bearbeitungsvermerke und Kommentare an Anschlüsse zu heften und ausgewählten Partnern sichtbar zu machen.

- Über das Rechtemanagement der Plattform kann fein gesteuert werden, wer welche Planungsstände und Daten einsehen kann.

- Die Plattform leistet eine objektive Dokumentation des Abstimmungsprozesses. Später auftretende Unstimmigkeiten oder gar negative Presse über die Anschlussqualität müssen nicht zum Streit führen, da auf Basis der Plattform objektiv geklärt werden kann, „wie es dazu kommen konnte“.

- Das Zeitfenster für eine gute Abstimmung der dezentral entwickelten Angebotskonzepte wird durch die Nutzung der Plattform in vielen Fällen deutlich verlängert. Ein Austausch über Konzepte ist schon möglich, wenn diese erst zu 80 oder 90 Prozent stabil sind, da der Aufwand zur Prüfung und Bewertung solcher Konzepte durch die Plattform verkleinert wird.

Bild 6: Beispiel des zeitlichen Verlaufs im jährlichen Fahrplan-Fortschreibungsprozess mit zwei Fahrplanwechseln. Mit der Fahrplanabstimmungsplattform lassen sich schon früh im Prozess Konzepte austauschen und mit minimalem Aufwand hinsichtlich der Anschlussqualität bewerten.

Derzeit existiert eine prototypische Implementierung der Fahrplanabstimmungsplattform („SynPlan-Plattform“). Sie baut auf dem Versionsverwaltungssystem Subversion auf wodurch der Entwicklungsaufwand für Rechtemanagement und Versionierung von Daten minimiert werden konnte.

Das Hochladen von Angebotskonzepten auf die Plattform soll so einfach wie möglich gestaltet werden. Letztlich soll es nicht mehr Aufwand verursachen, als der Versand eines Konzepts per E-Mail. Die Plattform speichert die Fahrplandaten im VDV-Standardformat. Darüber hinaus „versteht“ die Plattform Konzepte im Excel-Format, wenn diese gewissen Formatierungsregeln entsprechen.

6 Zusammenfassung und Ausblick

Die Arbeit erweitert die auf der Heureka ´08 (siehe [5]) vorgestellten Konzepte und Ergebnisse zur Fahrplanabstimmung in Verkehrsverbünden. Neben der Modellierung der Problemstellung stellen wir Optimierungskonzepte vor, die Metaheuristiken und eine mathematische Formulierung als Quadratisches Semi-Assignment Problem beinhalten. Diese Konzepte kombinieren schnelle Verfahren zur Lösungsgenerierung und neue Techniken zum Abschätzen der Lösungsqualität.

Neben der reinen Verbesserung der Anschlussqualität stellen wir auch einen Ansatz vor, der die Umlaufplanung für die Fahrzeuge berücksichtigt. Dies ist ein wichtiger Punkt für die Fahrplansynchronisierung, da zusätzlich benötigte Fahrzeuge häufig ein Ausschlusskriterium für neu entwickelte Fahrpläne sind.

Das Konzept wird im Fraunhofer-Projekt „SynPlan“ entwickelt und als Softwaretool umgesetzt. Durch die Entwicklung der SynPlan-Plattform können die verschiedenen, in den Planungsprozess einbezogenen Unternehmen gemeinsam an einem besser abgestimmten Gesamtfahrplan arbeiten.

7 Literatur

[1]    DOMSCHKE, W. (1989). Schedule synchronization for public transit networks. OR Spektrum 11, 17-24.

[2]    FLEURENT, CH.; LESSARD, R.; SÉGUIN, L. (2004). Transit timetable synchronization: evaluation and optimization. 9th International Conference on Computer Aided Scheduling in Public Transport.

[3]    KLEMT, W.: STEMME. W. (1988). Schedule synchronization for public transit networks. In: J.R. Daduna, A. Wren (eds.), Computer-aided transit scheduling, Proceedings, Lect. Notes Econ. Math. Syst. 308, 327-335.

[4]    VOSS, S. (1992). Network design formulations in schedule synchronization. In: M. Desrochers et al. (eds.), Computer-aided transit scheduling, Proceedings, Lect. Notes Econ. Math. Syst. 386, 137-152.

[5]    SCHRÖDER, M.; SCHÜLE, I. (2008). Interaktive mehrkriterielle Optimierung für die regionale Fahrplanabstimmung in Verkehrsverbünden. Straßenverkehrstechnik, (6), 332-340.

[6]    SCHÜLE, I.; DRAGAN, A.; RADEV, A.; SCHRÖDER, M.; KÜFER, K.-H. (2008). Multicriteria optimization for regional timetable synchronization in public transport. Operations Research Proceedings 2008, 313-318, Springer Verlag.

[7]    SCHÜLE, I. (2010). RLT Approaches to QSAPs – Applied to Timetable Synchronization in Public Transport, Dissertation an der TU Kaiserslautern, Logos Verlag.

[8]    KLIEWER, N. (2005). Optimierung des Fahrzeugeinsatzes im öffentlichen Personennahverkehr: Modelle, Methoden und praktische Anwendungen, Dissertation an der Universität Paderborn.

[9]    HANSEN, N. (2009). Integrating Timetabling And Vehicle Scheduling, Diplomarbeit an der TU Kaiserslautern.