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

[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