Smart GPS
Diallo Abdoulaye • Semih Taskin • Muller Arthur — BUT Informatique S5
Modélisation mathématique et navigation urbaine intelligente — comparaison de trois algorithmes de plus court chemin sur un réseau routier représenté en graphe pondéré, le tout restitué dans une application web interactive.
Contexte & objectif
Un GPS ne se résume pas à "trouver une route". Il faut modéliser proprement le réseau routier, choisir un algorithme adapté et produire un résultat compréhensible pour l'utilisateur. C'est l'angle académique de ce projet : une approche à la fois mathématique, algorithmique et applicative.
L'objectif était de représenter une ville comme un graphe non orienté pondéré, d'implémenter et comparer plusieurs algorithmes de plus court chemin, d'intégrer une estimation de trajet réaliste, et de rendre le tout exploitable dans une interface de visualisation interactive.
Comparaison des algorithmes
Le cœur du projet : implémenter trois approches classiques, puis les comparer en pratique sur des graphes urbains (coût, sommets visités, temps d'exécution).
Dijkstra
Recherche exhaustive garantissant le chemin optimal. Référence de base pour l'analyse comparative.
A*
Guidé par une heuristique euclidienne. Réduit significativement le nombre de sommets explorés sans perdre l'optimalité.
Bellman-Ford
Robuste théoriquement mais plus coûteux dans ce contexte. Intéressant pour la comparaison de complexité.
Application interactive
Ce qui transforme le projet d'un sujet théorique en une démonstration exploitable.
Choix départ / arrivée
L'interface permet de sélectionner interactivement les noeuds de départ et d'arrivée sur le réseau, puis de déclencher le calcul de chemin en choisissant l'algorithme souhaité.
Chemin calculé & itinéraire
Le chemin optimal est affiché visuellement sur le graphe, avec estimation du temps de trajet basée sur un modèle réaliste incluant les coûts incompressibles (démarrage, arrêts, feux).
Comparaison visuelle des algorithmes
L'écran de comparaison met en regard les trois algorithmes : nombre de sommets visités, temps d'exécution et coût final. Les tableaux et graphiques rendent les différences de comportement immédiatement lisibles.
Navigation & contrôles
La barre de navigation de l'application offre un accès direct aux différentes vues : chargement du réseau, calcul de chemin, comparaison des algorithmes et documentation.
Ce que ce projet révèle
Ce projet reflète une facette plus algorithmique et analytique de mon profil. Là où d'autres projets mettent l'accent sur l'architecture applicative ou l'IA, celui-ci montre ma capacité à formaliser un problème, choisir des méthodes adaptées, comparer rigoureusement plusieurs solutions et transformer un sujet théorique en une application interactive claire.
Le modèle de temps réaliste — qui va au-delà du simple temps = distance / vitesse — illustre aussi une volonté de coller à la réalité terrain plutôt que de s'en tenir à l'élégance théorique.