Kurzfassung

Ergebnisse der DFG-Forschungsgruppe 2083 „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. In diesem Beitrag wird dargestellt, dass die dabei entstandenen Optimierungsverfahren für die ÖV-Planung in der Praxis eingesetzt werden können. Dazu werden die Eingangsdaten des Verkehrswegenetzes vereinfacht, um einerseits die Problemgrößen für die Algorithmen zu reduzieren und andererseits Ergebnisse erzeugen zu können, die planerischen Vorstellungen an die Gestalt der Linien besser entsprechen. Die Vereinfachung erfolgt durch die Reduktion der relevanten Haltestellen und durch eine Aggregation von Strecken zu sogenannten Systemrouten. Eine Systemroute fasst die Haltestellen eines Netzabschnitts zwischen zwei potenziellen End- oder Umsteigehaltestellen zu einer Strecke zusammen. Eine Systemroute entspricht einer möglichen Teilroute einer Linie. Das Vorgehen wird an einem realen städtischen Verkehrswegenetz beschrieben, für das eine planerische Referenzlösung existiert.

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

1 Einleitung

Der Planungsprozess für den öffentlichen Verkehr (ÖV) lässt sich in die folgenden Schritte aufteilen: (1) Linienpoolerstellung, (2) Linienplanung, (3) Fahrplanung, (4) Umlaufplanung und (5) Dienstplanung.

Für die Umlauf- und Dienstplanung haben sich mathematische Optimierungsverfahren bereits in der Praxis etabliert (z. B. [1, 2]). Sie sind in kommerziellen Softwareprodukten für die ÖV-Angebotsplanung implementiert und werden von Verkehrsbetrieben im Alltag eingesetzt. Mathematische Methoden für die Fahrplanung sind ebenfalls verfügbar (z. B. [3]), werden in der Praxis jedoch nur in ausgewählten Projekten einsetzt. Ähnliches gilt für die Linienplanung, die für ein Verkehrswegenetz mit zugehöriger Nachfrage ein Linienkonzept bestimmt, das aus einer Menge von Linien mit Frequenzen (Takten) besteht. Es gibt eine Vielzahl an Optimierungsverfahren (siehe [4]), die in Forschungsprojekten entwickelt und beispielhaft angewendet wurden. Sie werden bislang aber nur in Ausnahmefällen für die Planung von Liniennetzen in der Praxis angewandt [5]. Stand der Praxis sind rechnergestützte Intuitivverfahren (z. B. [6, 7]). Dabei entwerfen Planende eine gewisse Anzahl an Lösungen und berechnen ihre Wirkungen auf die Angebotsqualität und die Betriebskosten mit Verkehrsplanungsmodellen.

Ergebnisse der DFG-Forschungsgruppe 2083 „Integrierte Planung im öffentlichen Verkehr“ zeigen, dass die Linienplanung bei einem gegebenen (guten) Linienpool gut funktioniert, aber die Linienpoolerstellung noch ein großes Verbesserungspotenzial aufweist [8–10]. In der Forschungsgruppe wurden für virtuelle Untersuchungsräume (u. a. Rasternetz, Ringnetz) eine große Anzahl von planerischen und algorithmischen Lösungen erzeugt und verglichen. Für den Vergleich wurde für jede Lösung die Angebotsqualität (Kenngröße empfundene Reisezeit) und der betriebliche Aufwand (Kenngröße Betriebskosten) ermittelt. Die wesentlichen Unterschiede rein planerischer und rein algorithmischer Lösungen lassen sich wie folgt zusammenfassen [11]:

• Planerisches Vorgehen bevorzugt Lösungen mit relativ wenigen Linien, deren Frequenz auf einem Systemtakt Dadurch kann das Angebot jedoch nur begrenzt an die tatsächliche Nachfrage angepasst werden, sodass nicht alle Linien eine hohe Auslastung aufweisen.
• Algorithmisch erstellte Lösungen zeichnen sich meist durch eine höhere Anzahl von Linien aus, die jedoch mit einer geringeren Frequenz Dadurch können mehr Fahrgäste direkt befördert werden, was die Reisezeit reduziert. Mit geringeren und unterschiedlichen Frequenzen kann das Angebot besser an die Nachfrage angepasst werden, sodass die Kosten sinken. Die resultierenden Linienkonzepte werden von Planern allerdings häufig als „unübersichtlich“ bewertet.

Ziel dieses Beitrages ist es, darzustellen, wie Liniennetze für reale städtische Verkehrswegenetze mit den in der OpenSource-Bibliothek LinTim [12] vorhandenen Optimierungsverfahren erstellt werden können. Es geht also nicht um die Neu- oder Weiterentwicklung von Optimierungsverfahren, sondern um die geschickte Nutzung der dort bereits vorhandenen Verfahren. Das umfasst zum einen die Parametrisierung der Verfahren und zum anderen eine Aufbereitung der Eingangsdaten, die die Komplexität der Optimierungsaufgabe reduziert. Es ergibt sich die folgende Vorgehensweise:

• Untersuchungsraum ist das Gebiet der Stadt Stuttgart, für das ein Busnetz erstellt werden soll. Das schienengebundene Angebot (S-Bahn, Stadtbahn) ist vorgegeben, ebenso die Haltestellen für die Buslinien. Für den Untersuchungsraum existiert eine planerische Lösung, die als Referenzlösung genutzt wird.
• Die Eingangsdaten des Verkehrswegenetzes werden durch die Einführung sogenannter Systemrouten Eine Systemroute fasst die Haltestellen eines Netzabschnitts zwischen zwei potenziellen End- oder Umsteigehaltestellen zu einer Strecke zusammen. Auf diese Weise wird die Problemgröße für die Optimierungsverfahren reduziert. Die Systemrouten enthalten außerdem planerische Vorstellungen zu Teilrouten des Netzes.
• Mit LinTim werden für ausgewählte Parameter und Eingangsdaten neun verschiedene Lösungen generiert. Diese beinhalten auch eine automatische Erzeugung des Linienpools.
• Alle Lösungen werden anhand der Kenngrößen Reisezeit und Betriebskosten miteinander verglichen. Diese Kenngrößen werden mit einem Verkehrsnachfragemodell ermittelt. Um die Vergleichbarkeit der Ergebnisse zu ermöglichen, wird die planerische Lösung angepasst.
• Die Hauptergebnisse sind: 1. Die Verwendung von Systemrouten kann die rein automatisierte Erstellung von Lösungen verbessern. 2. Die planerische Lösung kann durch die in LinTim vorhandenen Optimierungsverfahren weiter verbessert werden.

2 Verkehrsangebot und Verkehrsnachfrage im Untersuchungsraum

Das Verkehrsangebot (Strecken, Haltestellen, Linien und Fahrpläne) und die Verkehrsnachfrage des Untersuchungsraums wird aus dem Verkehrsnachfragemodell der Region Stuttgart für den Planfall 2030 übernommen [13]. Das Modell ist mit PTV Visum implementiert und umfasst die Stadt Stuttgart und fünf umliegende Kreise. Für die Untersuchungen in diesem Beitrag wird nur das Stadtgebiet Stuttgart betrachtet. Das Verkehrsnachfragemodell enthält ein Liniennetz mit Fahrplänen für den Planungshorizont 2030, das als planerische Referenzlösung genutzt wird.

Für den Zweck der Busliniennetzplanung im Stadtgebiet Stuttgart wird das Verkehrsangebot auf das von Linien befahrene Straßennetz reduziert. In diesem Reduktionsprozess wird ein Netzmodell erstellt, das die Anforderungen von LinTim erfüllt. Dazu wird auf das in [14] beschriebene Verfahren zurückgegriffen, bei dem u. a. Haltepunkte zu Haltestellen aggregiert und Zwischenknoten im Straßennetz entfernt werden.

Das LinTim-kompatible Verkehrswegenetz [15] ist in Bild 1 dargestellt. Das Netz wird an der Stadtgrenze abgeschnitten, es sei denn, eine ÖV-Linie führt aus dem Stadtgebiet hinaus und dann auch wieder hinein. Dann wird auch der Verlauf außerhalb Stuttgarts berücksichtigt. Das Netzmodell besteht aus 577 Knoten, die zugleich die Haltestellen repräsentieren, 1.436 Strecken und 588 Verkehrszellen, wobei 74 davon Kordonzellen sind. Jeder dieser Verkehrszellen wird genau eine Haltestelle zugeordnet. Die Haltestellen sind zusätzlich durch ein Fußwegenetz miteinander verbunden. Ziel dieses Beitrags ist es, Busliniennetze für das Stadtgebiet Stuttgarts zu generieren. Das Angebot der sieben S-Bahn- und 18 Stadtbahn-Linien ist vorgegeben und soll nicht verändert werden. Die Mindestfahrzeiten für den Busverkehr auf den Strecken werden aus der Referenzlösung übernommen. Die planerische Referenzlösung umfasst 56 Buslinien.

Bild 1: Verkehrswegenetz für Bus- und Schienenverkehr im Untersuchungsraum.

Die Verkehrsnachfrage des ÖV entspricht der morgendlichen Spitzenstunde. Sie liegt bei knapp 40.000 Fahrgastfahrten pro Stunde. 75 Prozent der Fahrgastfahrten nutzen nur schienengebundene Verkehrsmittel, 25 Prozent den Bus alleine oder in Kombination mit der Schiene. Die Nachfragesituation zeichnet sich durch eine ausgeprägte Lastrichtung stadteinwärts aus. Im Planfall 2030 führt das in der morgendlichen Spitzenstunde zu einer Beförderungsleistung von rund 375.000 Personenkilometern bei knapp 7.300 angebotenen Einsatzkilometern. Eine Aufteilung der Kenngrößen auf die einzelnen Verkehrssysteme zeigt Tabelle 1.

Tabelle 1:    Aufteilung der Beförderungsleistung und der Betriebsleistung auf die verschiedenen Verkehrssysteme im Planfall 2030 für die morgendliche Spitzenstunde.

Bild 2 veranschaulicht die räumliche Aufteilung der Nachfrage auf die einzelnen Verkehrssysteme in der morgendlichen Spitzenstunde. Erkennbar sind die Dominanz der schienengebundenen Verkehrssysteme und die Lastrichtungen. Es lassen sich aber auch Nachfrageschwerpunkte abseits der Schiene feststellen.

Bild 2: Verkehrsnachfrage ÖV im Planfall 2030.

3 Kenngrößen zur Bewertung einer Lösung

Die Bewertung einer Lösung erfolgt bikriteriell anhand der Kenngrößen Betriebskosten und mittlere empfundene Reisezeit. Die Betriebskosten beziehen sich auf eine Stunde. Sie umfassen die Kosten für die Bereitstellung der Fahrzeuge einschließlich des Fahrpersonals und die kilometerabhängigen Kosten (Gleichung 1). Ein Umsetzen von Fahrzeugen zwischen zwei Linien ist bei der Umlaufbildung zulässig. Depots werden nicht berücksichtigt. Bei der Umlaufbildung wird eine Mindestwendezeit von 3 Minuten vorgegeben.

Formel in der PDF

Ausgangspunkt für die Ermittlung der Angebotsqualität ist eine Umlegung der Fahrgastnachfrage auf das ÖV-Angebot. Die in LinTim implementierten Verfahren betrachten dabei nur eine Route für jeden Passagier und sie vernachlässigen Fußwege. Damit die Auswertung der erzeugten Lösungen möglichst realitätsnah ist, wird für die Bewertung eine Mehrwegumlegung genutzt, die die Nachfrage auf die Menge der angebotenen Verbindungen verteilt. Bei der Verbindungssuche sind nur solche Verbindungen zulässig, die eine Mindestumsteigezeit von 3 Minuten einhalten. Für die Aufteilung der Nachfrage wird jede Verbindung r anhand der empfundenen Reisezeit (Gleichung 2) bewertet. Die Fahrtzeit, die Umsteigezeit und die Anpassungszeit einer Verbindung werden mit dem Faktor 1,0 gewichtet, die Gehzeit mit dem Faktor 1,5. Jeder Umsteigevorgang wird mit einem Zuschlag von 5 Minuten belegt. Die Anpassungszeit entspricht der Differenz zwischen der Wunschabfahrtszeit und der tatsächlich angebotenen Abfahrtszeit. Es wird angenommen, dass die Wunschabfahrtzeiten innerhalb der betrachteten Spitzenstunde gleichmäßig verteilt sind. Die mittlere empfundene Reisezeit im Untersuchungsraum ergibt sich aus den nachfragegewichteten Zeiten der einzelnen Verbindungen (Gleichung 3).

Formel in der PDF

Tabelle 2 dokumentiert die angenommenen Kapazitäten und Kostensätze für die verschiedenen Verkehrssysteme.

Tabelle 2: Überblick über die Verkehrssysteme.

Bild 3 zeigt die Kenngrößen für die Referenzlösung in der morgendlichen Spitzenstunde:

• Die Gesamtkosten liegen bei rund 31.300 Etwa die Hälfte der Kosten entfallen auf den Bus. Da lediglich das Busangebot geplant wird, werden im Folgenden nur die Betriebskosten für den Bus ausgewiesen.
• Die mittlere empfundene Reisezeit liegt bei 34,3 Minuten, davon entfallen 1,4 Minuten auf die Fahrtzeit im Der Anteil ist klein, da die Beförderungsleistung im Busverkehr deutlich kleiner als auf der Schiene ist. Allerdings beeinflusst das Busangebot auch die Umsteigezeiten, die Anpassungszeit und die Umsteigehäufigkeit. Trotzdem werden Änderungen im Busnetz lediglich zu kleinen Änderungen bei der mittleren empfundenen Reisezeit führen.

Bild 3: Betriebskosten und Bestandteile der mittleren empfundenen Reisezeit in der Referenzlösung.

4 Netzvereinfachung durch Systemrouten

In [8] wurde aufgezeigt, dass die Qualität algorithmisch erzeugter Lösungen steigt, wenn der automatisch generierte Linienpool um von Planern erstellte Linienrouten ergänzt wird. Eine Lösung wäre, alle möglichen Linienrouten in den Linienpool aufzunehmen. Der so entstehende Linienpool würde aber exponentiell viele Linienrouten enthalten, so dass die Verfahren der Linienplanung darauf nicht angewendet werden können.

Leider steht nicht immer ein planerischer Linienpool zur Verfügung. Alternativ zur Vorgabe planerischer Linienrouten wird daher im Folgenden ein Ansatz vorgestellt, der mithilfe planerischer Vorgaben das in der Optimierung verwendete Verkehrswegenetz vereinfacht und die Anzahl an Kombinationsmöglichkeiten bei der Linienpoolgenerierung so verringert, dass es möglich ist, sehr viele der verbliebenen möglichen Linienrouten für die Berechnung zu verwenden. Die Vereinfachung erfolgt durch die Reduktion der relevanten Haltestellen und durch eine Aggregation von Strecken zu sogenannten Systemrouten (SR), die potenzielle Teile einer Linienroute darstellen. Dazu werden drei Kategorien von Haltestellen unterschieden:

• Terminals (T): Sie definieren Haltestellen, an denen Linien beginnen und enden können.
• Umsteigehaltestellen (U): Hier sollen Fahrgäste bevorzugt umsteigen.
• Linienhaltestellen (L): Sie dienen nur dem Zu- und Ausstieg von Fahrgästen.

Um den Einfluss einer Netzvereinfachung auf das Ergebnis untersuchen zu können, werden im Untersuchungsraum drei Stufen von Terminals und Umsteigehaltestellen eingeführt (siehe Bild 4), die sich im Maß der Aggregation unterscheiden:

• TU1: Terminals und Umsteigehaltestellen werden auf Basis des aktuellen Bus-Liniennetzes automatisiert Ein Terminal ist eine Haltestelle, an der im Planfall 2030 mindestens eine Bus-Fahrplanfahrt beginnt oder endet. Eine Umsteigehaltestelle ist eine Haltestelle, die mehr als zwei Strecken verknüpft. So ergeben sich 102 Terminals und 101 Umsteigehaltestellen.
• TU2: In einem manuellen Prozess werden sowohl die Anzahl der Terminals als auch der Umsteigehaltestellen Dabei wird planerisches Wissen genutzt. Es werden Haltestellen, an denen nur einzelne Fahrplanfahrten beginnen, von der Eigenschaft eines Terminals entbunden. Die Anzahl der Umsteigehaltestellen wird in etwa halbiert. Es verbleiben 85 Terminals und 47 Umsteigehaltestellen.
• TU3: Die Anzahl an Terminals und Umsteigehaltestellen wird manuell weiter reduziert. In dieser Stufe gibt es noch 68 Terminals und 17 Umsteigehaltestellen.

Bild 4: Terminals (rot) und Umsteigehaltestellen (grau) für die verschiedenen Abstufungen.

Neben der Zahl relevanter Haltestellen können auch die Strecken reduziert werden. Dazu werden Systemrouten eingeführt, bei denen mehrere Strecken der zugrundeliegenden Infrastruktur zusammengefasst werden [16]. Eine Systemroute verbindet nur noch Haltestellen miteinander, die als Terminal oder Umsteigehaltestelle kategorisiert sind. Zugangspunkte an Linienhaltestellen L entlang einer Systemroute werden zu einem Zugangspunkt X aggregiert. Gibt es keine Haltestellen entlang einer Systemroute, wird kein Zugangspunkt erstellt. Bild 5 zeigt für einen kleinen Netzausschnitt den Aggregationsvorgang. Um die Nachfrage zwischen Haltestellen entlang einer Systemroute abzudecken, kann für jede Systemroute eine Binnennachfrage ermittelt werden, die dazu dienen kann, eine zusätzlich nötige Kapazität entlang eines solchen Streckenzuges zu definieren. Das reduzierte Verkehrswegenetz wird nun für die algorithmische Linienplanung genutzt. Das resultierende Linienkonzept kann dann wieder auf das Ausgangsnetz übertragen werden.

Bild 5: Aggregation von Strecken durch Systemrouten. Sieben Strecken werden auf eine Systemroute mit zwei Strecken reduziert.

Im Netzmodell Stuttgart führen die drei TU-Stufen zu drei Ausprägungen von Systemrouten. Tabelle 3 gibt einen Überblick über die Eigenschaften der TU- und SR-Netzmodelle im Vergleich zum ursprünglichen Netzmodell (N0). Es fällt auf, dass die Anzahl der Systemrouten zunächst von fast 500 in Stufe 1 auf knapp unter 400 in Stufe 2 sinkt. Danach steigt sie wieder an, da Systemrouten wegen der nur noch geringen Anzahl von Terminals und Umsteigehaltestellen vermehrt abschnittsweise parallel geführt werden. Ursache dafür ist auch, dass schon N0 relativ stark vereinfacht ist.

Tabelle 3: Überblick über die Netzgrößen im Busnetz.

5 Anwendung des Verfahrens

Für den Untersuchungsraum wurde mit den vorgestellten Wegenetzen (N0, TU1 bis TU3, SR1 bis SR3) eine große Anzahl an Lösungen rein algorithmisch, inklusive der Linienpoolerstellung, generiert. Dabei wurden die in Tabelle 4 dargestellten Methoden genutzt, die zum Teil einen planerischen Eingriff ermöglichen oder erfordern. Nachfolgend werden Linienkonzepte für neun ausgewählte algorithmisch erzeugte Lösungen A1 bis A9 präsentiert. Tabelle 5 dokumentiert die Methoden, die den jeweiligen Linienkonzepten zugrunde liegen.

Alle Linienkonzepte basieren auf einer Systemfrequenz von 2, d. h. jede Buslinie hat mindestens die Frequenz 2 (30-Minuten-Takt) oder ein Vielfaches der Systemfrequenz, aber maximal die Frequenz 12 (5-Minuten-Takt). Es wurden auch Lösungen ohne diese Anforderungen generiert. Sie schneiden in einer bikriteriellen Bewertung unter Umständen besser ab, entsprechen aber nicht den planerischen Vorstellungen.

Die ausgewählten Linienkonzepte nutzen nicht alle in Tabelle 4 dargestellten Methoden, da die Kombinatorik der Methoden zu einer großen Anzahl von Linienkonzepten führt. Die Diskussion aller Linienkonzepte sprengt den Umfang einer Veröffentlichung. Deshalb werden solche Methoden miteinander kombiniert, die den Einfluss der Systemrouten aufzeigen (Tabelle 5). Für die nicht genutzten Methoden sind folgende Aussage möglich:

• Vorgaben für die Nachfrageumlegung beeinflussen das Verkehrswegenetz und in der Folge die Linienpoolgenerierung. In der Untersuchung wurde das Verkehrswegenetz bereits vorab stark vereinfacht, sodass der Einfluss der Nachfrageumlegung gering ist.
• Für die Methode „Kompletter Linienpool“ ist die Zahl der Terminals im betrachteten Untersuchungsraum zu groß.
• Die Vorgabe von planerischen Nebenbedingungen bei der Linienauswahl und der Frequenzbestimmung führt für jede Vorgabe zu einer bestimmten Lösung. Unterschiede in den Linienkonzepten erklären sich direkt aus den planerischen Vorgaben.
• Die Methode für die Fahrplanung hat einen geringen Einfluss auf das Ergebnis.

Tabelle 4:     Übersicht über ausgewählte Methoden der ÖV-Planung.

Tabelle 5:    Überblick über die algorithmischen Linienkonzepte.

Für den Vergleich der algorithmisch erzeugten Buslinienkonzepte mit der planerischen Referenzlösung werden vier Ausprägungen von planerischen Linienkonzepten P1 bis P4 unterschieden. Diese Unterscheidung ist notwendig, da die Referenzlösung Eigenschaften enthält, die sich von den algorithmischen Lösungen unterscheiden. Für die Linienkonzepte P3 und P4 werden zusätzlich mit algorithmischen Methoden neue Fahrpläne generiert, um so das Verbesserungspotenzial der Referenzlösung bei den Fahrplänen zu quantifizieren. Es ergeben sich folgende Linienkonzepte:

• P1: Dieses Linienkonzept entspricht der planerischen Referenzlösung. Hier gibt es Fahrplanfahrten, die nicht die komplette Linienroute bedienen. Der Fahrplan muss nicht perfekt getaktet sein und an Haltestellen sind Aufenthaltszeiten möglich.
• P2: Im Gegensatz zu P1 bedient jede Fahrplanfahrt die komplette Linienroute.
• P3: Im Gegensatz zu P2 sind die Fahrplanfahrten aller Linien getaktet.
• P4: Im Gegensatz zu P3 wird – wie bei den algorithmischen Lösungen – keine Haltestellenaufenthaltszeit mehr eingeplant.

Die Lösungen P3 und P4 werden weiter mit Optimierungsverfahren verbessert. Auf diese Weise werden die folgenden optimierten Linienkonzepte erzeugt.

• O3a: Der Fahrplan von P3 wird mit der in PTV Visum implementierten Taktversatzoptimierung [27] angepasst.
• O4a: Der Fahrplan von P4 wird mit der in PTV Visum implementierten Taktversatzoptimierung angepasst.
• O4b: Der Fahrplan von P4 wird mit LinTim Die Frequenzen bleiben erhalten.
• O4c: Die in der Referenzlösung verwendeten Linienrouten bilden den Linienpool. LinTim führt damit Linien-, Fahr- und Umlaufplanung aus. Die meisten Linien der Referenzlösung sind nötig, um den Bedarf abzudecken, drei Linien können aber entfallen.

Die Linienkonzepte P4, O4a, O4b und O4c halten die gleichen Randbedingungen ein, wie die mit LinTim generierten Linienkonzepte A1 bis A9. Die Linienkonzepte P1, P2, P3 und O3a enthalten zusätzliche Merkmale wie Pufferzeiten oder Verstärkerfahrten. Sie sind daher nur bedingt mit den anderen Linienkonzepten vergleichbar.

Tabelle 6 zeigt ausgewählte Kenngrößen der untersuchten Linienkonzepte. Die Kenngrößen der Angebotsqualität (mittlere empfundenen Reisezeit, Umsteigehäufigkeit) gelten für die Nachfrage im gesamten Untersuchungsraum. Die betrieblichen Kenngrößen beziehen sich nur auf den Bus.

Tabelle 6: Kenngrößen der Linienkonzepte.

Bild 6 veranschaulicht die bikriterielle Bewertung anhand der beiden Kenngrößen Betriebskosten und empfundene Reisezeit für die untersuchten Linienkonzepte.

Bild 6: Bikriterielle Bewertung und Paretofront der untersuchten Linienkonzepte.

Im Linienkonzept A1 werden Methoden gewählt, die bis auf die Vorgabe einer Systemfrequenz von 2 keine weiteren planerischen Beschränkungen verwendet. Für die Linienauswahl wird ein Verfahren gewählt, das sowohl Kosten als auch Direktfahrer berücksichtigt. Hinsichtlich der beiden Kenngrößen ist die Lösung vergleichbar mit P1.

Im Linienkonzept A2 wird statt eines kombinierten Kosten- und Direktfahrermodells ein reines Kostenmodell für die Linienauswahl gewählt. Die anderen Einstellungen sind gleich wie in A1. Gegenüber A1 sinken die Kosten und die mittlere empfundene Reisezeit steigt.

Linienkonzept A3 nutzt die Vorgabe von Terminals und Umsteigehaltestellen der Stufe TU1 bei Beibehaltung der sonstigen Einstellungen. Das Konzept wird teurer, aber auch schneller als A1. Aus planerischer Sicht ist bei diesem Konzept vorteilhaft, dass Fahrplanfahrten nur noch an Haltestellen beginnen und enden, an denen es auch in P1 vorgesehen ist.

Das Linienkonzept A4 nutzt Systemrouten basierend auf TU1. Ergebnis ist das kostengünstigste Linienkonzept der ausgewählten Lösungen.

Linienkonzept A5 basiert auf den Terminals und Umsteigehaltestellen der Stufe TU2. Bei einer geringen Kostensteigerung kann die empfundene Reisezeit gegenüber A3 deutlich gesenkt werden. Die Aggregationsstufe TU2 scheint daher besser geeignet zu sein als TU1.

Im Linienkonzept A6 werden Systemrouten basierend auf TU2 verwendet. Die Kosten der Buslinien werden gegenüber A5 bei gleichbleibender empfundener Reisezeit um rund elf Prozent gesenkt.

Das Linienkonzept A7 basiert auf Terminals und Umsteigehaltestellen der Stufe TU3. Aufgrund der geringeren Anzahl von Terminals werden die Buslinien länger. Dadurch sinkt die empfundene Reisezeit bei leicht erhöhten Kosten.

Das Linienkonzept A8 nutzt Systemrouten basierend auf TU3. Aufgrund der abschnittsweise parallel geführten Systemrouten werden viele lange Buslinien generiert. Das führt zu einer schnellen, aber sehr teuren Lösung. Offensichtlich führt diese Aggregationsstufe zu einem Wegenetz, dass für die Zwecke der Linienplanung nicht mehr geeignet ist.

Das letzte Linienkonzept A9 basiert auf den gleichen Randbedingungen wie A3, außer dass die Systemfrequenz 6 statt 2 beträgt. Dadurch reduziert sich die Anzahl der Buslinien von 131 auf 45. Gleichzeitig nimmt die mittlere Linienlänge deutlich zu. Diese Lösung dominiert A8. In der Realität würde man wohl nicht jede dieser Linien mit einer Frequenz von mindestens 6 bedienen. Diese Parameterwahl ist aber geeignet, um lange Linien zu generieren.

Unter den Lösungen A1 bis A8 (die alle den gleichen Systemtakt aufweisen) sind die Lösungen A4, A6, A7 und A8 Pareto-Lösungen. Sie dominieren die Lösungen A1, A2, A3 und A5, die alle nicht mit Systemrouten erstellt wurden. Die Anwendung von Systemrouten verbessert in diesem Beispiel also die Lösungsqualität.

Die planerische Referenzlösung ist allerdings als besser einzustufen. Sie dominiert die Lösungen A1, A2, A3, A5, A6, A7 und optimiert Kosten und Reisezeit gleichermaßen. Durch Anwendung von Optimierungsverfahren kann sie sogar noch weiter verbessert werden. Die Paretofront der erzeugten Lösungen besteht damit aus den Lösungen A9, O4c, O4b und A4, wobei A9 und O4c bei relativ hohen Betriebskosten eine sehr gute Reisezeit bieten, A4 die kostengünstigste Lösung ist und O4b bei kaum höheren Kosten als A4 eine immer noch sehr gute Reisezeit aufweist.

Untersucht man die Struktur der erzeugten Linienrouten, ist klar erkennbar, dass die mit automatisch generiertem Linienpool erstellten Linienkonzepte A1 bis A7 bei ähnlicher Betriebsleistung mehr und kürzere Linien mit geringeren Frequenzen aufweisen als die Linienkonzepte P1 bis P4, O3a, O4a und O4b. Damit lässt sich die Nachfrage mit kleinen Kosten abdecken, allerdings erhöht sich die Zahl an Umsteigevorgängen und damit auch die mittlere empfundene Reisezeit. Ein Planer würde in einem solchen Fall vermutlich die Linien miteinander verknüpfen und lediglich die Frequenz an den Außenästen reduzieren. Um das algorithmisch abzubilden müssten die entsprechenden Verstärkerlinien in den Linienpool mit aufgenommen werden.

Mit dem Systemrouten-Ansatz wurden auch für andere Parameter Linienkonzepte erstellt. Insgesamt entstanden Ergebnisse für 48 Szenarien. Vergleichswerte der Systemrouten-Lösungen hinsichtlich der Kosten, der mittleren empfundenen Reisezeit sowie der Rechenzeit der Algorithmen im Vergleich zu N0 und der jeweiligen TU-Lösung zeigt Tabelle 7. Es ist ersichtlich, dass der Systemrouten-Ansatz bis zu einem gewissen Maß der Vereinfachung (hier SR2) Verbesserungen liefert, danach aber unrealistisch teure Lösungen generiert. In allen drei Stufen haben Systemrouten einen positiven Einfluss auf die Rechenzeit der Algorithmen.

Tabelle 7: Vergleich von Linienkonzepten mit Systemrouten und Lösungen des ursprünglichen Netzmodells.

6 Fazit und Ausblick

Der Beitrag zeigt, dass die komplexe Struktur eines Verkehrswegenetzes so transformiert werden kann, dass Algorithmen der ÖV-Planung angewendet werden können. Dazu werden Haltepunkte zu Haltestellen aggregiert, Knoten des Straßennetzes entfernt, Terminals und Umsteigehaltestellen definiert und Strecken mithilfe von Systemrouten reduziert. Die Herausforderung besteht dabei darin, ein angemessenes Maß für die Vereinfachung der Eingangsdaten zu finden.

Die Ergebnisse des Anwendungsbeispiels lassen sich wie folgt zusammenfassen:

• Die Ergebnisse von [8] konnten von artifiziell erzeugten kleinen Beispielen auf ein realistisches Verkehrsnetz übertragen werden. Optimierungsverfahren sind geeignet das Verkehrsangebot zu verbessern, wenn ein von Planern generierter Linienpool verwendet wird.
• Systemrouten verbessern die automatische Generierung von Die resultierenden Linienpläne weisen bessere Kennzahlen auf und werden planerischen Vorstellungen besser gerecht.
• Die Verwendung eines planerisch erstellten Linienpools ist aber weiterhin besser.
• Die Lösungen mit algorithmisch erzeugtem Linienpool und die Lösungen mit planerisch erzeugtem Linienpool unterscheiden sich trotz vergleichbarer Kenngrößen bei der Linienzahl deutlich.
• Planerische Vorgehensweisen, die in einem rechnergestützten Prozess einen Linienpool erstellen, sind noch nicht durch algorithmische Lösungen ersetzbar.
• Bei der Fahrplanung verbessern Optimierungsverfahren die Ergebnisqualität.

Für die Weiterentwicklung und Anwendung der algorithmischen Linienplanungsverfahren ergeben sich folgende Schlussfolgerungen:

• Anwendungen in kleineren Netzen zeigen, dass die Erstellung eines kompletten Linienpools, der alle Linienwege zwischen Terminals umfasst, die Ergebnisqualität In großen Netzen ist dieses Vorgehen aufgrund der exponentiellen Anzahl möglicher Linienrouten nicht realisierbar.
• Eine Verkettung von Linien, auch bei unterschiedlichen Frequenzen, kann die Zahl der Linien reduzieren.
• Eine in der Praxis übliche Verdichtung der Frequenzen in Teilbereichen einer Linie kann durch die planerische Vorgabe von Verstärker-Terminals erleichtert werden, an denen nur Linienrouten enden dürfen, die Teil einer übergeordneten Linie sind (Bild 7-1). Alternativ kann man für alle Linienrouten auch ihre Teilrouten dem Linienpool zufügen.

Bild 7: Linienrouten, die durch planerische Vorgaben von Terminals, Umsteigehaltestellen und Abbiegebedingungen definiert werden können.

• Eine Verästelung von Liniennetzen in Außenbereichen mit geringerer Nachfrage kann durch Gabelungslinien (Bild 7-2) oder Zubringerlinien erreicht werden (Bild 7-3). Welcher Ansatz wünschenswert ist, ist eine planerische Entscheidung, die durch die Vorgabe von Terminals beeinflusst werden kann. Zusätzlich muss die Linienpoolgenerierung Abbiegebedingungen berücksichtigen können, die Einschränkungen der bestehenden Infrastruktur oder planerische Vorgaben darstellen.
• Ein Vergleich von planerischen und algorithmischen Linienrouten zeigt, dass die planerischen Linienrouten Eigenschaften aufweisen, die algorithmische Linienrouten auch mit einer Netzvereinfachung nicht abbilden können. Dazu gehören Stichlinien (Bild 7-4) und Blockumfahrungen am Linienende. Das erfordert die Vorgabe von Haltestellen, an denen U-Turns möglich sind und die Abbildung von Einbahnstraßen im Verkehrswegenetz.

7 Danksagung und Autorenbeiträge

Die Inhalte des Beitrags wurden im Rahmen der DFG-Forschungsgruppe 2083 „Integrierte Planung im öffentlichen Verkehr“ erarbeitet. Alexander Migl hat das Modell erstellt und die Berechnungen durchgeführt. Alexander Schiewe generierte die algorithmischen Linienkonzepte. Markus Friedrich und Anita Schöbel haben mit Anregungen beigetragen und die Ergebnisse des Modells plausibilisiert.

8 Literatur

1. S. Bunte, N. Kliewer (2009). An overview on vehicle scheduling models. Public Transport, Heft 4, Seiten 299–317.
2. M. Hickman, P. Mirchandani, S. Voß, Hrsg. (2008). Computer-aided systems in public transport. Lecture Notes in Economics and Mathematical Systems 600. Springer-Verlag, Berlin.
3. C. Liebchen (2005). Der Berliner U-Bahn Fahrplan 2005 – Realisierung eines mathematisch optimierten Angebotskonzeptes, Karlsruhe, 2.-3. März 2005 im Rahmen der Heureka '05 - Optimierung in Verkehr und Transport, Tagungsbericht. FGSV Verlag, Köln.
4. A. Schöbel (2012). Line planning in public transportation: models and methods. OR Spectrum 34, 3, S.491–510.
5. R. Borndörfer, M. Karbstein, A. Egerer, R. Messerschmidt, M. Perez, S. Pfisterer, P. Strauß (2019). Optimierung des Liniennetzes in Karlsruhe. Konzepte im Zeichen der Kombilösungen. Der Nahverkehr 37, 1+2, Seiten 33–38.
6. M. Friedrich (1994). Rechnergestütztes Entwurfsverfahren für den ÖPNV im ländlichen Raum. Dissertation. Schriftenreihe des Lehrstuhls für Verkehr und Stadtplanung, Technische Universität München.
7. P. Kirchhoff (2002). Städtische Verkehrsplanung. Springer eBook Collection Computer Science and Engineering. Vieweg+Teubner Verlag, Wiesbaden.
8. M. Friedrich, M. Hartl, A. Schiewe, A. Schöbel (2017). Angebotsplanung im öffentlichen Verkehr - Planerische und algorithmische Lösungen, Stuttgart, 22.-23. April 2017 im Rahmen der Heureka '17 - Optimierung in Verkehr und Transport, Tagungsbericht. FGSV Verlag, Köln.
9. M. Friedrich, M. Hartl, A. Schiewe, A. Schöbel (2018). System Headways in Line Planning. Proceedings of CASPT.
10. M. Friedrich, M. Hartl, A. Schiewe, M. Schilling, A. Schöbel (2021). Kombination von Linienkonstruktions- und Linienauswahlverfahren für die Liniennetzplanung, Stuttgart, 13.-14. April 2021 im Rahmen der Heureka '21 - Optimierung in Verkehr und Transport, Tagungsbericht. FGSV Verlag, Köln.
11. M. Hartl (2020). Integrierte ÖV-Planung – Entwurf, Vergleich und Bewertung von planerischen und algorithmischen Lösungsverfahren. Dissertation. Veröffentlichungen aus dem Institut für Straßen- und Verkehrswesen, Universität Stuttgart.
12. LinTim (2022). An integrated environment for mathematical public transport https://lintim.net/. Abgerufen am 31. Juli 2023.
13. S. Tritschler, M. Biechele (2020). Fortschreibung des VRS-Verkehrsmodells auf den Prognosehorizont 2030. Im Auftrag des Verbands Region Stuttgart (VRS).
14. A. Migl, M. Friedrich (2023). Make a real Visum network ready for LinTim. https:// github.com/FOR2083/Interface_MakeVisumNetworkReadyForLinTim. Abgerufen am Juli 2023.
15. FOR2083 (2023). Stuttgart https://github.com/FOR2083/PublicTransportNet-works/tree/master/Stuttgart. Abgerufen am 11. September 2023.
16. M.Friedrich, A. Migl, A. Schiewe, M. Schilling, A. Schöbel (2022). Improving the Solvability of Public Transport Problems Using System Routes im Rahmen der CASPT 2022.
17. M. Friedrich, M. Hartl, A. Schiewe, A. Schöbel (2017). Integrating Passengers' Assignment in Cost-Optimal Line Planning, Wien, 7.-8. September 2017 im Rahmen der AT-MOS 2017. Leibniz-Zentrum für Informatik, Schloss Dagstuhl.
18. R. Hüttmann (1979). Planungsmodell zur Entwicklung von Nahverkehrsnetzen liniengebundener Verkehrsmittel. Veröffentlichungen des Instituts für Verkehrswirtschaft, Straßenwesen und Städtebau, Universität Hannover.
19. P. Gattermann, J. Harbering, A. Schöbel (2017). Line pool generation. Public Transport 9, 1, Seiten 7–32.
20. P. J. Zwaneveld, M.T. Claessens, N.M. van Dijk (1996). A new method to determine the cost optimal allocation of passenger lines. Delft, TRAIL Research School. Defence or Attack: Proceedings 2nd Trail PhD Congress 1996, part 2.
21. M. R. Bussieck, P. Kreuzer, U.T. Zimmermann (1996). Optimal lines for railway systems. European Journal of Operational Research 96, 1, Seiten 54–63.
22. J. Pätzold, A. Schöbel (2016). A Matching Approach for Periodic Timetabling, Aarhus, 25. August 2016 im Rahmen der ATMOS 2016. Leibniz-Zentrum für Informatik, Schloss Dagstuhl.
23. L. Peeters, L. Kroon (2001). A Cycle Based Optimization Model for the Cyclic Railway Timetabling Problem im Rahmen der CASPT 2000. Lecture Notes in Economics and Mathematical Systems 505. Springer, Berlin, Heidelberg, Seiten 275–296.
24. C. Liebchen (2006). Periodic Timetable Optimization In Public Transport. Dissertation. Technische Universität Berlin.
25. J. Pätzold, A. Schiewe, P. Schiewe, A. Schöbel (2017). Look-Ahead Approaches for Integrated Planning in Public Transportation, Wien, 7.-8. September 2017 im Rahmen der ATMOS 2017. Leibniz-Zentrum für Informatik, Schloss Dagstuhl.
26. PTV AG (2020). PTV Visum Handbuch, Karlsruhe.
27. C. Liebchen, K. Nökel (2002). Überführung eines mathematischen Modells zur Taktversatzoptimierung in die Praxis, Karlsruhe, 6.-7. März 2002 im Rahmen der Heureka '02 - Optimierung in Verkehr und Transport, Tagungsbericht. FGSV Verlag, Köln.