Am Anfang stand ein Kunstprojekt. Der österreichische Fotograf David Kretz arbeitete in Berlin am Bard College. Hier kam ihm die Idee, alle S-Bahnhöfe der Stadt zu fotografieren und daraus eine Collage zu basteln. Ein zeitaufwendiges Vorhaben! Wo sollte man anfangen, wie sollte man fahren? In einem ersten Versuch und nach einer von ihm „händisch“ berechneten Strecke brauchte er über 17 Stunden. Auch das war schon eine Rekordzeit, David Kretz aber zu langsam.

Glücklicherweise hatte der Künstler bereits von Rekordversuchen aus anderen Städten gehört. Dabei ging es immer darum, bestimmte Strecken in einer möglichst schnellen Zeit abzufahren. Also fragte er den Mathematikprofessor Ralf Borndörfer vom Berliner Zuse-Institut (ZIB): Wie schaffe ich es am schnellsten, alle Strecken und damit alle Bahnhöfe abzufahren? Borndörfers Fachgebiet ist die Optimierung sehr schwieriger Wege-Probleme, deren Grundlage das in diesem Blog schon beschriebene Problem des „Travelling Salesman“ (s. Summa vom 26. Juli 2017) ist. Der Mathematiker war also genau der richtige Ansprechpartner, um das Problem des Künstlers zu lösen.

Prof. Borndörfer fand, dass dieses Problem ein gutes Projekt für die niederländische Studentin Loes Knoben sei. Im Rahmen eines Erasmus-Studium war die Niederländerin aus Twente gerade zu einem Praktikumsaufenthalt am ZIB. Gemeinsam mit den Wissenschaftlichen MitarbeiterInnen Niels Lindner und Isabel Beckenbach ging sie das Problem an. Die konkrete Aufgabenstellung lautete, dass jede S-Bahnstation im Netz A,B,C und jede Verbindung zwischen diesen Stationen mindestens einmal abgefahren werden musste. Anfang des Jahres 2015 war es dann soweit. Die drei hatten eine Software entwickelt, die tatsächlich die optimale und damit die schnellste Strecke berechnet hatte. 13 Stunden und 44 Minuten stand als Zeit fest, die man braucht, um alle Berliner S-Bahnlinien vollständig abzufahren und alle Bahnhöfe zu erreichen. Schneller geht es nicht!

Wie schwer diese Aufgabe ist, kann man an diesen absoluten Zahlen erkennen: Das Berliner S-Bahn-Netz hat 171 Strecken mit einer Gesamtlänge von 331,5 Kilometern. An diesen Strecken sind insgesamt 166 Stationen aufgereiht. Außerdem gibt es Verbindungen, bei denen die Züge nur im Abstand von 20 bis sogar 40 Minuten verkehren. Wer einen Zug verpasst, muss also lange Wartezeiten in Kauf nehmen!

Am 10. Januar 2015 packten die MathematikerInnen und David Kretz schließlich ihre Rucksäcke mit genug Reiseproviant und fuhren los. Allerdings kam ihnen „Felix“ dazwischen. Der Orkan mit dem freundlichen Namen war nämlich der Ansicht, dass er Bäume entwurzeln musste, die er dann auf einige Gleise der S-Bahn warf. Zu dem Zeitpunkt war das Team jedoch bereits etwa sieben Stunden unterwegs. „Da war es uns dann doch zu blöde aufzugeben. Allerdings war uns da schon bewusst, dass wir auf Grund der Sturmschäden die optimale Zeit nicht erreichen können“, erinnert sich Niels Lindner. Dennoch war am Ende der Fahrt mit 15 Stunden und vier Minuten ein neuer Weltrekord erreicht. Der alte von David Kretz 2014 aufgestellte Rekord lag bei 17 Stunden und einer Minute. Auf einen Eintrag ins Guinness-Buch der Rekorde hofft das niederländisch-österreichisch-deutsche Team gespannt.

Um ins Guinness-Buch zu kommen war ein zusätzlicher fast mathematisch geplanter Aufwand nötig. In einem Interview mit der Zeitschrift „jetzt“ beschreibt Loes Knoben das so: “Wir haben an jeder Station ein Foto von dem Stationsnamen gemacht, das mit einem Zeitstempel versehen ist. Anfangs war das noch sehr stressig, da man an jeder Station schnell rausspringen musste. Mit der Zeit sind war aber immer besser darin geworden. Außerdem haben wir ein Logbuch geführt, die Zugnummern und die genauen Abfahrts- und Ankunftszeiten dokumentiert. Teilweise haben wir uns auch von dem Zugführer unterschreiben lassen, dass wir wirklich in dem Zug waren.“

Nicht nur in Berlin machen MathematikerInnen immer wieder Versuche, die Netze öffentlicher Verkehrsmittel in einer möglichst schnellen, optimierten Zeit zu befahren. Aus dem Jahr 2014 stammt ein Rekord für die Berliner U-Bahn mit 7 Stunden 33 Minuten und 15 Sekunden. In London wurde sogar schon 2013 der Rekord mit 16 Stunden 20 Minuten und 27 Sekunden für alle Londoner U-Bahnstationen aufgestellt und in New York liegt der Rekord für die dortigen U-Bahnstationen bei 22 Stunden 26 Minuten und 2 Sekunden. So war die weltweite Resonanz auf die Fahrt der Berliner groß. Beispielsweise meldete sich der Rekordinhaber aus New York. Er erzählte, dass er sich auch schon mal an der Berliner U-Bahn versucht habe. Bisher jedoch lange nicht so perfekt wie die Berliner, denn er hatte alles manuell kalkuliert. jetzt würde er es gerne mit dem Programm der Berliner MathematikerInnen versuchen und hat bereits sein Interesse angekündigt, bei einer eventuellen nächsten Fahrt dabei zu sein.

Loes Knoben, Niels Lindner und Isabel Beckenbach hatten kurz überlegt, die Strecken der U-Bahn zu nehmen. Aber dann war da ja zum einen der Wunsch von David Kretz die S-Bahn-Höfe später zu fotografieren und dann waren auch noch ganz pragmatische Gründe bei der Wahl ausschlaggebend, wie Loes Knoben erklärt: „Wir dachten, S-Bahn ist netter als U-Bahn, da sieht man wenigstens etwas von der Stadt. Außerdem ist die S-Bahn etwas komplizierter zu berechnen, weil dort die Züge seltener fahren.“

Natürlich steckt hinter solchen Wettbewerben der wissenschaftliche Wunsch nach der Lösung mathematischer Probleme und zu zeigen, dass sie auch für „alltägliche“ Anwendungen von Bedeutung sind. Die benutzten mathematischen Optimierungsmethoden finden immer Anwendung, wenn es darum geht, optimale und schnelle Wege zu finden, also beispielsweise bei Fahrplänen, in der Logistik, beim Be- und Entladen in Speditionen oder Container-Häfen und vielem anderen mehr. Niels Lindner verweist darauf, dass das für den S-Bahn-Challenge neu entwickelte Programm geeignet ist, die Fahrpläne von allen öffentlichen Verkehrsnetzen einzugeben. „Wir haben einen bestehenden Fahrplan als Ausgangspunkt genommen, unsere Software auf diese Aufgabenstellung ausgerichtet und sie hierfür erstellt.“ Dabei kann man bei der öffentlich zugänglichen Nutzung der Software frei wählen, an welchem Bahnhof man die Fahrt beginnen möchte. Die Software berücksichtigt außerdem lange Umsteigezeiten, die Wartezeiten, wenn ein Zug verpasst wurde, oder auch – nicht unwichtig -Toilettenpausen. Niels Lindner ergänzt: „Die Berliner S-Bahn ist ja immer wieder in der Kritik, nicht ganz zuverlässig zu sein und so haben wir – so weit vorhersagbar – auch Verspätungen mit eingerechnet.

Neben dem Erfolg mit dem neuen Weltrekord hat die Fahrt allen Beteiligten auch großen Spaß gemacht. Noch keiner von ihnen hatte bisher die „komplette“ Stadt mit der S-Bahn erkundet. „Da sind wir manchmal in Ecken gekommen, die ich vorher überhaupt nicht kannte“, sagt Loes Knoben. Und auf die Frage, ob die vier die Reise noch einmal machen möchten kommt ein eindeutiges „Ja“. Allerdings müssten dann laut Niels Lindner einige Vorbedingungen stimmen: „Zu einen müssen wir neben unserer regulären Forschungsarbeit die nötige Zeit haben, zum anderen arbeitet Loes Knoben nun an der Uni in Utrecht und müsste extra nach Berlin kommen und – ganz wichtig – bei der S-Bahn dürfte es nicht allzu viele Fahrplaneinschränkungen und wenig Schienenersatzverkehr geben“.

Man kann den Weltrekordler jetzt nur die Daumen drücken und auf einen neuen S-Bahn-Challenge Rekord in Berlin hoffen. Die Vorgabe von 13 Stunden und 44 Minuten steht und es ist noch keinem gelungen zu beweisen, dass es schneller gehen könnte.