| Volltext |
Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.
1 Einleitung
Die Linienplanung ist ein wichtiges strategisches Entscheidungsproblem bei der Planung eines öffentlichen Nahverkehrsnetzes. In der Linienplanung wird festgelegt, auf welchen Wegen (im Nahverkehrsnetz) Linien entlang fahren und wie oft sie fahren, d. h. zu bestimmen sind Linienrouten und Taktfrequenzen der Linien. Man kann dabei verschiedene Ziele verfolgen. Zum einen können die Kosten des Linienplans minimiert werden, so dass eine gegebene Anzahl an Fahrgästen transportiert werden kann. Zum anderen können die Fahrzeiten und/oder Umsteigezeiten der Passagiere minimiert werden. Eine weitere Möglichkeit besteht darin, einen Linienplan zu finden, der für möglichst viele Personen attraktiv ist, d. h. den Modal Split zugunsten des Nahverkehrs zu verbessern.
Es gibt einige Ansätze, mit Hilfe von Planungssystemen Linienpläne zu berechnen bzw. zu verbessern. Mit der Verkehrsplanungssoftware VISUM der ptv AG können zum Beispiel Veränderungen am Liniennetz vorgenommen und die Auswirkungen am Rechner simuliert werden [13]. So weit wir wissen, gibt es bisher keine Beispiele für den Einsatz von mit mathematischen Methoden der ganzzahligen Optimierung berechneten Linienplänen in der Praxis.
In der Operations-Research-Literatur wird die Linienplanung im öffentlichen Nahverkehr seit den 70er Jahren untersucht. Die ersten Verfahren beschäftigten sich mit heuristischen Ansätzen zur Bestimmung eines Linienplans, siehe z. B. Ceder und Israeli [9] und die darin enthaltenen Referenzen. Eine auf Branch-and-Bound basierende Software zur Linienplanung für Nederlands Spoorwegen wurde von Bouma und Oltrogge [5] entwickelt. Dazu schlagen sie eine Methode vor, den sogenannten „System Split“, um die Passagiere bereits vor der Linienplanung auf die einzelnen Kanten im Netz zu verteilen. Die Idee ist, dass Passagiere zu schnellen Zügen so früh wie möglich und zu langsamen Zügen so spät wie möglich wechseln. Außerdem nehmen sie an, dass sich Passagiere immer für den fahrzeitkürzesten Weg entscheiden. Aufbauend auf dem System Split gibt es einige Arbeiten, die die Linienplanung als ganzzahliges Optimierungsproblem auffassen und mit Branch-and-Bound- bzw. Branch-and-Cut-Methoden lösen. Bussieck, Kreuzer und Zimmer [7] maximieren die Anzahl der Direktfahrer. Claessens, van Dijk und Zwanefeld [10] minimieren die operativen Kosten eines Linienplans. Sie versuchen dabei die Kosten durch die zu erwartende Menge an benötigtem Material und Personal abzuschätzen. Sie betrachten zunächst ein nichtlineares Modell, das sie dann linearisieren, um es mit Methoden der ganzzahligen, linearen Programmierung zu lösen. Die Doktorarbeit von Bussieck [6] diskutiert sowohl den Ansatz zur Maximierung der Direktfahrer als auch den zur Minimierung der Kosten und betrachtet Komplexität, polyedrische und algorithmische Aspekte im Detail. Bussieck, Lindner und Lübbecke [8] betrachten ebenfalls ein Modell zur Minimierung der Kosten, ähnlich zu dem von Claessens, van Dijk und Zwanefeld [10]. Sie schlagen jedoch vor, Methoden der linearen und nichtlinearen Optimierung miteinander zu kombinieren und zur Berechnung einer guten Startlösung zu verwenden. Goossens, van Hoesel und Kroon [11] untersuchen einen detaillierten Lösungsalgorithmus zur Berechnung eines Linienplans mit minimalen Kosten und vergleichen diese Methode mit CPLEX. Alle vorgestellten Modelle werden mit den Daten des niederländischen Fernverkehrsnetzes getestet.
Mögen die Annahmen des System Splits im Fernverkehr noch ihre Berechtigung haben, so ist im Nahverkehr eher davon auszugehen, dass die Passagiere ihre Wege in Abhängigkeit vom Liniennetz ändern. Daher wurden in den letzten fünf Jahren verstärkt Modelle entwickelt, die die Wege der Passagiere während der Linienoptimierung mitbestimmen. Schöbel und Scholl [14] und Scholl [15] entwickelten ein Modell zur Minimierung der Fahrzeit inklusive einer Strafzeit für jeden Umstieg. Dazu betrachten sie einen sogenannten „Change-and-Go- Graphen“, der ein Nahverkehrsnetz zusammen mit den möglichen Linien repräsentiert und alle möglichen Umsteigerelationen enthält. Sie lösen mit Hilfe einer Dantzig-Wolfe-Dekomposition die LP-Relaxierung. Borndörfer, Grötschel und Pfetsch [4, 3] schlagen eine Modellierung des Linienplanungsproblems als ein Mehrgüterflussproblem vor, das Reisewege von Passagieren und den Verlauf von Linien im Netz miteinander verknüpft. Sie verzichten dabei auf einen gegebenen Linienpool und generieren die Linien dynamisch während des Lösungsprozesses. Ihre Zielfunktion ist eine Gewichtung aus Fahrzeit und Kosten. Sie benutzen Pricingalgorithmen für die Passagierpfade und die Linienpfade und lösen so eine LP-Relaxierung ihres Modells für die Daten von Potsdam. Sie benutzen eine Greedy-Heuristik um eine zulässige, ganzzahlige Lösung zu bestimmen. Auch Nachtigall und Jerosch [12] kombinieren eine Verkehrsumlegung mit einer Linienplanung. Dabei werden die Wege der Passagiere in Routensegmente aufgeteilt, für die es eine direkte Verbindung mit einer Linie gibt. Dadurch kann für jeden Weg die Anzahl der Umstiege gezählt und mit einer zusätzlichen Zeit bestraft werden. Daraus lässt sich eine Nutzenfunktion für jeden Weg bestimmen, die in dem Modell dann maximiert werden soll. Für ihr Modell ist ein gegebener Linienpool Voraussetzung. Sie führen Berechnungen für das Bus- und Straßenbahnnetz von Berlin durch. Obwohl die Menge der betrachteten Linien recht gering ist (kleiner als 100), erreicht ihr Modell die Speichergrenze des verwendeten Computers.
In dieser Arbeit stellen wir die Ergebnisse einer Studie zur Berechnung eines Linienplans für den Verkehrsbetrieb in Potsdam (ViP) vor, der alle wichtigen praktischen Anforderungen erfüllt und beweisbar nahezu optimal ist. Für Potsdam ist neben den Kosten des Linienplans und den Fahrzeiten der Passagiere auch die Anzahl der Umstiege wichtig. Daher verwenden wir für unser Modell den Change-and-Go-Graphen von Schöbel und Scholl [14]. Da die Größe des Change-and-Go-Graphen von der Größe des betrachteten Linienpools abhängt, hängt auch die Rechenbarkeit dieses Modells direkt von der Größe des Linienpools ab. Allerdings ist die Menge aller zulässigen Linien in Potsdam nicht größer als 3500. Daher ist dieser Ansatz kombiniert mit den Algorithmen aus [3] zur Behandlung der Vielzahl von möglichen Passagierrouten für diesen Fall noch rechenbar. Es sei bemerkt, dass wir kürzlich zur Lösung von größeren Instanzen in [1] als Alternative zur Verwendung des Change-and-Go-Graphen eine Erweiterung des Modells von Borndörfer, Grötschel und Pfetsch [3] vorgeschlagen haben, das eine untere Schranke an die Umstiege pro Passagierpfad liefert und die Einhaltung einer Direktfahrerbedingung sicherstellt.
2 Modellierung
In diesem Abschnitt stellen wir die Idee des Change-and-Go-Ansatzes vor, definieren ein lineares Optimierungsproblem zur Berechnung eines optimalen Linienplans und beschreiben die Anforderungen an den Linienplan 2010 für Potsdam und dessen Berechnung mit Hilfe des Modells.
2.1 Change-and-Go-Ansatz
Die Idee eines Change-and-Go-Graphen, siehe auch Schöbel and Scholl [14], besteht darin, alle möglichen Umsteigebeziehungen als Kanten in einem Graphen zu repräsentieren, so dass es möglich ist Gewichte auf diesen Kanten zu definieren und somit den Umsteigevorgang zu „bestrafen“. Dazu wird ein (gerichtetes) Netzwerk G = (V, A) aufgebaut, so dass jeder Knoten v ∈ V eindeutig einem Paar von Station und Linie zugeordnet werden kann oder ein OD-Knoten (Start- oder Endknoten eines Passagierweges) ist. Zwei Knoten werden dann durch eine Kante miteinander verbunden, wenn es eine direkte Verbindung zwischen diesen beiden Stationen gibt und beide Knoten zu der gleichen Linie gehören oder wenn es möglich ist, zwischen den beiden Linien an den beiden (nicht notwendigerweise verschiedenen) Stationen umzusteigen. Für zwei OD-Knoten s und t bezeichne dst die Nachfrage, d. h. die Anzahl der Personen, die von s nach t fahren wollen.
Formal kann der Change-and-Go-Graph wie folgt beschrieben werden. Aus einem Nahverkehrsnetz G = (V , E ), in dem V die Menge aller Stationen repräsentiert und E die Menge aller Strecken, d. h. direkte Verbindungen zwischen zwei Stationen, wird ein Change-and-Go-Graph G = (V, A) konstruiert. Die Knotenmenge ist V = VO ∪ VL, wobei VL Paare von Linien und Stationen repräsentiert und VO die Menge der OD Knoten mit positiver Nachfrage:
Formel siehe PDF.
Die Kanten sind A = AO ∪ AL ∪ AT , wobei AO die Kanten sind, die OD-Knoten mit den Netzknoten verbinden, AL Linienkanten und AT Umsteigekanten:
AO = {s ,(s, l) ∈ VO × VL | l ∈ L : s ∈ l}
AL = {u , l), (v , l) ∈ VL × VL | l ∈ L : {u,v} ∈ E}.
AT = {v , l), (v , l) ∈ VL × VL | l ∈ L, l ∈ L}.
Bild 1: Gemischt-ganzzahliges Optimierungsmodell zur Linienplanung
2.2 Lineares Optimierungsmodell
Wir definieren in diesem Abschnitt ein Modell zur Linienplanung, in dem die Wege der Passagiere nicht a-priori fixiert sind, d. h., zusammen mit dem (optimalen) Linienplan berechnen wir gleichzeitig und in wechselseitiger Abhängigkeit auch die Wege der Passagiere. Dies eröffnet im Vergleich mit den bisher verwendeten Ansätzen ein höheres Optimierungspotential hinsichtlich Fahrzeit und Kosten [2]. Zur Berechnung der Passagierwege verwenden wir eine Modellierung als ein Mehrgüterflussproblem. Die Passagierwege werden dabei als Pfade modelliert und mit einem Pricingalgorithmus dynamisch generiert. Dies ist notwendig, da das gesamte Nahverkehrsnetz von Potsdam (aufgeschlüsselt nach Verkehrssystemen) über 5200 Kanten enthält und über 4400 positive Nachfragebeziehungen. Allein der dem Mehrgüterflussproblem zugrunde liegende Graph hat über 20 Millionen Kanten.
Formal kann das Modell wie folgt beschrieben werden: Wir konstruieren einen Change-and-Go-Graphen aus der Menge der Linien L und aller Stationen und Strecken des Nahverkehrsnetzes. Jede Linie verbindet zwei ausgezeichnete Endstationen im Netz und besteht aus zwei Richtungen. Jede Richtung ist ein einfacher Pfad, d. h., es wird keine Station mehrfach angefahren. Für jede Linie betrachten wir eine Menge von möglichen Taktfrequenzen F = {1, . . ., F }. Die Kapazität κl,f einer Linie l hängt von dem Verkehrstyp (z. B. Bus oder Straßenbahn) und der Frequenz der Linie ab. Für eine Linie betrachten wir außerdem Fixkosten Cl, die anfallen, sobald eine Linie in Betrieb genommen wird, und variable Kosten cl,f = cl · f für den Betrieb der Linie, die von der Länge und der Frequenz der Linie abhängen.
Sei D = {(s, t ) ∈ V ×V : dst > 0} die Menge der Paare von OD-Knoten mit positiver Nachfrage, wir nennen sie auch OD-Paar. Für jedes OD-Paar (s, t ) ∈ D betrachten wir eine Menge von Pfaden Pst , die s und t miteinander verbinden, die Passagierpfade oder Passagierrouten. Diese stellen die möglichen Reiserouten dar, die ein Passagier nutzen kann. Ein Pfad p hat eine Fahrzeit von τp = a∈p τa, die sich aus der Fahrzeit der enthaltenen Strecken zusammensetzt. Unser Optimierungsmodell verwendet zwei Arten von Variablen:
yp ∈ IR+: die Anzahl der Passagiere, die von s nach t auf einem Pfad p ∈ Pst reisen,
xl,f ∈ {0, 1}: gibt an, ob Linie l mit Frequenz f in Betrieb genommen wird.
Wir können damit das Linienplanungsproblem als ein gemischt-ganzzahliges lineares Programm formulieren, das in Bild 1 dargestellt ist. Die Zielfunktion besteht aus zwei Teilen, den Linienkosten, die die betriebswirtschaftlichen Aspekte widerspiegeln, und der Gesamtfahrzeit für alle Passagiere, die die Angebotsqualität misst. Beide Komponenten sind durch einen Faktor λ ∈ [0, 1] gewichtet. Nebenbedingung (i) stellt für alle OD-Paare (s, t) sicher, dass die Nachfrage dst von s nach t erfüllt wird. Die Kapazitätsbedingung (ii) garantiert für alle Linienkanten im Change-and-Go-Graphen, dass die Kapazität der Linie auf dieser Kante ausreicht, um das Passagieraufkommen auf dieser Kante zu erfüllen. Die letzte Nebenbedingung (iii) stellt sicher, dass pro Linie nur eine Frequenz gewählt werden kann.
2.3 Anforderungen in Potsdam und Umsetzung
Wir beschreiben im Folgenden die Anforderungen, die bei der Entwicklung des Linienplans 2010 für Potsdam aufgetreten sind. Diese sind beispielhaft für die Behandlung betrieblicher, betriebswirtschaftlicher und qualitativer Aspekte in dieser Fragestellung.
Der Verkehrsbetrieb in Potsdam (ViP) betreibt etwa 20 Bus- und Straßenbahnlinien. Es besteht ein Grundtakt von 20 Minuten, von dem in Randgebieten auch auf einen 30 Minutentakt oder sogar 60 Minutentakt abgewichen werden darf. Für Fahrten von 6 bis 9 Uhr morgens (3 Stunden) ergeben sich Taktfrequenzen von F = {3, 6, 9, 18}. Weiterhin schreibt der Nahverkehrsplan eine Mindestbedienhäufigkeit an einigen Stationen vor. Diese Mindestbedienhäufigkeit kann ein 10, 20, 30 oder 60 Minutentakt sein, wobei der 10 und 30 Minutentakt auch mit je zwei Linien im 20 bzw. 60 Minutentakt erfüllt werden kann, die anderen Takte müssen durch eine Linie mit mindestens diesem Takt erfüllt werden. Dies ergibt für unser Modell folgende zusätzliche Nebenbedingungen:
Formel (1) siehe PDF.
Hierbei bezeichnet V1 die Menge der Knoten mit einer Mindestbedienhäufigkeit von 60 oder 20 Minuten und V2 die Menge der Knoten mit einer Mindestbedienhäufigkeit von 30 oder 10 Minuten.
Die Wichtigkeit der Straßenbahn wird als etwas höher angesehen als die des Busses. Ein Grund dafür ist, dass offenbar die Straßenbahn als Verkehrsmittel beliebter ist als der Bus. Daher sollte an allen Haltestellen, die sowohl vom Bus als auch von der Straßenbahn angefahren werden können, die Mindestbedienhäufigkeitsbedingung allein durch die Straßenbahn erfüllt werden. Desweiteren soll für die Straßenbahn nicht vom 20 Minuten Grundtakt abgewichen werden und ein Parallelverkehr von Bussen ausgeschlossen werden. Diese Anforderungen können durch geeignete Modifikation der Bedingungen (1) und durch das Verbieten von Buslinien parallel zur Straßenbahn modelliert werden.
Für die Generierung von neuen Linien wurden neben erlaubten Abbiegerelationen noch einige Bedingungen gestellt, die einen robusten Betrieb begünstigen. Dazu zählen z. B. eine maximale Fahrzeit pro Richtung, das Sperren von Bahnübergängen und die Definition von wichtigen Umsteigestationen, von denen mindestens eine in jeder Linie enthalten sein muss. Eine Enumerierung ergab, dass es unter diesen Bedingungen insgesamt nicht mehr als 3500 Linien gibt. Somit war es möglich mit allen potenziellen Linien den Change-and-Go-Graphen aufzubauen und somit mit allen potenziell möglichen Linien zu rechnen. Allerdings kann die Berechnung von sehr guten Lösungen mitunter mehrere Tage dauern.
Bild 2: Paretokurve. Abhängig von dem Wert eines Parameters (Werte zwischen 0 und 1) werden Kosten und Fahrzeiten (in Minuten) für die Zielfunktion prozentual gewichtet. Ein Wert von 0 bedeutet, nur die Fahrzeiten sind wichtig und die Kosten unwichtig, ein Wert von 1 bedeutet das Gegenteil. Die Gesamtfahrzeit ist in Minuten angegeben.
Das Ziel der Optimierung ist einen Linienplan zu bestimmen, der möglichst geringe Betriebskosten nach sich zieht und die Fahrzeiten und die Anzahl der Umstiege der Passagiere minimiert. ViP kalkuliert mit Kosten pro gefahrenem Kilometer, um die zu erwartenden Kosten aus der Umlauf- und Dienstplanung abzuschätzen. Diese Vorgehensweise entspricht genau den Annahmen unseres Modells. Darüberhinaus haben wir einen Fixkostenanteil verwendet, um die Anzahl der Linien in einer Lösung gering zu halten.
Zur Bewertung der Wechselwirkung zwischen den Zielkriterien Kosten und Fahrzeit (inkl. Umsteigezeiten) wurde eine bikriterielle Optimierung durchgeführt. Dabei wurde für alle prozentualen Gewichtungen der beiden Zielfunktionen (d. h. von 0% Kostenoptimierung, 100% Fahrzeitminimierung bis 100% Kostenoptimierung, 0% Fahrzeitminimierung) jeweils eine untere Schranke an die Gesamtbewertung des für die jeweilige Gewichtung optimalen Linienplans errechnet. Bild 2 zeigt die zugehörigen Paretokurven für Kosten (blau) und Fahrzeiten (grün); auf der Abszisse ist der Gewichtungsfaktor für die Kosten abzulesen. Ganz links (Kostengewichtung 0%) finden sich (untere Schranken an) Kosten und Fahrzeit der fahrzeitminimalen Lösung, rechts (Kostengewichtung 100%) (untere Schranken an) Kosten und Fahrzeit der kostenminimalen Lösung.
Die beiden Kurven zeigen, dass bei einer Verschiebung der Gewichtung von einer fahrzeitminimalen Lösung hin zu einer kostenminimalen Lösung die Fahrzeit zunächst nur geringfügig zunimmt, wohingegen die Kosten deutlicher abnehmen. Bei einer Gewichtung von 0.8 (80% Kosten, 20% Fahrzeit) weisen beide Kurven einen leichten Knick auf, der einen verstärkten Anstieg der Fahrzeit pro zusätzlich eingespartem Euro markiert. Diese Stelle ist in der Abbildung mit einer roten Linie markiert. Tatsächlich haben Berechnungen gezeigt, dass eine Gewichtung der Kosten von 80% zu Lösungen führt, deren Kosten in etwa im Zielbereich liegen. Daher haben wir diese Gewichtung für unsere Berechnungen gewählt.
3 Ergebnisse für Potsdam – Linienplan 2010
In diesem Abschnitt stellen wir nicht nur die mit dem Modell berechnete Lösung vor, die alle Bedingungen an einen Linienplan 2010 erfüllt, sondern führen auch eine detaillierte verkehrliche Bewertung dieser Lösung durch. Dazu vergleichen wir den von uns berechneten Linienplan mit einem von ViP per Hand berechneten Linienplan und zwei Linienplänen für die beiden Extremfälle, in denen ausschließlich die Kosten bzw. die Fahrzeiten minimiert werden. Dann führen wir eine kurze Detailbetrachtung von einzelnen Linien durch und analysieren einige Auslastungsprofile.
Tabelle 1: Kennzahlen der ViP- und ZIB-Lösung, der kostenminimalen und der fahrzeitminimalen Lösung. Kilometer, Kosten und Fahrzeiten sind für den Zeitraum von 6 bis 9 Uhr eines Tages bestimmt. Die Zeit ist in Sekunden·107gemessen. Umsteigen wird mit 15 Minuten pro Umstieg bewertet.
3.1 Einordnung – Kosten vs. Fahrzeit
Die mit unserem Modell berechnete Lösung nennen wir ZIB-Lösung. Wir vergleichen diese Lösung mit einem von ViP per Hand berechneten Linienplan (ViP-Lösung) sowie mit einer fahrzeitminimalen und einer kostenminimalen Lösung. Alle Linienpläne erfüllen alle Anforderungen an den Linienplan 2010. Die wichtigsten Kennzahlen dieser Lösungen sind in Tabelle 1 zusammengefasst. Eine Visualisierung der Netze ist in Bild 3 dargestellt.
Die kostenminimale Lösung ist optimal, d. h., 5688 Euro ist eine untere Schranke an die Kosten, die für den Betrieb eines Liniennetzes zwischen 6 und 9 Uhr entstehen, das alle vorgegebenen Bedingungen erfüllt. Die fahrzeitminimale Lösung ist nahezu optimal. Sie weicht um höchstens 0,4% von der Optimallösung ab, d. h., eine untere Schranke an die Gesamtreisezeit inklusive Umsteigezeit aller Passagier ist 6,06·10hoch7 Sekunden.
Die Lösungen von ViP und ZIB realisieren einen Kompromiss zwischen diesen Extremen. In beiden Fällen wird durch eine geringfügige Erhöhung der Fahrzeiten gegenüber dem Minimum eine erhebliche Kostenreduktion erzielt. Im Vergleich mit der kostenminimalen Lösung zeigt sich, dass durch den Mittelmehreinsatz vor allem das Umsteigen vermindert wird. Die ZIB- Lösung weist etwas günstigere Kennzahlen auf: Die Fahrzeiten sinken gegenüber der ViP- Lösung nochmals um 1% und die Kosten um 2.7%. Die Fahrzeitverbesserung ist insbesondere durch die Reduzierung von Umsteigern erreicht worden, siehe Tabelle 2. Die Kosten wurden durch die Verkürzung von Straßenbahnlinien verringert.
3.2 Linienanalyse
Die ZIB-Lösung unterscheidet sich von der ViP-Lösung nicht nur darin, dass einige Linien ausgetauscht wurden, sondern auch dadurch dass andere Linien verkürzt bzw. verlängert wurden. Gerade Verkürzungen und/oder Verlängerungen einzelner Linien sind Maßnahmen, die vergleichsweise einfach durchgeführt werden können und daher von besonderem Interesse sind. In diesem Zusammenhang ist es sinnvoll, auf die Auslastungsprofile einzelner Linien zu schauen. Diese geben für den gesamten Linienverlauf die Anzahl der transportierten Fahrgäste an. Allerdings sollte man sich bei einer Betrachtung von Auslastungsprofilen bewusst sein, dass eine auch geringfügige Linienänderung zu einer sehr unterschiedlichen Passagierroutenwahl führen kann. Daher müssen nicht die gleichen Passagiere eine nach einer Linienplanänderung unveränderte Linie nutzen. Dennoch stellen Auslastungsprofile einen guten Indikator dar, wie sich Linienänderungen auswirken können. Wir stellen hier zwei Beispiele vor.
Tabelle 2: Umsteiger in den vier Liniennetzen. Die Zahlen geben an wie viele Passagiere 0-mal, 1-mal, usw. umsteigen müssen. Die Annahme ist hierbei, dass die Passagiere auf dem für sie kürzesten Weg fahren (Umsteigestrafe von 15 Minuten), d.h., es kann einen Weg geben, der weniger Umstiege hat, aber dafür etwas länger ist.
Die Linie 92 wurde in der ZIB-Lösung zu der Variante new13 verkürzt. Das Betreiben der Linie 92 statt der verkürzten Variante new13 bedeutet einen Kostenanstieg um 224 Euro (2.9%) und eine Fahrzeitverringerung von 6.1927·10hoch7 auf 6.1852·10hoch7 Sekunden (0.12%). In Bild 4 ist die Auslastung der Linie 92 für die ViP-Lösung und der verkürzten Variante new13 für die ZIB-Lösung dargestellt. Man sieht, dass die Auslastung in der ViP-Lösung in den letzten Stationen nicht sehr hoch ist. In der verkürzten Variante der ZIB-Lösung nimmt die Auslastung zum Ende noch etwas mehr ab. Die Passagiere, die in Richtung Marie-Juchacz-Str. fahren, nehmen für diesen Abschnitt die Linie 96. Dies kann man an der höheren Auslastung der Linie 96 in Bild 5 erkennen.
Bild 4: Links: Auslastung der Linie 92 in der ViP-Lösung. Die x-Achse repräsentiert die Stationen von Kirschallee bis Marie-Juchacz-Str. Rechts: Auslastung einer verkürztenVariante in der ZIB-Lösung. Linie new13 geht von Bisamkiez bis Kirschallee.
Bild 5: Auslastung der Linie 96 im Vergleich. Links: ViP-Lösung. Rechts: ZIB-Lösung. Die x-Achse repräsentiert die Stationen von Viereckremise bis Marie-Juchacz-Str.
Die Linie 698 wird in der ZIB-Lösung zu der Variante new13832 verlängert. Bei Wahl von Linie 698 statt new13832 sinken die Kosten um 85 Euro (1.1%) und die Fahrzeit steigt von 6.1927·10hoch7 auf 6.2012·10hoch7 Sekunden (0.14%), siehe das Auslastungsprofil in Bild 6.
4 Fazit
Wir haben in diesem Artikel anhand einer Fallstudie dargestellt, wie die Berechnung eines Linienplans mit mathematischen Optimierungsmethoden durchgeführt werden kann. Das Modell beinhaltet als Zielfunktion eine gewichtete Summe aus Fahrzeit und Kosten und ist daher insbesondere auch für die Berechnung verschiedener Fahrzeit-Kosten-Gewichtungen bzw. zur Bestimmung von minimalen Kosten und minimalen Fahrzeiten anwendbar. Wichtige praktische Anforderungen sind Mindestbedienhäufigkeiten an wichtigen Stationen zur Erfüllung einer Daseinsvorsorge, die Einhaltung von bestimmten Konstruktionsregeln für „neue“ Linien einschließlich einer Vorgabe von möglichen Taktfrequenzen für die Linien. Diese Vorgaben können mit unserem Modell abgedeckt werden. Durch einen Vergleich der berechneten Lösung mit einem handgeplanten Liniennetz konnte nachgewiesen werden, dass bei geeigneter Datenversorgung und Parametrisierung mit Optimierungstools Linienpläne berechnet werden können, die einer Handplanung mindestens gleichkommen.
Bild 6: Links: Auslastung der Linie 698 in der ViP-Lösung von Kirschallee bis Lerchensteig/kleingartenanlage. Rechts: Auslastung der Linie new13832 von Kirschallee bis Alter Markt. Die Linie new13832 ist eine längere Variante von 698.
Literatur
[1] Borndörfer, R.; Neumann, M. Models for line planning with transfers. ZIB-Report ZR 10-11, ZIB, 2010.
[2] Borndörfer, R.; Neumann, M.; Pfetsch, M. E. Angebotsplanung im öffentlichen Nahverkehr. In HEUREKA’08. FGSV Verlag, 2008.
[3] Borndörfer, R.; Grötschel, M.; Pfetsch, M. E. A column-generation approach to line planning in public transport. Transportation Sci., 41(1):123–132, 2007.
[4] Borndörfer, R.; Grötschel, M.; Pfetsch, M. E. Models for line planning in public transport. In Hickman, M.; Mirchandani, P.; Voß, S. (Hrsg.), Computer-aided Systems in Public Transport, Band 600 von Lecture Notes in Economics and Mathematical Systems, S. 363–378. Springer-Verlag, 2008.
[5] Bouma, A.; Oltrogge, C. Linienplanung und Simulation für öffentliche Verkehrswege in Praxis und Theorie. Eisenbahntechnische Rundschau, 43(6):369–378, 1994.
[6] Bussieck, M. R. Optimal lines in public rail transport. Dissertation, TU Braunschweig, 1997.
[7] Bussieck, M. R.; Kreuzer, P.; Zimmermann, U. T. Optimal lines for railway systems. Eur. J. Oper. Res., 96(1):54–63, 1997.
[8] Bussieck, M. R.; Lindner, T.; Lübbecke, M. E. A fast algorithm for near optimal line plans. Math. Methods Oper. Res., 59(2), 2004.
[9] Ceder, A.; Israeli, Y. Scheduling considerations in designing transit routes at the network level. In Desrochers, M.; Rousseau, J.-M. (Hrsg.), Proc. of the Fifth International Workshop on Computer-Aided Scheduling of Public Transport (CASPT), Montréal, Canada, 1990, Band 386 von Lecture Notes in Economics and Mathematical Systems, S. 113–136. Springer-Verlag, Berlin, Heidelberg, 1992.
[10] Claessens, M. T.; van Dijk, N. M.; Zwaneveld, P. J. Cost optimal allocation of rail passenger lines. Eur. J. Oper. Res., 110(3):474–489, 1998.
[11] Goossens, J.-W. H. M.; van Hoesel, S.; Kroon, L. G. A branch-and-cut approach for solving railway line-planning problems. Transportation Sci., 38(3):379–393, 2004.
[12] Nachtigall, K.; Jerosch, K. Simultaneous network line planning and traffic assignment. In Fischetti, M.; Widmayer, P. (Hrsg.), ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, Dagstuhl, 2008. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[13] ptv AG. Visum website. http://www.ptv.de/cgi-bin/traffic/traf_visum.pl.
[14] Schöbel, A.; Scholl, S. Line planning with minimal traveling time. In Kroon, L. G.; Möhring, R. H. (Hrsg.), 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, Dagstuhl, 2006. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl.
[15] Scholl, S. Customer-Oriented Line Planning. Dissertation, Universität Göttingen, 2005. |
