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.

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.

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).

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.

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–21–18–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.

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