Das Briefträgerproblem im Tramnetz der Stadt Zürich (2/3)

Anwendung auf das Tramnetz der Stadt Zürich

Der Graph unserer Aufgabenstellung (reduzierter Netzplan in Abbildung 1 bzw. als Graph in Abbildung 2 des letzten Posts) besteht aus 29 Knoten und 43 Kanten. Die Gewichte der Kanten entsprechen der Fahrzeit in Minuten und sind in Abbildung 2 den Kanten zugeordnet.

Die Anzahl ungerader Knoten (r) ist zehn (Knotennummern 1 bis 10, rot eingefärbt). Für diese zehn Knoten wird ein vollständiger Graph erstellt, d.h. jeder ungerade Knoten wird mit jedem anderen ungeraden Knoten durch eine Kante verbunden (Abbildung 3). Die Gewichte (Fahrzeiten) der Kanten entsprechen der kürzesten Verbindung zwischen den jeweiligen Knoten im ursprünglichen Graphen gemäss Abbildung 2.

Abb3

Abbildung 3: Vollständiger Graph für ungerade Knoten mit der kostenminimalen perfekten Paarung (fünf farbige Matchingkanten)

Beispiel (Abbildung 4): Von der Tunnelstrasse zum Bürkliplatz sind gemäss Abbildung 2 folgende zwei direkte Routen denkbar: Entweder Tunnelstrasse – Stockerstrasse – Paradeplatz – Bürkliplatz (violett in Abbildung 4) oder Tunnelstrasse – Bahnhof Enge – Bürkliplatz (orange in Abbildung 4). Die Fahrzeit der ersten Verbindung beträgt 5 Minuten (1 + 2 + 2), der zweiten Verbindung 6 Minuten (2 + 4). Im vollständigen Graphen in Abbildung 3 wird jeweils die kürzeste Verbindung, in diesem Fall also 5 Minuten, eingetragen.

Abb4

Abbildung 4: Beispiel kürzeste Verbindung für vollständigen Graphen

Die grösste Schwierigkeit der Aufgabe besteht nun darin, die kostenminimale perfekte Paarung zu finden. Dabei müssen fünf Kanten im vollständigen Graphen in Abbildung 3 ausgewählt werden, sodass jeweils zwei Knoten miteinander verbunden werden. Die Paarung ist so zu wählen, dass die Summe der Kantengewichte der verbundenen Knoten minimal wird. Es gibt 945 verschiedene Möglichkeiten, aus den zehn Knoten fünf Paare zu bilden. Für jede dieser Kombinationen können die Kantengewichte aufsummiert und schliesslich diejenige Kombination mit der minimalen Summe ausgewählt werden.

Die Lösung dieses Matching-Problems ist in Abbildung 3 dargestellt: Breit gezeichnete farbige Matchingkanten entsprechen jeweils einer Paarung. Folgende fünf Verbindungen müssen im reduzierten Netzplan demnach ergänzt werden (in Klammern sind jeweils die Zwischenknoten der kürzesten Verbindungen angegeben):

Bahnhof Enge – Tunnelstrasse (rot), Stockerstrasse – Stauffacher (blau), Bürkliplatz – Kantonsschule (violett, Bellevue – Kunsthaus), Bahnhofplatz/HB – Bahnhofstrasse (gelb, Bahnhofquai/HB) und Haldenegg – Leutschebach (grün, Schaffhauserplatz – Milchbuck – Sternen Oerlikon)

Mit der Ergänzung des ursprünglichen Graphen in Abbildung 2 durch die fünf Matchingkanten gemäss Abbildung 3 wurde der ursprünglich nicht-eulersche Graph eulersch gemacht und es existiert eine Eulertour (Abbildung 5).

Abb6

Abbildung 5: Eulerscher Graph; mit fünf Matchingkanten (farbig) ergänzert ursprünglicher Graph (reduzierter Netzplan)

Als letzter Schritt muss nun eine Eulertour gefunden werden, d.h. ein geschlossener Zyklus, der alle Kanten genau einmal enthält. Hierzu wird vom gewünschten Startknoten aus (z.B. 12) ein beliebiger Zyklus K gewählt, der jede Kante genau einmal enthält. Der rote Zyklus in Abbildung 6 ist ein solcher: Krot = (12, 4, 1, 2, 11, 1, 2, 3, 5, 6, 17, 7, 16, 5, 3, 16, 4, 12). Nun wird von einem beliebigen Knoten des roten Zyklus, an dem Kanten zusammenlaufen, die nicht Teil von Krot sind, ein neuer Zyklus gewählt: Kblau = (6, 18, 7, 18, 17, 9, 21, 18, 6). Auf die gleiche Weise entstehen die Zyklen Kgrün = (17, 15, 12, 15, 14, 13, 12), Kviolett = (9, 21, 23, 19, 20, 8, 15, 8, 19, 9), Kgelb = (21, 22, 24, 23, 24, 10, 27, 28, 29, 26, 23, 21) und Kmagenta = (24, 10, 25, 24). Die Teilzyklen werden am Schluss ineinander kopiert: der magentafarbene in den gelben, der grüne, violette und gelbe in den blauen und der blaue schliesslich in den roten.

Abb7

Abbildung 6: Herleitung Eulertour

Die so entstandene Eulertour beginnend beim Knoten 12 (Bellevue) ist nur eine von vielen möglichen und sieht wie folgt aus (in Abbildung 7 mit Haltestellennamen):

12–4–1–2–11–1–2–3–5–6–18–7–18–17–15–12–15–14–13–12–17–9–21–23–19–20–8–15–8–19–9–21–22–24–23–24–10–25–24–10–27–28–29–26–23–2118–6–17–7–16–5–3–16–4–12

In einem weiteren Schritt könnte auch noch die Zahl der Umsteigevorgänge optimiert und auf diese Weise die Dauer der Tour etwas reduziert werden. Diese Fragestellung aber wurde bei der vorliegenden Lösung des Problems ausgeklammert, da lediglich Strecken und keine Linien berücksichtigt wurden.

Abb9

Abbildung 7: Eulertour mit Start am Bellevue

 

Teil 1: Aufgabenstellung und allgemeine Lösung des Problems

Teil 2: Anwendung auf das Tramnetz der Stadt Zürich

Teil 3: Durchführung – Die Eulertour in Zahlen

Bence Tasnády

Bence Tasnády

Bence Tasnády (MSc) hat an der ETH Zürich Bauingenieurwissenschaften studiert mit Vertiefung im Bereich Verkehr. Er arbeitet seit 2010 bei EBP im Themenfeld Verkehrsgrundlagen und Verkehrstechnik des Geschäftsbereichs Verkehr als Projektleiter.

Bence Tasnády verfügt über grosse Erfahrung mit der Modellierung von Verkehrsflüssen und Einflussfaktoren, der komplexen Datenanalyse sowie der Erarbeitung von Kennzahlen und Indikatorensystemen für Bewertungen. Daneben berät er Kunden mittels Simulationen bei der Dimensionierung von Infrastrukturen und der Steuerung von Verkehrsmanagementsystemen.

Mail: bence.tasnady@ebp.ch

Bence Tasnády auf:

Das könnte Dich auch interessieren...

2 Antworten

  1. 1. Oktober 2015

    […] früheren Blogposts haben wir das Briefträgerproblem und das Konzept der Eulertour eingeführt und eine Lösung für das Tramnetz der Stadt Zürich präsentiert. Wie auf Twitter angekündigt, ging es dann am 20. Juni um 07:57 Uhr ab Bellevue auf Eulertour […]

  2. 13. April 2016

    […] Teil 2: Anwendung auf das Tramnetz der Stadt Zürich […]