Réalisation d’un outil de calcul du temps de parcours d’une route avec la prise en compte d’un trafic prédictif

Ce mémoire s'inscrit dans le domaine de l'informatique appliquée aux systèmes de transport et à la gestion du trafic routier. Il s'adresse principalement aux étudiants, chercheurs et professionnels intéressés par la modélisation du trafic, la prédiction des temps de parcours et le développement d'outils web intégrant ces fonctionnalités. L'objectif est de concevoir un service capable d'estimer, pour un trajet donné et une date future, le temps de parcours en tenant compte du trafic prédictif.

La question

Le projet vise à résoudre un problème concret rencontré par les services de voitures de tourisme avec chauffeur (VTC) : l'estimation fiable du temps de parcours en fonction du trafic, notamment pour des réservations à l'avance. Les services existants comme Uber ou LeCab présentent des limites, notamment l'absence de prise en compte du trafic dans le calcul du temps et du prix, ou l'impossibilité de réserver avec une estimation précise du délai. Ce travail cherche donc à concevoir un outil web qui, pour un trajet et une date future donnés, puisse fournir une estimation du temps de parcours en intégrant une prédiction du trafic routier. Cette problématique est importante pour améliorer la gestion du temps, optimiser les trajets, réduire les coûts et répondre aux attentes des clients et des chauffeurs.

Concepts de base

Pour comprendre ce projet, plusieurs notions fondamentales sont nécessaires :

Cartographie en ligne (Web-Mapping)

Le web-mapping consiste à publier des cartes géographiques sur Internet via des serveurs SIG (Systèmes d'Information Géographique). Ces serveurs assurent trois fonctions principales :

• Stockage : gestion des données géographiques dans des bases spécialisées (ex. PostGIS, Oracle Spatial) et des images cartographiques référencées.
• Traitement : exécution de requêtes spatiales complexes (inclusion, croisement, calculs de distances, mise à jour des données) grâce à des serveurs web et des scripts (PHP, ASP, JSP).
• Diffusion : transmission des cartes et données au client via des formats adaptés aux navigateurs (GIF, JPEG, PNG pour les images, SVG ou SWF pour les vecteurs).

Le web-mapping permet ainsi d'afficher des cartes interactives accessibles à distance, avec des fonctions comme le zoom, le calcul de distances, ou la réaction aux clics.

APIs cartographiques en ligne

De grandes entreprises comme Google, Nokia (Here), Microsoft (Bing) et Yahoo proposent des APIs permettant d'intégrer facilement des fonds de carte et des services associés dans des applications web. Ces APIs offrent des fonctionnalités telles que la géolocalisation, le calcul d'itinéraires, et l'accès à des données de trafic en temps réel ou prédictif. Google Maps API et Here Maps API sont particulièrement adaptées pour ce projet, Google Maps pour sa base de données spatiale étendue et Here Maps pour ses données de trafic.

Problèmes de cheminement dans un graphe

La ville est modélisée sous forme d'un graphe où les nœuds représentent des points géographiques (carrefours, intersections) et les arcs représentent les routes entre ces points. Le problème consiste à trouver le chemin optimal entre deux points, ici le chemin qui minimise le temps de parcours. Plusieurs algorithmes sont utilisés :

• Dijkstra : algorithme classique pour trouver le plus court chemin dans un graphe avec des poids positifs.
• Bellman-Ford : permet de gérer des graphes avec des poids négatifs, mais moins efficace.
• A étoile (A*) : améliore Dijkstra en utilisant une heuristique pour accélérer la recherche.

Prédiction du trafic et séries temporelles

La prédiction repose sur l'analyse statistique des séries temporelles des données de trafic recueillies. Ces séries représentent l'évolution du trafic (vitesse, temps de parcours) sur les arcs du graphe au fil du temps. La stationnarité des séries temporelles est une caractéristique importante pour choisir la méthode de prédiction. Une méthode courante est la modélisation autorégressive, qui utilise les valeurs passées pour estimer les valeurs futures. Ce modèle statistique permet d'anticiper le trafic à une date donnée, ce qui est essentiel pour estimer le temps de parcours futur.

Approche

Le projet s'est déroulé en trois grandes étapes :

1. Création automatique d'un graphe de la ville de Paris : À partir de coordonnées géographiques, une structure de graphe est générée automatiquement, représentant les routes et intersections. Ce graphe est validé visuellement sur une carte.
2. Calcul du temps optimal de parcours : Un outil est développé pour prendre en entrée deux coordonnées géographiques et une date, puis construire un graphe adapté à cette date. Les algorithmes de plus court chemin (notamment Dijkstra) sont appliqués pour déterminer le chemin et le temps de parcours optimaux en fonction du trafic.
3. Intégration d'un module de prédiction : Un modèle statistique basé sur les séries temporelles du trafic est mis en place pour prédire les conditions de circulation futures. Cette prédiction est intégrée dans le calcul du temps de parcours, permettant d'estimer ce dernier pour une date future.

Techniquement, le service est conçu comme une application web utilisant des APIs cartographiques (Google Maps, Here Maps) pour l'affichage et la gestion des données géographiques. L'environnement NodeJS est choisi pour son architecture adaptée aux services web et à la gestion asynchrone des données. Le graphe est construit à partir de données géographiques découpées en carrés pour faciliter la gestion et la génération automatique des arcs.

Résultats

Le mémoire rapporte la réalisation d'un prototype fonctionnel qui :

• Génère automatiquement un graphe représentant la ville de Paris, avec ses nœuds et arcs, validé par affichage cartographique.
• Implémente l'algorithme de Dijkstra pour calculer le plus court temps de parcours entre deux points donnés.
• Met en œuvre un module de prédiction du trafic basé sur l'apprentissage des séries temporelles, capable d'estimer les conditions de circulation à une date future.
• Intègre ces composants dans un service web accessible, permettant à un utilisateur de saisir un trajet et une date pour obtenir une estimation du temps de parcours prenant en compte le trafic prédictif.

Ce service répond ainsi aux besoins identifiés dans les VTC, en particulier la possibilité de réserver à l'avance avec une estimation fiable du temps de trajet, ce qui peut améliorer la gestion des flottes et la satisfaction client.

Limitations et questions ouvertes

Le mémoire souligne certaines limites :

• La précision de la prédiction dépend fortement de la qualité et de la quantité des données historiques de trafic disponibles. Sans données suffisantes, la prédiction peut être moins fiable.
• Le modèle de prédiction utilisé est basé sur des méthodes statistiques classiques (modèle autorégressif) ; d'autres approches plus avancées pourraient améliorer la précision.
• Le projet est initialement limité à la zone de Paris et sa grande couronne, ce qui restreint la généralisation immédiate à d'autres villes ou régions.
• Le service ne prend pas en compte certains facteurs dynamiques comme les événements exceptionnels (accidents, travaux) qui peuvent fortement impacter le trafic.

Glossaire

• API : Application Programming Interface, interface permettant l'interaction entre logiciels.
• Graphe : Structure composée de nœuds (points) et d'arcs (liens) représentant un réseau routier.
• NodeJS : Environnement d'exécution JavaScript côté serveur, adapté aux applications web.
• Prédiction : Estimation des valeurs futures à partir de données passées, ici appliquée au trafic routier.
• Série temporelle : Suite de données mesurées successivement dans le temps, utilisée pour l'analyse statistique.
• SIG : Système d'Information Géographique, outil de gestion et d'analyse de données géographiques.
• Trafic prédictif : Estimation anticipée des conditions de circulation routière à une date future.
• VTC : Voiture de Tourisme avec Chauffeur, service de transport privé.