Accueil▸IA et Machine Learning▸Prédicteur d'itinéraire & d'heure d'arrivée

🚌 Prédicteur d'itinéraire & d'heure d'arrivée

Simulateur de transport interactif : des bus se déplacent sur un vrai réseau de lignes tandis que l'algorithme de Dijkstra calcule les plus courts chemins et qu'un modèle en direct prédit les heures d'arrivée face à la réalité — observez l'erreur de prédiction se réduire à mesure que les bus approchent.

IA et Machine Learning3DAvancé60 FPS

À propos du prédicteur d'itinéraire & d'heure d'arrivée

Chaque fois qu'une appli de transport vous annonce qu'un bus est « à 4 minutes », deux branches très différentes de l'informatique travaillent ensemble en coulisses. La première est la recherche de plus court chemin : étant donné un réseau d'arrêts et de temps de trajet, trouver l'itinéraire le plus rapide de A à B. La seconde est la prédiction d'arrivée en direct : à partir du comportement réel récent du trafic, estimer combien de temps prendra vraiment le prochain tronçon d'un trajet — car un horaire imprimé n'est jamais qu'une estimation de départ. Cette simulation implémente les deux, pour de vrai, sur un réseau de lignes de 16 arrêts.

Cliquez sur deux arrêts quelconques pour lancer une véritable recherche de plus court chemin par l'algorithme de Dijkstra entre eux : observez le front des arrêts « réglés » s'étendre et l'itinéraire final se surligner une fois trouvé. Pendant ce temps, jusqu'à quatre bus tournent en continu sur des lignes fixes. Chaque arête du réseau a un facteur de trafic fluctuant aléatoirement, et un modèle de moyenne mobile exponentiellement pondérée en direct apprend le temps de trajet actuel de chaque arête à partir de chaque bus qui la traverse — de sorte que les heures d'arrivée prédites s'adaptent aux conditions plutôt que de suivre un horaire fixe. Un graphique en continu suit l'écart entre les prédictions et la réalité à mesure que la volatilité du trafic change.

Questions fréquentes

Comment l'algorithme de Dijkstra calcule-t-il réellement l'itinéraire le plus court ?

L'algorithme de Dijkstra conserve une distance connue courante vers chaque arrêt, commençant à 0 pour la source et à l'infini partout ailleurs. À chaque étape, il choisit l'arrêt non visité avec la plus petite distance connue, le marque comme réglé, et relâche chaque arête qui en sort : si passer par l'arrêt réglé donne un chemin plus court vers un voisin que le meilleur actuel de ce voisin, ce meilleur et son prédécesseur sont mis à jour. Comme les arrêts sont toujours réglés par ordre de distance croissante, une fois qu'un arrêt est réglé, sa distance ne peut plus jamais s'améliorer, et l'algorithme s'arrête dès que la destination est réglée. Remonter les pointeurs de prédécesseur depuis la destination reconstitue le véritable plus court chemin.

Qu'est-ce qu'un modèle d'ETA à moyenne mobile exponentiellement pondérée, et pourquoi bat-il un horaire statique ?

Un horaire statique suppose que chaque trajet le long d'un segment prend la même durée programmée, quelles que soient les conditions. Une moyenne mobile exponentiellement pondérée (EWMA) conserve à la place une estimation courante par arête et la met à jour chaque fois qu'un bus traverse réellement cette arête : nouvelle_estimation = α · temps_observé + (1 − α) · ancienne_estimation. Comme α est compris entre 0 et 1, les observations récentes comptent plus que les anciennes, si bien que l'estimation suit les conditions actuelles tout en lissant le bruit ponctuel d'un trajet inhabituellement rapide ou lent. Cette simulation utilise α = 0,3.

Pourquoi l'erreur de prédiction s'envole-t-elle quand on augmente la volatilité du trafic ?

Le modèle EWMA ne peut réagir qu'après avoir observé un trajet terminé, il s'agit donc fondamentalement d'un indicateur retardé. Lorsque le curseur de volatilité augmente l'ampleur des variations des facteurs de trafic par arête, l'écart entre « ce que le modèle a appris en dernier » et « ce qui se passe réellement en ce moment » se creuse, si bien que l'erreur absolue moyenne entre les heures d'arrivée prédites et réelles augmente.

Pourquoi le plus court chemin change-t-il alors que la carte elle-même ne bouge jamais ?

Cette simulation exécute Dijkstra en utilisant le temps de trajet prédit en direct par l'EWMA de chaque arête plutôt que sa distance physique fixe, si bien qu'une requête pour les deux mêmes arrêts peut renvoyer un itinéraire différent une fois que les conditions de trafic ont suffisamment modifié les poids appris pour qu'un chemin auparavant plus lent devienne le plus rapide.

⚙ Sous le capot

Des bus se déplacent sur un réseau de lignes tandis que l'algorithme de Dijkstra calcule les plus courts chemins et qu'un modèle en direct prédit les heures d'arrivée.

Three.jsWebGLAIMachine Learning

3D · Moteur de rendu Three.js / WebGL · cible 60 FPS · s'exécute entièrement côté client, sans installation