Liniennetz

In einer kleinen Stadt fahren drei Linien: blau (von Station A über M nach Y und zurück), grün (B-N-Z und zurück) und orange (L-M-N und zurück).

Alle Linien fahren im 10-Minuten-Takt.

Taktfahrplanung

Die Aufgabe der Taktfahrplanung ist es, für jede Linie an jeder ihrer Stationen Ankunfts- und Abfahrtszeiten festzulegen. Weil sich bei einem 10-Minuten-Takt der Fahrplan alle 10 Minuten wiederholt, beschränken wir uns auf ganzzahlige Ankunfts- bzw. Abfahrtsminuten 0, 1, 2, 3, ..., 9. In der interaktiven Visualisierung sind Ankunftsereignisse als weiße Kreise mit farbiger Umrandung und Abfahrtsereignisse als gefüllte Kreise dargestellt.

Zwischen diesen Abfahrts- und Ankunftsereignissen bestehen Beziehungen, die in der Visualisierung als Pfeile dargestellt werden:

• Fahren (farbig, durchgezogen): Fahren auf einer Linie von einer Abfahrt zur nächsten Ankunft
• Halten (farbig, gepunktet): Halten in einer Station zwischen Ankunft und Abfahrt
• Wenden (farbig, gestrichelt): Wenden am Endpunkt der Linie
• Umsteigen (grau, gepunktet): Umsteigen von einer Linie (Ankunft) zu einer anderen (Abfahrt)

Bei der Erstellung eines Fahrplans ist eines unabdingbar: Die gewählten Ankunfts- und Abfahrzeiten müssen zu den Fahr-, Halte-, Wende- und Umsteigezeiten passen!

Für alle diese Zeiten gelten untere und obere Schranken wie im folgenden Bild dargestellt:

Zum Beispiel muss die Fahrt der blauen Linie von A (Station oben) nach M (in der Mitte) exakt 6 Minuten dauern. An jeder Station sollen die Fahrzeuge einer Linie mindestens eine, aber höchstens fünf Minuten halten usw.

Aufgabe 1

Können Sie einen Fahrplan finden – d. h., für jedes Ankunfts- und Abfahrtsereignis Zeiten zwischen 0 und 9 bestimmen – sodass alle Bedingungen an die Fahr-, Halte-, Wende- und Umsteigezeiten erfüllt sind? Dazu können Sie die in die runden Knoten klicken und die Minute eingeben. Sobald eine Schranke verletzt wird, färbt sich der entsprechende Pfeil rot. Das Ziel ist nun, solche Zahlen zu finden, sodass kein Pfeil mehr rot ist. Die Pfeile sind mit der von der aktuellen Abfahrt- bzw. Ankunftsminute bestimmten Dauer beschriftet.

Optimierung

Nicht alle Fahrpläne sind gleich gut. Sobald ein zulässiger Fahrplan für die entsprechende Route gefunden wurde, wird rechts angezeigt, wie lange eine Fahrt z. B. von Y nach L dauert. Das Ziel ist nun einen solchen Fahrplan zu finden, bei dem die Gesamtdauer für alle rechts aufgelisteten Strecken so klein wie möglich ist.

Aufgabe 2

Finden Sie einen Taktfahrplan, bei dem die Fahrgäste so schnell wie möglich an ihr Ziel kommen. Der Wert hinter "Total" sollte also kleinstmöglich sein!

Lösung

Ein optimaler Taktfahrplan ist hier zu sehen.

Hintergrund

Finden Sie es schwierig, überhaupt einen Fahrplan zu finden, bei dem keine Kante rot ist? Und stellen Sie auch fest, dass wenn man für die Minimerung der Reisezeiten einen Pfeil besonders kurz wählt, dass oft woanders Probleme entstehen? Seien Sie beruhigt, denn sowohl Taktfahrplanerstellung als auch -optimierung gehören zur Klasse der sogenannten NP-schweren Probleme. Dies sind mathematische Probleme, die als "schwer" gelten und für die keine effiziente Lösungsmethode bekannt ist. Im MobilityLab am Zuse-Institut Berlin beschäftigen wir uns unter anderem mit der Frage, wie trotzdem in realistischen Szenarien Fahrpläne mithilfe intelligenter Algorithmen auch praktisch optimiert werden können. Dies gelingt aber nur durch ein fundiertes theoretisches Verständnis der mathematischen Struktur von Fahrplänen. Hier gibt es zum Beispiel auch Bezüge zur Geometrie: Ein wichtiger Baustein ist z. B. das von allen zulässigen Fahrplänen aufgespannte Polyeder, wie es im folgenden Bild zu sehen ist.