26 cantons en 24 heures: un algorithme à la rescousse

17 heures et 19 minutes. C’est le record à battre détenu par quatre Tessinois et réalisé l’an dernier. En un peu plus de 17 heures, ils ont réussi à mettre le pied dans chaque canton suisse en utilisant exclusivement les transports publics. Un défi lancé en 2015 par Nicolas Rossé, journaliste de la RTS qui, à l’époque, avait bouclé le tour en 19h46. Il faut dire que le tunnel de base du Gothard n’était pas encore ouvert. Vendredi, deux doctorants et des étudiants de l’EPFL vont tenter l’exploit en 16h54. A noter que pour la première fois l’itinéraire optimal a été établi par un algorithme, et non à la main.

Avant d’implémenter l’algorithme, il a fallu télécharger l’ensemble des données géographiques nécessaires, soit les gares (22 080 en comptant les arrêts de bus), les frontières géographiques des cantons et bien sûr les horaires de trains. Les chercheurs ont ensuite réduit la complexité en identifiant des gares «remarquables», c’est-à-dire potentiellement intéressantes pour changer de train (110). Ils ont ensuite téléchargé la liste de tous les trains traversant ces gares avec leurs horaires et regardé par quelles gares ils passaient afin de maximiser les traversées de canton. C’est à cette étape-là qu’il a fallu concevoir, puis implémenter un algorithme pour trouver une solution optimale. L’ordinateur a mouliné pendant 10 jours.

Quelques détails qui comptent

«Lorsque notre logiciel d’optimisation nous a donné une solution, la première (bonne) surprise a été le temps de parcours: 16h54. Il est donc possible de battre le record. Pas de beaucoup, grâce au travail de nos prédécesseurs, et à la redondance du réseau Suisse, mais assez pour dire que nous avons battu le record, avance Emmanuel Clédat, doctorant au Laboratoire de topométrie. La seconde surprise a été la place du Tessin dans notre itinéraire. Alors que nous pensions que ce canton serait la fin du parcours, ou une antenne (c’est-à-dire qu’il faut faire un aller-retour pour y accéder), il constitue une étape pour atteindre le canton des Grisons. La preuve que le canton 100% italophone n’est pas à l’écart des grands axes de communications de la Confédération!»

Le départ est fixé à St-Maurice (VS) à 5h24 et le périple se termine à Jakobsbad (AI) à 22h18. L’itinéraire va chercher les enclaves cantonales pour éviter les détours et est pimenté de quelques difficultés. Dans la gare d’Alpnachstad (dans le demi-canton de Obwalden) par exemple, les voyageurs ont 0 minute pour changer de train… «Les précédents vainqueurs de ce défi ont dû s’y reprendre à deux fois pour réussir leurs exploits, nous courons aussi le risque de devoir faire plusieurs essais avant de réussir», rappelle Dirk Lauinger, doctorant à la Chaire d’analyse de risque et d’optimisation.

L’envie de prendre le train

Dirk Lauinger conduit sa thèse sur l’optimisation des interactions entre des véhicules électriques et le réseau électrique tandis que son colocataire Emmanuel Clédat, avec lequel il s’est lancé ce défi, travaille sur la vision par ordinateur. Leur motivation n’est donc en rien liée avec leur doctorat, mais guidée avant tout par l’envie et le plaisir de voyager en train. Plusieurs étudiants se sont joints à eux, aussi attirés par le goût du défi.