FGSV-Nr. FGSV 002/127
Ort online-Konferenz
Datum 13.04.2021
Titel Kombination von Linienkonstruktions- und Linienauswahlverfahren für die Liniennetzplanung
Autoren Univ.-Prof. Dr.-Ing. Markus Friedrich, M. Sc. Maximilian Hartl, Dr. Alexander Schiewe, Prof. Dr. Anita Schöbel, M.Sc. Magdalena Schilling
Kategorien HEUREKA
Einleitung

Ergebnisse der DFG Forschergruppe „Integrierte Planung im öffentlichen Verkehr“ zeigen, dass algorithmische Lösungen für die automatisierte Erstellung eines ÖV-Angebots durch die Integration planerischer Regeln verbessert werden können. Das Verbesserungspotenzial betrifft besonders die Liniennetzplanung. Bei der Liniennetzplanung kann die Erstellung eines Linienkonzepts in zwei Schritte unterteilt werden. Ein Linienkonstruktionsverfahren generiert eine Menge an potenziellen Linien, die als Linienpool bezeichnet werden. Linienauswahlverfahren wählen dann eine Teilmenge der Linien für das Linienkonzept so aus, dass eine Zielfunktion optimiert und Nebenbedingungen eingehalten werden. Ein Linienkonzept kann damit nur so gut werden wie der Linienpool potenzielle Linien bereitstellt. Ausgehend von dieser Tatsache wird gezeigt, dass bereits einfache Linienkonstruktionsverfahren den Linienpool sinnvoll erweitern und das Ergebnis einer automatisierten ÖV-Angebotsplanung verbessern können. Dazu wird wie folgt vorgegangen: (1) Es wird ein einfaches Linienkonstruktionsverfahren entwickelt. (2) Für den Test des Verfahrens werden drei Demonstratoren genutzt. Ein Demonstrator besteht aus einem Verkehrswegenetz und einer Nachfragestruktur. (3) Mit dem Linienkonstruktionsverfahren werden Linienkonzepte für die Demonstratoren erzeugt und mit bereits verfügbaren Lösungen verglichen. (4) Alle Demonstratoren und dessen Lösungen sind zur Nachvollziehbarkeit in einem Repository auf GitHub [1] verfügbar.

PDF
Volltext

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

1 Einleitung

Die Planung eines ÖV-Angebots ist eine komplexe Aufgabe. Sie umfasst die Planung des Liniennetzes mit den Haltestellen und Linienwegen, die Fahrplanung, die Fahrzeugumlaufplanung und die Dienstplanung. Die einzelnen Stufen werden dabei heute in der Regel sequentiell bearbeitet, wobei das Ergebnis der vorhergehenden Stufe den Input für die jeweils nachfolgende Stufe liefert. Dabei ist auffällig, dass Optimierungsverfahren in unterschiedlichem Umfang eingesetzt werden:

∙ Die Liniennetzplanung ist eine Aufgabe der Verkehrsplanung. In dieser Planungsstufe werden die Liniennetze und die Takte der Linien festgelegt. Stand der Praxis sind rechnergestützte Entwurfsverfahren [2–4]. Dabei entwirft der Planer oder die Planerin eine begrenzte Anzahl von Lösungen und berechnet ihre Wirkungen mit detaillierten Verkehrsnachfragemodellen. Für die Liniennetzplanung existiert eine Reihe von Optimierungsverfahren, die aber in der Planungspraxis nur in Ausnahmefällen eingesetzt werden [5]. Eine mögliche Erklärung hierfür ist, dass sich planerische und algorithmische Lösungen bisher deutlich unterscheiden. Liniennetze lassen sich gut in Karten visualisieren. Menschen mit Planungserfahrung verfügen womöglich über besondere Fähigkeiten mit Hilfe von Karten kreative Lösungen für Liniennetze zu erzeugen und die Wirksamkeit der Lösung implizit abzuschätzen. Da die Nutzer der Liniennetze ebenfalls Menschen sind, verstehen Fahrgäste von Menschen erzeugte Pläne möglicherweise besser als algorithmische Lösungen.

∙ Die Fahrplanung legt die genauen Abfahrtszeiten der Fahrplanfahrten fest und bestimmt damit die Umsteigewartezeiten der Fahrgäste und die Fixpunkte der nachfolgenden Einsatzplanung. Die Fahrplanung kann sowohl Teil der Verkehrsplanung als auch Teil der Betriebsplanung sein. Die Anpassung von Fahrplänen mit dem Ziel einer Anschluss- und Umlaufoptimierung ist für Menschen eine schwierige Aufgabe, da sich die Fahrplandaten mehrere Linien nur in besonderen Fällen – z.B. bei Taktfahrplänen [6] – in einer Karte visualisieren lassen [7,p.2649,8]. Optimierungsverfahren [9,10] sollten bessere Ergebnisse erzielen als planerische Lösungen. Allerdings ist auch bei der Fahrplanung die rechnergestützte Planung Stand der Praxis.

∙ Die Einsatzplanung ist Teil der Betriebsplanung. Sie ermittelt die Fahrzeugumläufe und die Dienstpläne des Fahrpersonals, die dann Grundlage für Turnuspläne und die Personaldisposition sind. In der Einsatzplanung werden bereits seit den 1970er Jahren Optimierungsverfahren eingesetzt [5,11–13]. Sie haben sich in der Planungspraxis etabliert.

Ergebnisse der DFG Forschergruppe „Integrierte Planung im öffentlichen Verkehr“ [14,15] zeigen, dass algorithmische Lösungen durch die Integration planerischer Regeln verbessert werden können [16–18]. Das Verbesserungspotenzial betrifft besonders die Liniennetzplanung. Aufgabe der Liniennetzplanung ist die Erstellung eines Linienkonzepts (ℒ, f), das eine Menge von Linien l ∈ ℒ mit den zugehörigen Frequenzen fl umfasst [19]. Bei der automatisierten Liniennetzplanung wird häufig die Erstellung eines Linienkonzepts in zwei Schritte unterteilt, die sequentiell oder simultan durchgeführt werden: Ein Linienkonstruktionsverfahren generiert eine Menge an potenziellen Linien, die als Linienpool ℒ0 bezeichnet werden. Linienauswahlverfahren wählen dann eine Teilmenge der Linien L ⊆ ℒ0 für das Linienkonzept so aus, dass eine Zielfunktion optimiert und Nebenbedingungen eingehalten werden. Ein Linienkonzept kann damit nur so gut werden wie der Linienpool potenzielle Linien bereitstellt.

Ausgehend von dieser Tatsache will der vorliegende Beitrag zeigen, dass bereits einfache Linienkonstruktionsverfahren den Linienpool sinnvoll erweitern und das Ergebnis einer automatisierten ÖV-Angebotsplanung verbessern können. Dazu wird wie folgt vorgegangen:

∙ Es wird ein einfaches Linienkonstruktionsverfahren entwickelt (Kapitel 3).

∙ Für den Test des Verfahrens werden drei Demonstratoren genutzt. Ein Demonstrator besteht aus einem Verkehrswegenetz und einer Nachfragestruktur (Kapitel 4).

∙ Mit dem Linienkonstruktionsverfahren werden Linienkonzepte für die Demonstratoren erzeugt und mit bereits verfügbaren Lösungen aus [1] verglichen (Kapitel 5).

2 Optimierungsverfahren für Linienkonzepte

Der Lösungsraum für Linienkonzepte ist groß. Das ist bereits in einem einfachen 2x2 Rasternetz mit 4 Haltestellen und 4 Strecken erkennbar. Für dieses Verkehrswegenetz ergeben sich 17 mögliche Linien, die in Bild 1 dargestellt sind. Jede der Linien deckt das Wegenetz teilweise oder komplett ab. Aus der Kombination der Linien können 217 = 131.072 Linienkombinationen erstellt werden. Einige der Kombinationen liefern allerdings ein ungültiges Linienkonzept, da nicht alle Quelle-Ziel-Relationen bedient werden. Mit jeder Haltestelle steigt die Kombinationsmöglichkeit exponentiell an. Jedes Optimierungsverfahren muss deshalb in realen Anwendungen den Lösungsraum durch gewisse Annahmen einschränken. Dies geschieht meist ohne Kenntnis, ob die optimale Lösung dadurch ausgeschlossen wird. Deshalb können automatisierte Verfahren der Liniennetzplanung oft kein optimales Linienkonzept garantieren und stellen daher eine Heuristik dar.

Bild 1: Alle Linienkombinationsmöglichkeiten bei einem 2x2 Rasternetz

Algorithmen zur Erzeugung eines Linienkonzepts lassen sich entsprechend ihren Eigenschaften auf verschiedene Weise klassifizieren. Ein mögliches Klassifizierungsmerkmal ist die Art der Linienweggenerierung. Mit diesem Merkmal lassen sich Linienkonstruktionsalgorithmen und Linienauswahlalgorithmen unterscheiden.

Algorithmen aus der Klasse der Linienkonstruktionsalgorithmen beginnen mit einem leeren Verkehrswegenetz. Sie erzeugen Linien nach gewissen Regeln und bewerten die Linien mit einer Zielfunktion. Ein früher Ansatz dieser Klasse ist das Reduktionsverfahren [20]. Es geht von einem Maximalnetz aus bei dem alle Strecken befahren werden können und verringert die Anzahl der befahrbaren Strecken schrittweise. Mit Hilfe eines Entscheidungsbaumverfahrens wird das Liniennetz abgeleitet. Das Gegenstück zum Reduktionsverfahren bildet das Progressivverfahren [21]. Es geht von der Strecke im Netz mit der höchsten Belastung aus und propagiert sich entlang der Nachfrageströme. Zielkriterium für die Umsetzung ist die minimale Reisezeit bei einer maximalen Direktfahreranzahl. Einen anderen Ansatz verfolgt das Verkehrsstromverfahren [22,23]. Durch die Suche von Streckenfolgen zwischen allen potenziellen Endhaltestellen wird ein Linienpool ermittelt. Jede Linie wird anhand des Direktfahreranteils und der erforderlichen Fahrzeugzahl bewertet und dann sequentiell als Teil des Linienkonzepts übernommen [23,24]. [25] nutzt ebenfalls Endhaltestellen für die Erzeugung von Linienwegen, die er mit "nearly shortest routes" verbindet. Bei der Auswahl der Linien berücksichtigt er die komplette Reisekette und verbindet oder verwirft Linien mittels eines Ameisenalgorithmus [26]. Das Problem der Linienplanung wird in [27] als Mehrgüterflussverfahren formuliert. Kombiniert wird dabei die Tatsache, dass der Reiseweg von Fahrgästen und der Verlauf von Linien miteinander verknüpft sind. Dazu wird eine Routenwahl sowie die die freie Liniengenerierung nach gegebenen Regeln unterstellt und ein Ansatz zur Spaltenerzeugung verwendet. Ein erweiterter algorithmischen Ansatz ist in [28] zu finden, der iterativ Spannbäume zur Abdeckung der Nachfrage nutzt. Der agentenbasierten Ansatz [29] nutzt die dynamische Reaktion der Nachfrage, um Linien zu entwerfen. Es versucht den finanziellen Gewinn zu maximieren, woraus sich ein dünnes ÖV-Angebot mit einer hohen Taktfolge ableiten lässt.

Algorithmen aus der Klasse der Linienauswahlverfahren werden in [19] beschrieben. Sie nutzen als Input einen gegebenen Linienpool. Durch die Steigerung der Leistungsfähigkeit von Solvern [30,31] können komplexere Modelle gelöst werden. Dadurch gehen aktuelle Entwicklungen dahin, mehrere Planungsschritte integriert zu lösen.

Neueste Problemformulierungen beziehen sich deshalb auf die integrierte Planung [32–34], die Behandlung von Verspätungen [35] oder Robustheitsaspekte [36–39]. [13] modellieren anhand eines Branch & Bound Ansatzes das Linienplanungsproblem als ganzzahliges Optimierungsproblem (IP), während [40] eine Linearisierung verwendet und sowohl Kosten als auch Direktfahrer berücksichtigt. In [41] wird das Linienkonzept anhand eines Change & Go Netzwerks mittels Dekompositionstechnik und der LP-Relaxation des IP-Problems berechnet. [42] ermittelt ein Systemoptimum, bei dem die Reisezeiten für einzelne Fahrgäste schlechter ausfallen, um die Kosten zu reduzieren.

3 Ein Linienkonstruktionsverfahren

Im Folgenden wird ein einfaches Linienkonstruktionsverfahren vorgestellt. Das Verfahren soll folgende Anforderungen erfüllen:

∙ Es soll eine Menge von Linien generieren, die zusammen ein zulässiges Linienkonzept ergeben. Ein Linienkonzept ist zulässig, wenn alle Fahrtwünsche der Fahrgäste unter Berücksichtigung der Kapazität bedient werden können.

∙ Das Linienkonzept soll Linien für die in LinTim [43] implementierten Linienauswahlverfahren bereitstellen.

Das Linienkonstruktionsverfahren umfasst mehrere Module, die in Bild 2 dargestellt sind. Jedes Modul liefert Ergebnisse, die von den Planenden durch die Vorgabe von Parametern beeinflusst werden können:

∙ Das Modul „Ermittlung Streckennetz“ definiert die Teilmenge des Wegenetzes, das von Linien befahren werden kann.

∙ Das Modul „Erzeugung Liniennetz“ bestimmt die Menge der Linien.

∙ Das Modul „Ermittlung Linienkonzept“ legt für jede Linie eine Frequenz fest.

Ausgangspunkt ist ein Graph Gi = (Vi, Ei) eines betrachteten Verkehrsmittels i. Vi repräsentiert die Menge aller Haltestellen, Ei die Menge aller gerichteten Verbindungen zwischen den Haltestellen. Der heuristische Ansatz zur Erstellung eines Liniennetzes basiert auf der sequentiellen Bearbeitung von Quelle-Ziel-Relationen. Die Reihenfolge der Bearbeitung kann durch den Planenden durch die Definition von relationsbezogenen Gewichten festgelegt werden. Neben der Verkehrsnachfrage eignet sich auch die Reisezeit oder der Reisezeitaufwand (Nachfrage ´ Zeit) oder Verbindungsfunktionsstufen (RIN [44]) als Gewicht für die Sortierung. So können beispielsweise für nachfragestarke Quelle-Ziel-Beziehung direkte Linien gebildet werden. Nachfrageschwächere Relationen werden anschließend über Zubringerlinien bedient. Die Gewichte für das gewählte Sortierkriterium werden in einer sogenannten Bemessungsmatrix gespeichert.

Das entwickelte Verfahren agiert nach keinem übergeordneten Ziel im Sinne der klassischen Optimierung unter der Vorgabe einer Zielfunktion. Es arbeitet nach vorgegebenen Regeln die in der Bemessungsmatrix beschriebene Nachfragestruktur ab, bis ein Abbruchkriterium erreicht ist.

Bild 2: Überblick über modularisierten Aufbau

3.1 Ermittlung Streckennetz

Die Verwendung einer Teilmenge des Streckennetzes reduziert die Komplexität bei dem Erstellen des Liniennetzes. Hierfür wird ein Reduktionsverfahren genutzt, das durch die Bündelung der Nachfrage einen Subgraphen G = (Vi, E) mit EEi erstellt. Dazu wird der Streckenwiderstand iterativ bestimmt und darauf basierend eine Bestwegumlegung durchgeführt: Anhand der Streckenbelastung qk der k.-Iteration wird die Widerstandsfunktion r(qk) ausgewertet, die eine Eingangsgröße der k + 1.-Iteration ist. Eine hohe Belastung führt zu einem geringen Widerstand, Strecken mit geringer Belastung werden bestraft. Die Belastung einer Strecke als Ergebnis der Umlegung ist damit abhängig von vorherigen Ergebnissen. Über eine Dämpfungsfunktion wie beispielsweise der Method of Succesive Averages (MSA) werden die Änderungen der Streckenbelastungen zwischen zwei Iterationsschritten reduziert, was die Konvergenzbildung im Untersuchungsgebiet beschleunigt. Das Verfahren bricht ab, wenn entweder die maximale Anzahl an Iterationsschritten erreicht ist, oder die Änderung der Streckenbelastungen zwischen zwei Iterationsschritten unter einen angegebenen Grenzwert fällt. Bei den Ergebnissen aus Kapitel 5 wird eine treppenähnliche Funktion zur Anpassung der Streckenwiderstände verwendet.

Basierend auf den konvergierten Belastungen, werden den Strecken Gewichte zugeordnet. Für Strecken, die ein vorgegebenes Kriterium nicht erfüllen, wird nach aufsteigender Gewichtung eine Sperrung für das betrachtete Verkehrsmittel geprüft. Dabei muss gewährleistet sein, dass kein Knoten im Netz isoliert wird. Deshalb wird untersucht, ob das Streckennetz durch das Entfernen von Strecken weiterhin zusammenhängend ist. Nur dann wird der Graph sukzessive reduziert. Mit jeder Reduktion sinkt die Wahrscheinlichkeit, dass das Entfernen einer weiteren Strecke die Zulässigkeit erfüllt. Die Reihenfolge der Betrachtung der Strecken ist damit implizit relevant für die Entscheidung über die Sperrung der Strecke.

3.2 Erzeugung Liniennetz

Das Problem der Liniennetzerstellung ist wie folgt definiert: Gegeben sei das Streckennetz

Gi = (Vi, Ei) eines betrachteten Verkehrsmittels i sowie eine Bemessungsmatrix, die Gewichte wuv für jede Nachfragerelation (u, v) enthält, mit u, v Vi. Dazu soll ein Liniennetz Li = (Vi, ELi) erstellt werden mit ELi Ei, so dass in Li für jeden Pfad puv vorgegebene Nebenbedingungen erfüllt sind. Die Menge der Linien sei ℒ, dabei ist eine Linie l ∈ ℒ eine Folge benachbarter Kanten.

Bild 3 zeigt die Vorgehensweise des Linienkonstruktionsverfahren als vereinfachter Pseudocode. Zu Beginn werden Li als leerer Graph sowie ℒ als leere Menge initialisiert und die Nachfragerelationen werden anhand ihrer Gewichte sortiert. Mit absteigender Priorität wird für jede Relation die Existenz einer gültigen Verbindung in Li überprüft. Falls zwischen den Knoten der Relation kein Pfad in Li existiert oder die Nebenbedingungen verletzt sind, wird ℒ um eine neue Linie erweitert und die zusätzlichen Kanten in Li ergänzt. Die neue Linie entspricht dem Bestweg bezüglich des vorgegebenen Streckenwiderstands zwischen den beiden Knoten. Die Vorgabe des Streckenwiderstands ist damit eine wichtige Möglichkeit des Planers, den Verlauf der Linien zu beeinflussen.

Eine Nebenbedingung kann beispielsweise sein, dass eine vorgegebene, maximale Umsteigehäufigkeit nicht überschritten werden darf. Beim Hinzufügen einer neuen Linie wird überprüft, ob diese mit bestehenden Linien verknüpft werden kann. Linien, deren Knoten eine Teilmenge der Knoten der einzufügenden Linie sind, werden gelöscht. Die Schleife über die Nachfragerelationen führt zu einem sukzessiven Aufbau des Liniennetzes. Eine Priorisierung der Relation erhöht die Wahrscheinlichkeit einer Direktverbindung zwischen dem untersuchten Knotenpaar.

Bild 3: Pseudocodedarstellung für die automatisierte Erzeugung von Linienmengen

Implementierte Verfahrensparameter, die vom Planenden gesetzt werden, sind der maximale Umwegfaktor sowie die maximale Umsteigehäufigkeit als Nebenbedingungen sowie der Streckenwiderstand bei der Bestwegsuche, die Priorisierung der Relationen und die Verwendung von Gi oder Gi′. Als weitere Option können Planende entscheiden, ob neue Linien mit bestehenden Linien verknüpft werden sollen, so wie es in Bild 4 (Iteration 2, 5, 6) beschrieben ist.

In Bild 4 wird beispielhaft für einen Parametersatz der Linienaufbau für die ersten Iterationsschritte dargestellt. Zur Veranschaulichung der Lösungsvielfalt sind in Bild 5 für unterschiedliche Demonstratoren und verschiedene Parametereinstellungen Liniennetze dargestellt. Die Lösungen auf der linken Seite erinnern eher an planerischen Lösungen, die sich durch wenige dicht getaktete Linienwege auszeichnen. Diese Lösungen ergeben sich mit Parametern, die die Umwegigkeit und die Umsteigehäufigkeit nur in geringem Umfang begrenzen. Die Lösungen auf der rechten Seite erinnern an algorithmische Lösungen, die immer dann viele direkte Linien mit geringer Frequenz erzeugen, wenn die Zielfunktion die Startwartezeit der Fahrgäste nicht berücksichtigt [16,17]. Um diese Lösungen zu erzeugen, werden die Parameter Umwegigkeit und Umsteigehäufigkeit begrenzt.

Bild 4: Beispielhafte Darstellung für den Aufbau eines Liniennetzes der ersten sechs Iterationsschritte

Bild 5: Verschiedene erzeugte Linienkonzepte für unterschiedliche Parametersätze

3.3 Ermittlung Linienkonzept

Formel und Erläuterung siehe PDF

3.4 Technische Anforderungen

Die Implementierung erfolgt in der Verkehrsplanungssoftware Visum [7], unterstützt durch eingebundene Skripte der Programmiersprache Python [45]. Es werden Funktionen der Python Bibliotheken NetworkX [46,47] sowie NumPy [48] verwendet. LinTim [43] stellt ein Softwarepaket für die Verwendung von Optimierungsverfahren.

Auf einem Desktop Computer (Prozessor: Intel® Core™ i7-5820K CPU @ 3.30GHz, Arbeitsspeicher: 64 GB, Betriebssystem: Microsoft Windows 10) beträgt die Rechenzeit für den Durchlauf der kompletten Prozesskette aus Bild 2 je nach Demonstrator und Parametereinstellung zwischen zehn Sekunden und einer Minute. Da auch nur einzelne Module durchgeführt werden können, kann sich die Rechenzeit pro Durchlauf verändern.

4 Demonstratoren

Für die nachfolgenden Demonstratoren soll das vorgestellte Linienkonstruktionsverfahren (LKV) ÖV-Angebote erstellen. Die generierten Lösungen werden mit bereits bekannten algorithmischen und planerischen Lösungen verglichen. Eine vollständige Beschreibung des zugrundeliegenden Datenmodells und der Konfiguration der Demonstratoren liefert [16]. Gleichzeitig werden die Daten auf GitHub [1] in verschiedenen Datenformaten zur Nutzung veröffentlicht. Alle Interessierten sind eingeladen, die Vielzahl an Lösungen zu erweitern und ihre Methoden mit den bisherigen Lösungen zu vergleichen.

Bild 6: Übersicht von Demonstratoren mit Darstellung der Nachfragesituation

In Bild 6 sind die verwendeten Untersuchungsgebiete dargestellt und um die Nachfrageverteilung erweitert. Die Demonstratoren überführen typische Planungssituationen in virtuelle Untersuchungsgebiete und haben folgende Ausprägungen:

∙ Monozentrale Stadt als Radialringwegenetz oder als aufgerastertes Stadtgebiet: ein öffentliches Verkehrssystem mit weitgehend gleichbleibenden Geschwindigkeiten auf dem Wegenetz, ein Fahrzeugtyp, Relationen mit hoher gebündelter und niedriger disperser Nachfrage.

∙ Polyzentrale Region: unterschiedliche Geschwindigkeiten, Relationen mit hoher gebündelter und niedriger disperser Nachfrage.

Jeder Demonstrator umfasst Daten zum Verkehrsangebot, Daten der Verkehrsnachfrage und Daten, die die Wirkungen auf die Fahrgäste (z. B. Reisezeiten) und die Betreiber (z. B. Kostendeckungsgrad) beschreiben. Die Nachfrage wird tageszeitabhängig abgebildet. Für die Liniennetzplanung wird im Folgenden jedoch nur die Nachfrage der morgendlichen Spitzenstunde herangezogen.

5 Anwendung des Verfahrens

In diesem Kapitel werden Lösungen mit dem beschriebenen Linienkonstruktionsverfahren erzeugt und mit bereits erzeugten Lösungen aus [1] verglichen. Für die Erzeugung wird der Wertebereich der einzelnen Parameter des Verfahrens variiert. Auf diese Weise ergeben sich für jeden Demonstrator ca. 100 Linienkonzepte als Lösungen. Für jedes Linienkonzept gibt es zwei Ausprägungen von Fahrplänen. Entweder wird der Fahrplan als eine Aneinanderreihung von Fahrten mit dem berechneten Linientakterstellt (LKV). Alternativ wird das Linienkonzept als Linienpool an LinTim für die optimierte Bestimmung eines Fahrplans übergeben (LKV+Lin- Tim). LinTim optimiert die Linienfrequenzen und die Abfahrtszeiten. Dabei wird eine Abschätzung der entstehenden Betriebskosten [19] sowie heuristisch die Umsteigezeiten minimiert [49]. Die Lösungen werden dann mit einer fahrplanbasierten Umlegung mit Mehrwegsuche ohne Kapazitätsbeschränkung und einer linienübergreifenden Umlaufbildung bewertet. Detailliert beschrieben wird die Umlegungs- und Kostenberechnung in [16].

Die Ergebnisse jeder Lösung werden anhand einer bikriteriellen Bewertung für die Kosten und die empfundene Reisezeit (ERZ) bewertet. Bild 7 zeigt die Ergebnisse für jeden Demonstrator. Dabei werden vier Arten von Lösungen unterschieden:

∙ Algorithmische Lösungen (A): Diese Lösungen wurden bereits mit LinTim ermittelt. Der Linienpool dieser Lösungen wurde mit unterschiedlichen Verfahren erzeugt.

∙ Planerische Lösungen (P): Diese Lösungen wurden von Planenden erstellt unter dem Einsatz von rechnergestützter Planungssoftware [7]. Damit bezieht sich der manuelle Entwurf insbesondere auf die Liniennetzplanung und Fahrplankoordination, während die Umlaufbildung algorithmisch gelöst wird.

∙ LKV: Lösungen des Linienkonstruktionsverfahrens ohne Fahrplanoptimierung.

∙ LKV+LinTim: Lösungen des Linienkonstruktionsverfahrens mit anschließender Linienauswahl und Fahrplanoptimierung durch LinTim.

Zusätzlich ist in Bild 7 eine approximierte Pareto-Front eingezeichnet, die die besten bisher bekannten Lösungen verbindet. Außerdem ist eine untere Schranke für die Kosten dargestellt, die mit der in [32] beschriebenen Methode bestimmt wurde. Diese Methode unterstellt ein systemoptimales Fahrgastverhalten.

Die Bewertung der erweiterten empfundenen Reisezeit wird anhand einer Fahrplanfeinen Umlegung ohne eine zusätzliche Bestrafung bei Kapazitätsüberschreitungen durchgeführt. Anschließend wird geprüft, ob die Kapazitätsbedingung eingehalten wird. Es werden nur Lösungen gezeigt, die die Kapazitätsbedingung einhalten. Alle Verfahrenseinstellungen können auf [1] nachvollzogen werden.

Die Lösungen zeigen für alle Demonstratoren ähnliche Eigenschaften. Die einfache Fahrplanerstellung für LKV-Lösungen ist aus betrieblicher Sicht meistens teurer als die optimierten Lösungen mit LKV+LinTim. Die einfache Frequenzermittlung und die fehlende Fahrplankoordinierung der LKV-Lösungen führen zu mehr Fahrplanfahrten und zu ineffizienten Umläufen. Dadurch steigen der Fahrzeugbedarf und die Kosten. LKV+LinTim-Lösungen sind dagegen meist kostengünstiger. Die Reduktion der Fahrplanfahrten auf einigen Linien kann allerdings zu einer etwas höheren mittleren Reisezeit gegenüber der nicht optimierten Fahrplanausprägung führen, da Umsteigevorgänge länger dauern können.

Bei vielen LKV+LinTim-Lösungen kann die Reisezeit nahezu gehalten werden und verdeutlicht die betrieblichen Optimierungsmöglichkeiten auf der Kostenseite.

Bild 7: Ergebnisse für die drei Demonstratoren

Der Ring-Demonstrator stellt in der Hinsicht eine Ausnahme dar. Die symmetrische Struktur erlaubt es dem Linienkonstruktionsverfahren bereits mit einem einfachen Fahrplan die bisher beste bekannte approximative Pareto-Front zu verschieben. In den anderen Demonstratoren führen LKV+LinTim-Lösungen mit optimierten Fahrplänen zu einer Anpassung der bisherigen Pareto-Front. Dies gilt insbesondere für die algorithmische Linienpoolauswahl mit dem Verfahren aus [41].

Bild 8 zeigt eine Auswahl von Lösungen, die mit planerischen Verfahren, mit algorithmischen Verfahren aus LinTim oder mit dem Linienkonstruktionsverfahren erzeugt wurden. Für jeden Demonstrator wird die kostenminimale Lösung und eine weitere Lösung mit einer niedrigen empfundenen Reisezeit dargestellt. Die Lösung mit einer niedrigen Reisezeit wurde aus der Menge der Lösungen ausgewählt, die die minimalen Kosten der unteren Schranke höchstens um den Faktor 3 überschreiten und nahe an der Pareto-Front liegen. Damit sind alle Lösungen „gute“ Lösungen, die mit Ausnahme der planerischen Lösung für den Ring-Demonstrator nicht von einer anderen dargestellten Lösung dominiert werden. Die Lösungen unterscheiden sich vor allem bei der Anzahl der Linien. Planerische Lösungen und die LKV-Lösungen bestehen aus wenigen Linien mit höheren Frequenzen, die algorithmischen Lösungen enthalten mehr Linien mit geringen Frequenzen. Die Unterschiede lassen sich bei den algorithmischen Lösungen durch die Vorgabe eines Systemtakts [18] reduzieren.

Bild 8: Auswahl an Lösungen

6 Fazit und Ausblick

Die Ergebnisse der Anwendungen zeigen, dass die Kombination eines Linienkonstruktionsverfahrens und eines Linienauswahlverfahrens zumindest für die drei Demonstratoren zu guten Lösungen bei der Liniennetzplanung führt. Dabei sind auch Lösungen enthalten, die die bisher bekannte Pareto-Front verbessern.

Das vorgestellte Linienkonstruktionsverfahren kann – mit Einschränkungen – als ein Verfahren interpretiert werden, das planerische Vorgehensweisen bei der Konstruktion von Linienwegen berücksichtigt. Es bildet – ähnlich wie Planende – Linienwege sequentiell nach vorgegeben Regeln und beginnt dabei mit wichtigen Relationen.

Das Linienkonstruktionsverfahren liefert bereits ohne Erweiterung zulässige Lösungen, die alle Fahrtwünsche der Fahrgäste bedienen. Durch den Einsatz der Softwarebibliothek LinTim können die Linienkonzepte um einen optimierten Fahrplan ergänzt werden, der die Frequenzen und die Abfahrtszeiten optimiert. Dadurch reduzieren sich die betrieblichen Kosten gegenüber dem nicht optimierten Fahrplan im Schnitt um etwa 20 %. Die Reisezeiten werden durch die Fahrplanoptimierung kaum verändert, da der Anteil der Umsteiger relativ klein ist. Das liegt an der Größe der Netze und an der Tatsache, dass das Linienkonstruktionsverfahren für nachfragestarke Relationen direkte Linien einfügt.

Das Verfahren hat nicht den Anspruch ein fertiges ÖV-Angebot zur Verfügung stellen. Es ist als Ergänzungsmethode zu Linienauswahlverfahren zu sehen und soll eine Menge von Linien für den Linienpool bereitstellen, die planerischen Regeln genügt. Beispiele für solche Regeln sind:

∙ Linienwege sollen Wege nutzen auf denen sich die Nachfrage gut bündeln lässt. Das wird über das Modul „Ermittlung Streckennetz“ erreicht.

∙ Linienwege sollen einen maximalen Umwegfaktor nicht überschreiten. Das wird durch Regeln bei der Linienwegerstellung erreicht.

∙ Wichtige Relationen können bevorzugt werden. Wichtig kann sich dabei sowohl auf die Nachfrage oder den Reisezeitaufwand (Nachfrage ´ Zeit) beziehen, aber auch auf die Zentralität von Orten (Stadtteilzentrum - Stadtzentrum).

Das Verfahren hat eine Reihe leicht erkennbarer Schwächen:

∙ Das sequentielle Vorgehen kann zu Linienwegen führen, die für das gesamte System nicht sinnvoll sind. Das ermittelte Liniennetz ist statisch. In Verbindung mit einen Linienauswahlverfahren wird diese Schwäche kompensiert, da eine Linie nicht ausgewählt werden muss.

∙ Das sequentielle Vorgehen erfolgt auf der Ebene der Relationen. Diese Auflösung erscheint für die Liniennetzplanung zu fein. Eine Alternative könnte die Bildung von Teillinien sein, die benachbarte Haltestellen zusammenfasst, die mit einer hohen Wahrscheinlichkeit von der gleichen Linie bedient werden.

∙ Die planerische Vorgehensweise, kleine Siedlungen, die etwas außerhalb einer Verkehrsachse liegen, durch gewisse Umwegfahrten zu erschließen, erfordert entweder eine modifizierte Wegesuche oder das Aufbrechen bereits existierenden Linienwege.

∙ Der planerische Ansatz, bestehende Linienäste mit anderen Linien zu kombinieren, erfordert ebenfalls eine Erweiterung.

Die Ergebnisse zeigen jedenfalls, dass es für die Optimierung von Liniennetzen sinnvoll ist, in Linienkonstruktionsverfahren zu investieren. Dazu sollten bereits verfügbare Verfahren auf ihre Brauchbarkeit untersucht und neue Verfahren entwickelt werden.

7 Literatur 

[1] FOR2083. FOR2083\PublicTransportNetworks: Integrated planning in public transport [Internet] [cited 2019 Jan 16]. Available from: https://github.com/FOR2083/PublicTransportNetworks.

[2] Krug S. Ein interaktives Programmsystem zur Angebotsplanung für den liniengebundenen öffentlichen Personennahverkehr. Dissertation: Veröffentlichungen des Instituts für Stadtbauwesen, Heft 44; 1987.

[3] Friedrich M. Entwurfsverfahren für den ÖPNV im ländlichen Raum. Dissertation: Schriftenreihe des Lehrstuhls für Verkehrs- und Stadtplanung, Heft 5; 1994.

[4] Kirchhoff P. Städtische Verkehrsplanung: Konzepte, Verfahren, Maßnahmen. Wiesbaden: Vieweg+Teubner Verlag; 2002.

[5] Borndörfer R, Karbstein M, Egerer A, et al. Optimierung des Liniennetzes in Karlsruhe. Der Nahverkehr; 2019. (Heft 1+2).

[6] Liebchen C. Fahrplanoptimierung im Personenverkehr - muss es immer ITF sein? ETR - Eisenbahntechnische Rundschau. 2005.

[7] PTV AG. Visum 18: Handbuch. Karlsruhe; 2018.

[8] Liebchen C. Der Berliner U-Bahn Fahrplan 2005 – Realisierung eines mathematisch optimierten Angebotskonzeptes. Heureka Tagungsband S. 483-499; 2005.

[9] Nachtigall K, Opitz J. Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations. ATMOS; 2008.

[10] Liebchen C. Periodic Timetable Optimization in Public Transport. In: Waldmann K-H, Stocker UM, editors Operations research proceedings: Selected papers of the Annual International Conference of the German Operations Research Society (GOR), jointly organized with the Austrian Society of Operations Research (OGOR) and the Swiss Society of Operations Research (SVOR); 2007; p. 29–36.

[11] Caimi G, Kroon L, Liebchen C. Models for railway timetable optimization: Applicability and applications in practice. Journal of Rail Transport Planning & Management. 2017;6:285–312.

[12] Bunte S, Kliewer N. An overview on vehicle scheduling models. 2009;1. DOI: 10.1007/s12469-010-0018-5.

[13] Borndörfer R, Grötschel M, Jaeger U. Planung von öffentlichem Personenverkehr [Internet]. 127th edn. Springer; 2008. Available from: https://www.zib.de/groetschel/pubnew/paper/borndoerfergroetscheljaeger2008.pdf.

[14] FOR2083. DFG - Forschungsgruppe 2083: Integrierte Planung im öffentlichen Verkehr [Internet] [cited 2019 Jan 15]. Available from: https://for2083.math.uni-goettingen.de/.

[15] FOR2083. Integrierte Planung im öffentlichen Verkehr: Fortsetzungsantrag [Internet] [cited 2019 Jan 30]. Available from: http://gepris.dfg.de/gepris/projekt/238487308.

[16] Hartl M. Integrierte ÖV-Planung – Vergleich, Entwurf und Bewertung von planerischen und algorithmischen Lösungsverfahren. Stuttgart; 2019. (Promotion, noch nicht veröffentlicht).

[17] Friedrich M, Hartl M, Schiewe A, et al. Angebotsplanung im öffentlichen Verkehr - planerische und algorithmische Lösungen. Heureka. 2017.

[18] Friedrich M, Hartl M, Schiewe A, et al. System Headways in Line Planning. CASPT; 2018.

[19] Schöbel A. Line planning in public transportation: models and methods. OR Spectrum. 2012;34:491–510.

[20] Hüttmann R. Planungsmodell zur Entwicklung von Nahverkehrsnetzen liniengebundener Verkehrsmittel. Universität Hannover; 1979.

[21] Simonis K. Die nachfrageorientierte Optimierung von Omnibuslinien im Stadtbereich durch Verknüpfung von Teilstrecken nach unterschiedlichen Modellansätzen. (Stadt, Region, Land B, Berichte; vol. 26). Aachen: RWTH; 1981.

[22] Sonntag H. Ein heuristisches Verfahren zum Entwurf nachfrageorientierter Linienführung im öffentlichen Personennahverkehr. Zeitschrift für Operations Research. 1979;23:B15-B31.

[23] Wiedemann R, Bosserhoff D, Sahling B-M, et al. Linienplanung im öffentlichen Personenverkehr. 81st edn. Karlsruhe; 1981. (Institutsnotiz Nr. 29).

[24] Mott P, Sparmann U. Interaktive Liniennetzplanung im praktischen Einsatz: Ein neues zukunftsorientiertes Liniennetz für Mannheim und Ludwigshafen. Der Nahverkehr; 1983. (Heft 6).

[25] Alt B. Investigation of space-time structures in public transport networks and their optimization. ETH Zurich; 2010.

[26] Dorigo M, Stützle T. Handbook of Metaheuristics: Chapter 9: The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances. 47th edn. Boston; 2003.

[27] Borndörfer R, Grötschel M, Pfetsch ME. A Column-Generation Approach to Line Planning in Public Transport. Transportation Science [Internet]. 2007;41:123–132. Available from: https://pdfs.semanticscholar.org/586b/a7bc48e33773ac671e8a553ec2b9ea479b5a.pdf.

[28] Gattermann P, Harbering J, Schöbel A. Line pool generation. Public Transport. 2017;9:7–32.

[29] Manser P, Hörl S, Becker H, et al. Evolutionary modeling of large-scale public transport networks [Internet]. Zürich; 2017. Available from: https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/193148/ab1293.pdf?sequence=2&isAllowed=y.

[30] Plato. Decison Tree for Optimization Software [Internet] [cited 2019 Feb 14]. Available from: http://plato.asu.edu/guide.html.

[31] NEOS. NEOS Server for Optimization [Internet] [cited 2019 Feb 14]. Available from: https://neos-server.org/neos/.

[32] Pätzold J, Schiewe A, Schöbel A. Cost-Minimal Public Transport Planning. ATMOS; 2018.

[33] Pätzold J, Schiewe A, Schiewe P, et al. Look-Ahead Approaches for Integrated Planning in Public Transportation. ATMOS; 2017.

[34] Schöbel A. An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation. Transportation Research Part C: Emerging Technologies. 2017;74:348–365.

[35] Dollevoet T, Huisman D, Schmidt M, et al. Delay Management with Rerouting of Passengers. Transportation Science. 2012;46:74–89.

[36] Friedrich M, Müller-Hannemann M, Rückert R, et al. Robustness Tests for Public Transport Planning. ATMOS; 2017.

[37] Friedrich M, Müller-Hannemann M, Rückert R, et al. Robustness as a Third Dimension for Evaluating Public Transport Plans. ATMOS; 2018.

[38] Goerigk M, Schöbel A. Recovery-to-optimality: A new two-stage approach to robustness with an application to aperiodic timetabling. Computers & Operations Research. 2014;52:1–15.

[39] Lusby RM, Larsen J, Bull S. A survey on robustness in railway planning. European Journal of Operational Research. 2018;266:1–15.

[40] Bussieck M. Optimal Lines in Public Rail Transport. Braunschweig,; 1998.

[41] Schöbel A, Scholl S. Line Planning with Minimal Traveling Time. ATMOS; 2006.

[42] Borndörfer R, Neumann M, Pfetsch M. Angebotsplanung im öffentlichen Nahverkehr. Berlin; 2008. (ZIB-Report 08-04 (Januar 2008)).

[43] LinTim. LinTim-Integrated Optimization in Public Transportation [Internet] [cited 2019 Jan 8]. Available from: http://lintim.math.uni-goettingen.de/.

[44] RIN. Richtlinie für integrierte Netzgestaltung. FGSV; 2008.

[45] Python 2.7.16 documentation [Internet] [cited 2019 Jun 17]. Available from: https://docs.python.org/2.7/.

[46] Aric A. Hagberg, Daniel A. Schult, Pieter J. Swart. Exploring Network Structure, Dynamics, and Function using NetworkX. In: Gaël Varoquaux, Travis Vaught, Jarrod Millman, editors Proceedings of the 7th Python in Science Conference; 2008; p. 11–15.

[47] Hagberg A, Schult D, Swart P. Exploring network structure, dynamics, and function using NetworkX: NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks. [Internet] [cited 2019 Jun 17]. Available from: https://networkx.github.io/documentation/stable/.

[48] NumPy [Internet] [cited 2019 Jan 29]. Available from: http://www.numpy.org/.

[49] Pätzold J, Schöbel A. A Matching Approach for Periodic Timetabling. ATMOS; 2016.