Calcul d'itinéraire : cours de SNT en seconde

Tu déverrouilles une trottinette en libre-service, tu repères ta destination, et l'application te trace un chemin en quelques instants. Ce tracé n'a rien de magique : un programme a comparé des possibilités et retenu la meilleure selon un critère précis.

Dans les applications de location de vélos ou de trottinettes à la minute, l'itinéraire s'affiche aussi bien pour rejoindre le véhicule que pour visualiser le trajet effectué ². Le programme de SNT place ce thème dans la continuité de la cartographie : il évoque la détermination d'un itinéraire avec OpenStreetMap ¹.

Ce cours répond à trois questions :

• Comment un ordinateur « voit » une carte de routes ?
• Quel problème mathématique se cache derrière un itinéraire ?
• Comment le refaire toi-même, à la main puis en Python ?

Tu t'appuies sur ce que tu connais déjà : la géolocalisation par satellite, qui donne la position de départ, et les cartes numériques, qui fournissent les routes.

Pourquoi parle-t-on de « problème » ? Entre deux points d'une ville, il existe presque toujours plusieurs façons de rouler : certaines sont longues, d'autres directes, d'autres encore pleines de détours. Choisir parmi elles, c'est résoudre un problème d'optimisation.

Un graphe, ici, c'est un schéma fait de points reliés par des traits. Tout le travail consiste donc à transformer la carte en un tel schéma, puis à chercher le meilleur parcours dessus.

La suite détaille cette transformation, appelée modélisation. C'est la même démarche que pour un problème de géométrie : on remplace la réalité par un modèle simple sur lequel on sait calculer.

Cette représentation oublie volontairement beaucoup de choses : la forme exacte des rues, les arbres, les magasins. On garde uniquement ce qui sert au calcul : qui est relié à qui, et à quel coût.

Une vraie carte de ville contient des milliers de sommets. Le principe reste identique, seule la quantité de calcul change. C'est pour cela qu'on confie la tâche à un programme.

Cette énumération fonctionne ici car le graphe est minuscule. Avec des milliers de sommets, le nombre de chemins devient gigantesque et on ne peut plus tout essayer. Les programmes de calcul d'itinéraire emploient alors des méthodes plus économes, qui évitent d'examiner les parcours manifestement mauvais. Ces méthodes dépassent le programme de seconde, mais l'idée à retenir est simple : le résultat est le même que si on avait tout comparé.

Le poids d'une arête n'est pas imposé. Selon l'usage, l'application attribue des poids différents au même graphe, et l'itinéraire proposé change.

En SNT, tu manipules un vrai calcul d'itinéraire en Python. La ressource d'accompagnement utilise la bibliothèque pyroutelib3, qui calcule des itinéraires à partir des cartes OpenStreetMap ². OpenStreetMap est la carte collaborative citée dans le programme pour la détermination d'un itinéraire ¹.

Le principe d'un tel programme tient en quatre idées :

1. on définit le point de départ et le point d'arrivée (par exemple par leurs coordonnées GPS, obtenues grâce à la géolocalisation) ;
2. la bibliothèque retrouve les sommets de la carte les plus proches de ces deux points ;
3. elle cherche le meilleur chemin entre eux ;
4. le programme affiche le résultat sur une carte.

Une méthode ne devient vraiment tienne qu'après l'avoir appliquée plusieurs fois. Reprenons-la sur un autre petit réseau, en la déroulant sans rien sauter. L'objectif : t'habituer à écrire proprement chaque étape, comme on le demande en contrôle.