Kategorie: Visualisierung

In zwei 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 durch Zürich! Wir sind mit GPS und Notizblock gereist und haben fleissig Daten gesammelt. In diesem Blogbeitrag möchten wir nun einen datenzentrierten Rückblick auf unsere Erlebnisse geben.

Durchführung – Die Eulertour in Zahlen

Nachdem das Briefträgerproblem für das Tramnetz der Stadt Zürich theoretisch gelöst war, ging es am 20. Juni 2015 an die praktische Umsetzung.

12 Stunden und 22 Minuten

später sind wir wieder am Bellevue gestanden (zum vierten Mal an diesem Tag). Die reine Fahrzeit hat 8 Stunden und 12 Minuten betragen, 4 Stunden und 10 Minuten haben wir an Haltestellen wartend verbracht.

Eulertour nach Uhrzeit

 

Statt einen Tag lang in der Stadt Zürich im Kreis herumzufahren, wären wir in der gleichen Zeit

mit dem Flugzeug bis Los Angeles oder Singapur gekommen,

mit dem Auto bis Kopenhagen, Warschau oder Barcelona,

mit dem Fahrrad bis Stuttgart und

zu Fuss bis Schaffhausen:

 

Insgesamt sind wir

147 km Tram gefahren,

wovon wir rund 57 km Strecke doppelt befahren haben. Diese doppelt befahrene Streckenlänge haben wir mit der Eulertour optimiert (und nicht etwa die Fahrzeit!). 47 km der Strecke entfielen auf die Sackgassen (z.B. Bahnhof Enge – Wollishofen) und waren somit nicht Teil des Optimierungsproblems:

 

Wir sind auf unserer Tour insgesamt

55 Mal umgestiegen.

An den Haltestellen Stauffacher, Central und Milchbuck sind wir am meisten umgestiegen (je 3-mal). Alle Umsteigeaufenthalte pro Haltestelle aufsummiert, sind wir am längsten am Central gestanden (fast 35 Minuten, allerdings wegen Umleitungen und den damit verbundenen Wartezeiten) und am kürzesten am Bahnhof Stettbach (nur eine halbe Minute):

 

 

Die längste Etappe dauerte 24 Minuten (Frankental – Bahnhofstrasse), die kürzeste 1 Minute (Bahnhof Enge/Bederstrasse – Bahnhof Enge). Im Mittel war eine Etappe fast 9 Minuten lang. Die längste Wartezeit am Stück verbrachten wir am Central (23 Minuten), die kürzeste am Bahnhof Enge (nur wenige Sekunden). Die mittlere Wartezeit betrug 4.5 Minuten.

 

Am längsten sind wir mit der Tramlinie 14 gefahren. Insgesamt 6 Mal, total 1 Stunde und 6 Minuten. Am kürzesten sind wir mit der Linie 15 gefahren (2 Mal, insgesamt 12 Minuten).

 

Eulertour nach Tramlinien

 

12 verschiedene Personen haben uns während unserer Fahrt durch die Stadt zumindest ein Stück begleitet. Nur 3 Stunden und 54 Minuten waren wir zu zweit unterwegs. Zeitweise waren wir 7 Personen auf Eulertour. Vom Arbeitskollegen gab es eine Lieferung zum Mittagessen:

Und von Eulertour-Fan Thomas Bruderer einen feinen Apfelstrudel:

 

Eulertour nach Anzahl Begleitpersonen

 

Im Mittel waren wir mit 12 km/h unterwegs –

mit 18 km/h, wenn wir die Haltezeiten nicht berücksichtigen. Das heisst, für die gleiche Strecke hätten wir zu Fuss etwas mehr als doppelt so lange gebraucht.

Eulertour nach Geschwindigkeit

 

Auf unserer Tour war gemäss GPS-Gerät (!!) der

tiefstgelegene Punkt auf 391 m.ü.M. (Bürkliplatz) und
der höchstgelegene auf 621 m.ü.M. (Zoo).

Werden nun entlang der Tour nur die Steigungen aufsummiert (und das Gefälle ignoriert), so haben wir etwa 1’500 Höhenmeter zurückgelegt. Damit ergibt sich der

Energieverbrauch unserer Eulertour von 1.61 kWh.

Dafür hätten wir uns beide etwa je 35 Minuten lang die Haare trockenföhnen können.

Eulertour nach Höhenlage

Noch ein paar mehr Eindrücke gibt’s auf dem nun stillen Eulertour-Twitterfeed. Vielen Dank an alle, die uns unterstützt und sich für die Eulertour interessiert haben (und schon über Ausdehnungen auf andere Städte oder das SBB-Netz nachdenken)!

Wir danken Marcel Rieser von senozon für die Erstellung der Videosequenzen!

Nadine Rieser + Bence Tasnády

 

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

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

[Bence Tasnády ist Spezialist in den Themenfeldern Verkehrsgrundlagen und Verkehrstechnik unseres Geschäftsbereichs Verkehr. In seinen Gastbeiträgen in den nächsten Tagen beschreibt er eine klassische Problemstellung für Graphen (vereinfacht: Netzwerke) und deren Lösung für eine Tramreise durch die Stadt Zürich. Die Lösung wird es ihm erlauben, das gesamte Tram-Streckennetz Zürichs in einer Tour abzufahren.]

Das Briefträgerproblem ist ein Begriff aus der Graphentheorie. Ein Briefträger hat die Häuser eines Quartiers mit Post zu beliefern und muss dabei jede Strasse mindestens einmal durchlaufen. Je nach Strassennetz kann es notwendig werden, einige Strassen erneut zu durchlaufen, ohne Post zu verteilen, um andere Teile des Zustellbezirks zu erreichen. Der Briefträger ist an einem geschlossenen Weg interessiert, der alle Strassen mindestens einmal enthält und minimale Länge hat.

 

Aufgabenstellung

Das Briefträgerproblem soll für das Tramnetz der Stadt Zürich gelöst werden. Die Aufgabenstellung lautet: Das gesamte Streckennetz (nicht Liniennetz) ist als geschlossene Tour (Endpunkt = Startpunkt) abzufahren und zwar in der Art, dass dabei möglichst wenige Strecken (gemessen in Minuten Fahrzeit gemäss Fahrplan) doppelt befahren werden. Da es lediglich um die Strecken geht, spielt es keine Rolle, mit welcher Linie und in welche Richtung eine bestimmte Strecke befahren wird. Mathematisch ausgedrückt ist eine Eulertour im Streckennetz der Stadt Zürich gesucht.

 

Reduktion des Problems

Für die Lösung des Problems kann das Streckennetz stark vereinfacht werden: Alle Haltestellen können ausgeklammert werden, die keine Knotenpunkte sind. Als Knotenpunkte sind Haltestellen zu verstehen, an denen auf andere Linien umgestiegen werden kann. Nicht als Knotenpunkte gelten Haltestellen mit Umsteigemöglichkeit, wenn zwei oder mehr Linien parallel geführt werden (z.B. Linien 2 und 4 zwischen Tiefenbrunnen und Bellevue). Im Folgenden wird der auf diese Weise vereinfachte Liniennetzplan als «vereinfachter Netzplan» bezeichnet (graue und schwarze Strecken in Abbildung 1). In einem nächsten Schritt können diejenigen Strecken aus dem Problem ausgeklammert werden, die Sackgassen bilden und damit unabhängig vom Optimierungsproblem doppelt befahren werden müssen. Diese Strecken sind im vereinfachten Netzplan grau dargestellt. Somit reduziert sich das zu lösende Optimierungsproblem auf das schwarz dargestellte Netz (Abbildung 1). Im Folgenden wird dieses Netz als «reduzierter Netzplan» bezeichnet. Für die Lösung des Problems muss nur dieser reduzierte Netzplan genauer betrachtet werden.

 

Allgemeine Lösung des Problems

Mathematisch betrachtet handelt es sich beim Tramstreckennetz der Stadt Zürich um einen ungerichteten, gewichteten Graphen (Abbildung 2). Gesucht ist die sogenannte Eulertour im Graphen. In einem eulerschen Graphen (zusammenhängender Graph mit geraden Knotengraden, d.h. ausschliesslich gerader Anzahl Kanten pro Knoten) entspricht die kürzeste Route einer Eulertour. Eine Eulertour ist eine Tour, die jede Kante genau einmal durchläuft. Ein Blick auf den reduzierten Netzplan in Abbildung 2 zeigt aber, dass es sich in diesem Fall nicht einen eulerschen Graphen handelt, da nicht alle Knotengrade gerade sind. Die rot eingefärbten Knoten weisen ungerade Knotengrade auf (jeweils drei Kanten pro Knoten).

Allgemein lässt sich das Problem lösen, indem man den nicht-eulerschen Graphen kostenminimal durch Einfügen weiterer Kanten eulersch macht und das Problem damit auf das Finden einer Eulertour zurückführt. Ist ein zusammenhängender Graph nicht eulersch, besitzt er r > 0 Knoten mit ungeradem Knotengrad. Da in jedem Graphen Knoten mit ungeradem Grad nur in gerader Anzahl auftreten, ist r immer gerade. Verbindet man jeweils zwei Knoten ungeraden Knotengrades durch eine zusätzliche Kante werden die ungeraden Knotengrade gerade, während die geraden Knotengrade gerade bleiben. Damit besitzt der ergänzte Graph ausschliesslich gerade Knotengrade und ist somit eulersch. Um den Graph eulersch zu machen müssen also insgesamt r/2 zusätzliche Kanten in den Graphen eingefügt werden.

Zur kostenminimalen Erweiterung des Graphen wird aus den Knoten ungeraden Grades ein vollständiger Graph (jeder Knoten ist mit jedem anderen Knoten durch eine Kante verbunden) erstellt. Als Kantengewicht wird jeweils die Fahrzeit des kürzesten Weges zwischen den beiden Knoten im ursprünglichen Graphen gewählt. In diesem vollständigen Graphen wird dann eine kostenminimale perfekte Paarung mit r/2 sogenannten Matchingkanten gesucht. Für jede eingefügte Matchingkante zwischen zwei Knoten werden im ursprünglichen (nicht-eulerschen) Graphen die Kanten des entsprechenden kürzesten Weges zwischen den beiden Knoten dupliziert. Auf diesen Kanten des Ursprungsgraphen muss der Briefträger also genau zweimal entlanggehen. Jede Eulertour in dem auf diese Weise erweiterten Graphen ist eine optimale Lösung des Briefträgerproblems.

 

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