26 Kantone in 24 Stunden: Unterstützung durch einen Algorithmus

Artikel lesen
Verkehr
Algorithmen

Ein Team aus Doktorierenden und Studierenden der EPFL hat sich dem Swiss Train Challenge gestellt. Ihr Ziel? Mit den öffentlichen Verkehrsmitteln in weniger als 24 Stunden jeden Kanton betreten.

17 Stunden und 19 Minuten: Das war der von vier Tessinern im vergangenen Jahr aufgestellte Rekord, den es zu schlagen galt. Ihnen war es gelungen, in etwas mehr als 17 Stunden jeden Schweizer Kanton zu betreten und dabei ausschliesslich öffentliche Verkehrsmittel zu benutzen. Ins Leben gerufen wurde dieser Wettbewerb 2015 vom RTS-Journalisten Nicolas Rossé, der die Tour in 19 Stunden und 46 Minuten absolvierte. Allerdings war damals der Gotthard-Basistunnel noch nicht eröffnet. Am 7. September 2018 versuchten zwei Doktorierende und Studierende der EPFL, diese Spitzenleistung in 16 Stunden und 54 Minuten zu schaffen. Zum ersten Mal wurde die optimale Reisestrecke nicht von Hand, sondern von einem Algorithmus berechnet.

Vor der Programmierung des Algorithmus mussten alle notwendigen geografischen Daten, d.h. die Bahnhöfe (22’080 einschliesslich Bushaltestellen), die Kantonsgrenzen und natürlich die Fahrpläne heruntergeladen werden. Anschliessend reduzierten die Forscher die Komplexität, indem sie 110 «bemerkenswerte Bahnhöfe» identifizierten, d.h. solche, die für das Umsteigen potenziell interessant sind. Dann luden sie die Liste aller Züge, die diese Bahnhöfe bedienen, samt Fahrplänen herunter und schauten, welche Bahnhöfe sie anfuhren, um die Kantonsdurchquerungen zu maximieren. Bei diesem Schritt musste schliesslich ein Algorithmus entworfen und angewendet werden, um die optimale Lösung zu finden. Der Computer rechnete zehn Tage lang!

« Als unsere Optimierungssoftware eine Lösung ausspuckte, war die erste (positive) Überraschung die Gesamtfahrzeit: 16 Stunden und 54 Minuten. Es war also möglich, den Rekord zu brechen »

Wichtige Details

«Als unsere Optimierungssoftware eine Lösung ausspuckte, war die erste (positive) Überraschung die Gesamtfahrzeit: 16 Stunden und 54 Minuten. Es war also möglich, den Rekord zu brechen – zwar aufgrund der Arbeit unserer Vorgänger und der Redundanz des Schweizer Bahnnetzes nur knapp, aber genug, um sagen zu können, dass wir den Rekord geknackt haben», sagt Emmanuel Clédat, Doktorand am Labor für Topometrie (TOPO). «Die zweite Überraschung war die Position des Tessins innerhalb unserer Reisestrecke. Während wir dachten, dieser Kanton würde am Ende der Reise stehen oder eine Sackgasse bilden, d.h. dass der gleiche Weg hin und zurück genommen werden muss, stellte sich der Kanton als Etappe für die Reise nach Graubünden heraus. Dies beweist, dass der zu 100% italienischsprachige Kanton nicht abseits der grossen Verkehrswege der Schweiz liegt!»

Den Startpunkt bildet St-Maurice (VS) um 5:24 Uhr, und die Reise endet um 22:18 Uhr in Jakobsbad (AI). Die Reise nutzt kantonale Enklaven, um Umwege zu vermeiden, und ist gespickt mit Schwierigkeiten. Im Bahnhof Alpnachstad (OW) haben die Reisenden beispielsweise nur 0 Minuten Umsteigezeit. «Die früheren Gewinner des Wettbewerbs brauchten zwei Versuche, und auch wir liefen Gefahr, mehrere Anläufe nehmen zu müssen, um es zu schaffen», erklärt Dirk Lauinger, Doktorand am Lehrstuhl für Risikoanalyse und Optimierung (RAO).

Bahnbegeisterung

Dirk Lauinger schreibt eine Doktorarbeit über die Optimierung der Schnittstellen zwischen Elektrofahrzeugen und dem Stromnetz, während sein Mitbewohner Emmanuel Clédat, mit dem er sich der Herausforderung stellte, im Bereich Computer Vision arbeitet. Ihre Motivation hat folglich nichts mit ihrer Doktorarbeit, sondern vor allem mit ihrer Bahnbegeisterung zu tun. Mehrere andere, ebenfalls von der Lust auf diese Herausforderung angelockte Studierende schlossen sich ihnen an.

Am Tag X liess eine 20-minütige Verspätung bei der Ankunft in Bern den Versuch scheitern. Dennoch setzten die Doktoranden das Abenteuer fort, um zu beweisen, dass dank ihrer Methode der frühere Rekord geschlagen werden kann, wenn keine Anschlussprobleme auftreten. Sie kamen schliesslich um 23:18 Uhr in Jakobsbad an, nachdem sie die heiklen Punkte locker gemeistert hatten, und bewiesen so, dass ihr auf einem Algorithmus basierender Ansatz eine Reisestrecke herausgesucht hat, mit der der frühere Rekord des Swiss Train Challenge gebrochen und in 16 Stunden und 54 Minuten jeder Kanton betreten werden kann.

Emmanuel Clédat und Dirk Lauinger auf dem Weg zum Swiss Train Challenge

Scrollen
Forschung | 40 artikel