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.

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 f_l 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 ℒ₀ bezeichnet werden. Linienauswahlverfahren wählen dann eine Teilmenge der Linien L ⊆ ℒ₀ 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 G_i = (V_i, E_i) eines betrachteten Verkehrsmittels i. V_i repräsentiert die Menge aller Haltestellen, E_i 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^′ = (V_i, E^′) mit E^′ ⊆ E_i erstellt. Dazu wird der Streckenwiderstand iterativ bestimmt und darauf basierend eine Bestwegumlegung durchgeführt: Anhand der Streckenbelastung q_k der k.-Iteration wird die Widerstandsfunktion r(q_k) 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

G_i = (V_i, E_i) eines betrachteten Verkehrsmittels i sowie eine Bemessungsmatrix, die Gewichte w_uv für jede Nachfragerelation (u, v) enthält, mit u, v ∈ V_i. Dazu soll ein Liniennetz L_i = (V_i, E_Li) erstellt werden mit E_Li ⊆ E_i, so dass in L_i für jeden Pfad p_uv 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 L_i 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 L_i überprüft. Falls zwischen den Knoten der Relation kein Pfad in L_i existiert oder die Nebenbedingungen verletzt sind, wird ℒ um eine neue Linie erweitert und die zusätzlichen Kanten in L_i 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 G_i oder G_i′. 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