Durant un long trajet routier, vous consultez inévitablement l'écran de votre GPS pour estimer le temps restant. Cette prouesse technologique repose sur des mathématiques sophistiquées. La mathématicienne Ann Dooms, de la VUB, décrypte son fonctionnement.
Votre GPS, qu'il soit embarqué dans votre voiture ou sur smartphone, se localise partout dans le monde grâce à 24 satellites en orbite à environ 20 000 km d'altitude, effectuant une rotation complète autour de la Terre en 12 heures.
Chaque satellite émet un signal radio reçu par votre appareil, permettant de calculer la distance au satellite. Vous vous situez ainsi sur une sphère centrée sur ce satellite. Un seul satellite ne suffit pas : un second restreint les possibilités à un cercle (intersection des deux sphères), un troisième à deux points, et un quatrième détermine votre position unique en coordonnées latitude-longitude. En mouvement, cette position est recalculée en continu via la trilatération.
À partir de ces données, Google Maps, Waze et autres applications de navigation calculent votre itinéraire : routes à suivre, heure d'arrivée estimée. Elles s'appuient sur une carte mondiale des routes avec leurs coordonnées et longueurs, les limitations de vitesse, et les données de trafic issues des vitesses historiques des usagers par heure et par route.
Toutes ces informations forment un graphe : nœuds (villes, intersections, maisons) et arêtes (routes) pondérées par temps et distance.
Pour un itinéraire optimal (plus rapide ou plus court), l'algorithme de Edsger Dijkstra (1956) identifie le chemin de poids minimal, fournissant une liste précise de routes du départ à l'arrivée.
La théorie des graphes naquit d'un problème concret : en 1736, Leonhard Euler (1707-1783) analysa les sept ponts de Königsberg (aujourd'hui Kaliningrad). La ville, divisée par la rivière Pregel, posait la question d'un parcours piéton traversant chaque pont une fois et revenant au point de départ. Euler modélisa cela en graphe abstrait, prouvant l'impossibilité (degrés impairs des nœuds). Un cycle eulérien exige des degrés pairs. Une option "cycle d'Euler" dans Google Maps boosterait peut-être nos balades post-confinement !
