GPS Intelligent - Documentation Complète

Table des Matières

1. Introduction
2. Modélisation Mathématique
3. Algorithmes Implémentés
4. Modèle de Temps Réaliste
5. Architecture du Projet
6. Résultats et Analyses
7. Application Web
8. Conclusion

1. Introduction

1.1 Problématique

Question Centrale

Comment modéliser mathématiquement un système de navigation GPS et implémenter des algorithmes efficaces pour calculer le plus court chemin en milieu urbain ?

1.2 Objectifs

Modélisation

Représenter une ville comme un graphe pondéré

Algorithmes

Implémenter Dijkstra, A* et Bellman-Ford

Temps Réel

Modèle de temps urbain réaliste

Interface Web

Application interactive

2. Modélisation Mathématique

2.1 Représentation en Graphe

Une ville est modélisée par un graphe pondéré non orienté :

$$G = (V, E, w)$$

Où :

$V$ : ensemble des sommets (intersections)
$E \subseteq V \times V$ : ensemble des arêtes (routes)
$w: E \rightarrow \mathbb{R}^+$ : fonction de poids (distance)

2.2 Problème d'Optimisation

Trouver un chemin $P = (v_0, v_1, ..., v_k)$ tel que :

$$\min_{P} \sum_{i=0}^{k-1} w(v_i, v_{i+1})$$

Sous contraintes :

$$v_0 = s \quad \text{(départ)}$$ $$v_k = t \quad \text{(arrivée)}$$ $$(v_i, v_{i+1}) \in E \quad \forall i$$

2.3 Calcul des Poids

Distance euclidienne entre deux sommets :

$$w(v_1, v_2) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

Note

Si les coordonnées sont en degrés (latitude/longitude), 1° ≈ 111 km.

2.4 Exemple Visuel : Réseau Urbain

Voici un exemple de graphe représentant un réseau urbain avec 100 intersections :

Figure 1 : Graphe d'une ville avec 100 intersections (sommets) et leurs routes (arêtes)

3. Algorithmes Implémentés

3.1 Algorithme de Dijkstra

Principe

Exploration exhaustive du graphe par distances croissantes.

Complexité

$$O((n + m) \log n)$$

Avec $n = |V|$ sommets et $m = |E|$ arêtes

Pseudo-code

def dijkstra(G, s, t):
    distances[v] ← ∞ pour tout v ∈ V
    distances[s] ← 0
    Q ← file de priorité avec tous les sommets
    
    tant que Q n'est pas vide:
        u ← extraire_min(Q)
        si u = t: retourner chemin
        
        pour chaque voisin v de u:
            nouvelle_distance ← distances[u] + w(u, v)
            si nouvelle_distance < distances[v]:
                distances[v] ← nouvelle_distance
                parent[v] ← u

3.2 Algorithme A*

Principe

Utilise une heuristique pour guider la recherche vers la cible.

Fonction de Coût

$$f(n) = g(n) + h(n)$$

Où :

$$g(n) = \text{coût réel depuis le départ}$$ $$h(n) = \text{heuristique (estimation du coût restant)}$$

Heuristique : Distance Euclidienne

$$h(n) = \sqrt{(x_n - x_t)^2 + (y_n - y_t)^2}$$

Admissibilité

Cette heuristique est admissible car :

$$h(n) \leq \text{coût réel restant}$$

(La distance en ligne droite est toujours ≤ distance par routes)

3.3 Algorithme de Bellman-Ford

Principe

Algorithme qui peut gérer les poids négatifs et détecte les cycles négatifs.

Note importante : Dans ce projet, tous les poids sont positifs (distances euclidiennes). La capacité de Bellman-Ford à gérer les poids négatifs n'est donc pas utilisée ici, mais reste disponible pour d'autres applications.

Relaxation

Relaxe toutes les arêtes, n-1 fois :

$$d[v] = \min(d[v], d[u] + w(u,v))$$

Détection de Cycle Négatif

Après n-1 itérations, si on peut encore relaxer une arête, il y a un cycle négatif.

Complexité

$$O(n \cdot m)$$

Où n = sommets, m = arêtes

Cas d'Usage

Avantages :

✅ Gère les poids négatifs
✅ Détecte les cycles négatifs

Inconvénient :

❌ Plus lent que Dijkstra (O(n·m) vs O((n+m) log n))

3.4 Comparaison Visuelle

Voici une comparaison sur une grille 10×10 :

Dijkstra - Exploration exhaustive

A* - Exploration guidée

Note : Sur une grille régulière avec poids égaux, A* et Dijkstra visitent souvent le même nombre de sommets car l'heuristique euclidienne n'est pas très informative. Sur des graphes irréguliers (villes réelles), A* est beaucoup plus efficace.

3.5 Tableau Comparatif

Critère	Dijkstra	A*	Bellman-Ford
Complexité	$O((n+m) \log n)$	$O((n+m) \log n)$	$O(n \cdot m)$
Optimalité	Oui	Oui (si h admissible)	Oui
Sommets visités	Plus nombreux	30-75% de moins (selon graphe)	Tous les sommets (relaxation n-1 fois)
Vitesse pratique	Standard	1-2× plus rapide (selon graphe)	100-200× plus lent
Heuristique	Non	Oui	Non
Poids négatifs	Non	Non	Oui

3.6 Résultats Visuels

Figure 3 : Comparaison Dijkstra vs A* - Sommets visités et temps d'exécution

Figure 4 : Chemin optimal calculé par A* sur le réseau urbain

4. Modèle de Temps Réaliste

4.1 Problématique

Le modèle naïf est incorrect en milieu urbain :

$$t = \frac{d}{v}$$

❌ FAUX en milieu urbain

Car il ignore :

Le temps de démarrage
Les feux rouges
Les arrêts

4.2 Modèle Proposé

Formule du Temps Réaliste

$$t(d) = t_0 + \frac{d}{v}$$

Où :

$t_0$ = temps incompressible (démarrage, arrêt, feux)
$d$ = distance en km
$v$ = vitesse moyenne en km/h

4.3 Paramètres Calibrés

Moyen	$v$ (km/h)	$t_0$ (s)	Justification
🚗 Voiture	50	15	Démarrage + 1 feu + arrêt
🚴 Vélo	15	8	Plus agile (moins de feux)
🚶 À pied	5	5	Démarrage très rapide

4.4 Propriétés Mathématiques

Continuité

$$t(d) \in C^{\infty}(\mathbb{R}^+)$$

Croissance

$$\frac{dt}{dd} = \frac{1}{v} > 0$$

✅ Le temps croît linéairement avec la distance

Temps Minimum

$$t(0) = t_0 > 0$$

✅ Même pour $d \to 0$, il y a un temps minimum réaliste

4.5 Exemple de Calcul

Trajet de 31 mètres à pied

Données :

$d = 0.031$ km
$v = 5$ km/h
$t_0 = 5$ s

Calcul :

$$t = 5 + \frac{0.031}{5} \times 3600 = 5 + 22.3 = 27.3 \text{ s}$$

Réaliste !

5. Architecture du Projet

5.1 Structure Modulaire

ProjetS5_maths/
├── 🧠 src/                    # Cœur mathématique
│   ├── graph.py              # Classes Vertex, Edge, Graph
│   ├── algorithms.py         # Dijkstra, A*, Bellman-Ford
│   ├── generators.py         # Génération de graphes
│   ├── utils.py              # Utilitaires
│   └── visualizer.py         # Visualisations
│
├── 🌐 webapp_demo.py         # Interface web Streamlit
├── 🧪 experiments/           # Expériences scientifiques
├── ✅ tests/                 # Tests unitaires (25 tests)
└── 📚 docs/                  # Documentation

5.2 Flux de Données

1. Utilisateur

Demande un trajet

2. Interface Web

webapp_demo.py

3. Algorithme

src/algorithms.py

4. Résultat

Chemin optimal

5.3 Principes

Principe	Implémentation
Séparation des responsabilités	Logique (src/) ≠ Interface (webapp/)
Réutilisabilité	Même code pour webapp, expériences, tests
Testabilité	Code pur sans dépendances UI
Maintenabilité	1 bug corrigé = tout est corrigé

6. Résultats et Analyses

6.1 Validations

Tests Unitaires

25/25 tests passés

Optimalité

Dijkstra = A*

Efficacité

A* 30-50% plus rapide

Complexité

O(n log n) vérifié

6.1.1 Analyse de Complexité Empirique

Figure 5 : Validation empirique de la complexité O((n+m) log n)

6.1.2 Heatmap d'Exploration

Figure 6 : Carte thermique montrant l'exploration des sommets par A*

6.1.3 Interprétation des Résultats de la Console

Lorsque vous lancez une démonstration ou une expérience, voici ce qui s'affiche dans la console et comment l'interpréter :

Exemple de Sortie Console

======================================================================
 EXPÉRIENCE 2 : GRAPHE URBAIN ALÉATOIRE
======================================================================

Graphe : Non-orienté
----------------------------------------
Nombre de sommets (n) : 200
Nombre d'arêtes (m)   : 591
Degré moyen           : 5.91
Densité               : 0.0297
Connexe               : Oui

Recherche du plus court chemin : 2 → 177

############################################################
  COMPARAISON DES ALGORITHMES
############################################################
Graphe : 200 sommets, 591 arêtes

Algorithme      Coût       Sommets    Temps (ms)   Speedup   
------------------------------------------------------------
dijkstra        1574.18    149        0.21         1.00x (ref)
astar           1574.18    37         0.11         1.91x     
bellman_ford    1574.18    200        25.69        0.01x     
------------------------------------------------------------

📊 Analyse :
  • A* vs Dijkstra :
    - Réduction de sommets visités : 75.2% (37 vs 149 sommets)
    - Gain de temps : 47.6% (A* est 1.91× plus rapide)
  • Bellman-Ford vs Dijkstra :
    - Ratio de temps : 122.3× plus lent (visite tous les 200 sommets)
  • Tous les algorithmes trouvent le même chemin optimal ✓
############################################################

Explication Ligne par Ligne

1. Informations sur le Graphe

Nombre de sommets (n) : 200
Nombre d'arêtes (m)   : 591
Degré moyen           : 5.91

Signification :

n = 200 : La ville a 200 intersections (sommets)
m = 591 : Il y a 591 routes (arêtes) entre ces intersections
Degré moyen = 5.91 : Chaque intersection est connectée en moyenne à 5.91 autres intersections
Connexe : Oui : On peut aller de n'importe quelle intersection à n'importe quelle autre

2. Tableau de Comparaison

Algorithme      Coût       Sommets    Temps (ms)   Speedup   
------------------------------------------------------------
dijkstra        1574.18    149        0.21         1.00x (ref)
astar           1574.18    37         0.11         1.91x     
bellman_ford    1574.18    200        25.69        0.01x

Colonnes expliquées :

Coût : Somme des poids des arêtes du chemin (distance totale). Identique pour les 3 algorithmes = même chemin optimal trouvé. Dans cet exemple : 1574.18 unités.
Sommets : Nombre de sommets visités pendant le calcul
- Dijkstra : 149 sommets explorés (sur 200)
- A* : Seulement 37 sommets ! (75% de réduction)
- Bellman-Ford : 200 sommets (tous les sommets, relaxation n-1 fois)
Temps (ms) : Temps d'exécution en millisecondes (temps CPU pour trouver le chemin, pas le temps de parcours)
- Dijkstra : 0.21 ms (référence)
- A* : 0.11 ms (1.91× plus rapide car visite moins de sommets)
- Bellman-Ford : 25.69 ms (122× plus lent car visite tous les sommets)
Speedup : Facteur d'accélération par rapport à Dijkstra (temps_Dijkstra / temps_A*)
- 1.00x = référence (Dijkstra)
- 1.91x = A* est 1.91× plus rapide (0.21 / 0.11)
- 0.01x = Bellman-Ford est beaucoup plus lent (122× plus lent)

3. Analyse Détaillée

📊 Analyse :
  • A* vs Dijkstra :
    - Réduction de sommets visités : 75.2% (37 vs 149 sommets)
    - Gain de temps : 47.6% (A* est 1.91× plus rapide)
  • Bellman-Ford vs Dijkstra :
    - Ratio de temps : 122.3× plus lent (visite tous les 200 sommets)
  • Tous les algorithmes trouvent le même chemin optimal ✓

Interprétation :

Réduction de 75.2% : A* visite 75% de sommets en moins que Dijkstra (37 vs 149) grâce à son heuristique qui guide la recherche vers la cible
Gain de temps de 47.6% : A* est 1.91× plus rapide (0.11 ms vs 0.21 ms). Le gain vient du fait qu'A* visite beaucoup moins de sommets.
122.3× plus lent : Bellman-Ford est très lent (25.69 ms vs 0.21 ms) car sa complexité est O(n·m) au lieu de O((n+m) log n). Il visite tous les 200 sommets.
Même chemin optimal ✓ : Les 3 algorithmes trouvent exactement le même trajet avec le même coût (1574.18), ce qui prouve leur correction mathématique.

Points Clés à Retenir

Coût identique : Les 3 algorithmes trouvent le même chemin optimal (preuve mathématique)
A* est le plus rapide sur graphes irréguliers : Grâce à son heuristique, il visite beaucoup moins de sommets (75% de réduction sur graphe aléatoire). Sur grille régulière avec poids égaux, A* et Dijkstra visitent le même nombre de sommets.
Bellman-Ford est lent : Mais c'est le seul qui peut gérer les poids négatifs (non utilisé dans ce projet où tous les poids sont positifs)
Complexité vérifiée : Les temps mesurés correspondent à la théorie O((n+m) log n)

6.2 Points Forts

Aspect	Réalisation	Niveau
Mathématiques	Modélisation rigoureuse + preuves
Algorithmique	2 algorithmes implémentés + comparés
Architecture	Code modulaire et réutilisable
Tests	25 tests automatisés
Documentation	5 fichiers MD + doc HTML
Interface	Webapp interactive

7. Application Web

7.1 Fonctionnalités

Visualisation du réseau urbain sur carte
Sélection interactive départ/arrivée
Génération aléatoire de points
Comparaison Dijkstra vs A*
Choix du moyen de transport (voiture/vélo/pied)
Calcul de temps réaliste
Statistiques détaillées

7.2 Lancement

# Terminal
cd ProjetS5_maths
source venv/bin/activate  # Windows: venv\Scripts\activate
streamlit run webapp_demo.py

L'application s'ouvre dans le navigateur sur http://localhost:8501

7.3 Guide d'Utilisation de l'Application Web

Démonstration Interactive de l'Application

Étape 1 : Accueil et Carte Interactive
Réseau urbain de Paris - 491 intersections, 712 routes (OpenStreetMap)

Étape 4 : Visualisation du Résultat
Chemin optimal tracé - Distance: 1.74 km, Temps: 2.3 min, 21 étapes

Étape 5 : Comparaison des 3 Algorithmes
A* : 2× plus rapide que Dijkstra, 85% moins de nœuds explorés

Points clés de l'application :

Carte interactive : Réseau routier réel avec zoom et navigation
Calcul optimisé : Chemin le plus court en temps réel
Comparaison : Performance des 3 algorithmes (Dijkstra, A*, Bellman-Ford)
Temps réaliste : Calcul basé sur le modèle t = t₀ + d/v

Étape 2 : Configuration des Paramètres

Panneau de configuration :

Type de carte : OpenStreetMap activée
Algorithme : Dijkstra, A*, ou Bellman-Ford
Moyen de transport : Voiture, Vélo, ou À pied
Points : Sélection manuelle ou aléatoire

Statistiques : 491 intersections, 712 routes, degré moyen 2.9

Étape 3 : Sélection des Points

Sélection interactive :

Choisir manuellement les intersections de départ (311) et d'arrivée (184)
Ou utiliser le bouton "Aléatoire" pour générer des points aléatoires
Cliquer sur "Calculer le trajet" pour lancer l'algorithme

Avantages de l'Application Web

Données réelles : Intégration d'OpenStreetMap pour des distances authentiques
Visualisation interactive : Carte Folium avec zoom et navigation
Comparaison directe : Les 3 algorithmes calculés simultanément
Performances en temps réel : Mesures précises (millisecondes)
Pédagogique : Comprendre visuellement le comportement des algorithmes

8. Conclusion

8.1 Objectifs Atteints

Modélisation

Graphe pondéré rigoureux

Algorithmes

Dijkstra + A* + Bellman-Ford opérationnels

Modèle Temps

Formule mathématique justifiée

Application

Interface web interactive

8.2 Compétences Développées

Domaine	Compétences
Mathématiques	Modélisation, théorie des graphes, optimisation
Algorithmique	Dijkstra, A*, Bellman-Ford, analyse de complexité
Développement	Python, POO, architecture modulaire
Tests	Pytest, tests unitaires, validation
Web	Streamlit, Folium, interfaces interactives
Documentation	Markdown, LaTeX, HTML

8.3 Perspectives

                 Extensions Possibles
                Données réelles : Intégration OpenStreetMap complète
Trafic dynamique : Modélisation des heures de pointe
Multi-critères : Optimiser temps + coût + confort
Machine Learning : Prédiction du trafic
Autres algorithmes : Bellman-Ford (implémenté et disponible dans l'application web)

            

Commandes Rapides

Lancer l'Application Web

cd ProjetS5_maths
source venv/bin/activate
streamlit run webapp_demo.py

Exécuter les Tests

cd ProjetS5_maths
source venv/bin/activate
pytest tests/ -v

Lancer les Expériences

cd ProjetS5_maths
source venv/bin/activate
python3 experiments/comparaison_algos.py

Fichiers Importants

Fichier	Description
`README.md`	Documentation principale du projet
`webapp_demo.py`	Application web interactive
`src/algorithms.py`	Implémentation Dijkstra, A* & Bellman-Ford
`tests/test_algorithms.py`	Tests unitaires des algorithmes
`docs/modele_temps_reel.md`	Documentation du modèle mathématique

Galerie de Résultats

Interprétation des Expériences Complètes

Lorsque vous lancez python3 experiments/comparaison_algos.py, voici ce qui se passe :

Exemple de Sortie (Expériences Complètes)

######################################################################
  SUITE COMPLÈTE D'EXPÉRIENCES
######################################################################

======================================================================
 EXPÉRIENCE 1 : GRAPHE EN GRILLE (Type Manhattan)
======================================================================

Graphe : 400 sommets, 760 arêtes
Recherche du plus court chemin : 0 → 399

############################################################
  COMPARAISON DES ALGORITHMES
############################################################
Algorithme      Coût       Sommets    Temps (ms)   Speedup   
------------------------------------------------------------
dijkstra        1900.00    400        0.38         1.00x (ref)
astar           1900.00    400        0.49         0.77x     
bellman_ford    1900.00    400        64.01        0.01x     

📊 Analyse :
  • A* vs Dijkstra : 
    - Réduction de sommets visités : 0.0% (même nombre sur grille)
    - Gain de temps : -29.4% (A* légèrement plus lent sur grille)
  • Bellman-Ford vs Dijkstra : 168.1× plus lent
  • Tous les algorithmes trouvent le même chemin optimal ✓

======================================================================
 EXPÉRIENCE 2 : GRAPHE URBAIN ALÉATOIRE
======================================================================
...

######################################################################
  RÉSUMÉ GLOBAL DES EXPÉRIENCES
######################################################################

Graphe                              Dijkstra (ms)  A* (ms)      Bellman-Ford (ms)  Speedup A*
------------------------------------------------------------------------------------------------
Grille 20×20                        0.38          0.49         64.01              0.77x
Urbain Aléatoire (200 sommets)      0.21          0.11         25.69              1.91x
Ville Clustérisée (150 sommets)     0.14          0.14         13.14              1.03x
------------------------------------------------------------------------------------------------

Structure des Expériences

Expérience 1 : Grille - Réseau structuré (comme Manhattan)
- 400 sommets en grille 20×20
- Test sur un trajet long (coin à coin)
- Résultat : A* et Dijkstra visitent tous les 400 sommets (poids égaux). A* est légèrement plus lent (0.77x) car l'heuristique n'aide pas sur grille régulière.
Expérience 2 : Aléatoire - Réseau urbain réaliste
- 200 sommets placés aléatoirement
- Test sur trajet aléatoire (2 → 177)
- Résultat : A* visite 37 sommets vs 149 pour Dijkstra (75% de réduction). A* est 1.92× plus rapide (heuristique très efficace)
Expérience 3 : Clustérisé - Ville avec quartiers
- 150 sommets organisés en quartiers
- Test entre quartiers éloignés (0 → 149)
- Résultat : A* visite 64 sommets vs 108 pour Dijkstra (41% de réduction). A* est 1.03× plus rapide (temps similaire mais moins de sommets visités)

Pourquoi A* est parfois plus lent sur la grille ?

Sur une grille régulière avec poids égaux, l'heuristique euclidienne n'apporte pas d'avantage car :

Les chemins sont très structurés (pas de détours possibles)
Dijkstra et A* visitent tous les sommets (400/400 sur grille 20×20)
Le calcul de l'heuristique ajoute un léger surcoût
L'heuristique euclidienne ≈ distance Manhattan sur grille régulière

Conclusion : A* est beaucoup plus efficace sur graphes irréguliers (villes réelles) que sur grilles parfaites avec poids égaux. Sur grille : A* ≈ Dijkstra. Sur graphe aléatoire : A* visite 75% de sommets en moins !

Comparaisons sur Différents Types de Graphes

Grille Régulière 10×10

Graphe Urbain Aléatoire

Graphe Clustérisé (quartiers)

Autres Visualisations

Démonstration sur Grille

Comparaison de Chemins

Plus de 15 visualisations générées pour valider les algorithmes !

Références Bibliographiques

Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik, 1, 269-271.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

Critère	Dijkstra	A*	Bellman-Ford
Complexité	\(O((n+m) \log n)\)	\(O((n+m) \log n)\)	\(O(n \cdot m)\)
Optimalité	Oui	Oui (si h admissible)	Oui
Sommets visités	Plus nombreux	30-75% de moins (selon graphe)	Tous les sommets (relaxation n-1 fois)
Vitesse pratique	Standard	1-2× plus rapide (selon graphe)	100-200× plus lent
Heuristique	Non	Oui	Non
Poids négatifs	Non	Non	Oui

Équipe Projet

Diallo Abdoulaye • Semih Taskin • Muller Arthur

Table des Matières

1. Introduction

1.1 Problématique

Question Centrale

1.2 Objectifs

Modélisation

Algorithmes

Temps Réel

Interface Web

2. Modélisation Mathématique

2.1 Représentation en Graphe

2.2 Problème d'Optimisation

2.3 Calcul des Poids

Note

2.4 Exemple Visuel : Réseau Urbain

3. Algorithmes Implémentés

3.1 Algorithme de Dijkstra

Principe

Complexité

Pseudo-code

3.2 Algorithme A*

Principe

Fonction de Coût

Heuristique : Distance Euclidienne

Admissibilité

3.3 Algorithme de Bellman-Ford

Principe

Relaxation

Détection de Cycle Négatif

Complexité

Cas d'Usage

3.4 Comparaison Visuelle

3.5 Tableau Comparatif

3.6 Résultats Visuels

4. Modèle de Temps Réaliste

4.1 Problématique

4.2 Modèle Proposé

Formule du Temps Réaliste

4.3 Paramètres Calibrés

4.4 Propriétés Mathématiques

Continuité

Croissance

Temps Minimum

4.5 Exemple de Calcul

Trajet de 31 mètres à pied

5. Architecture du Projet

5.1 Structure Modulaire

5.2 Flux de Données

1. Utilisateur

2. Interface Web

3. Algorithme

4. Résultat

5.3 Principes

6. Résultats et Analyses

6.1 Validations

Tests Unitaires

Optimalité

Efficacité

Complexité

6.1.1 Analyse de Complexité Empirique

6.1.2 Heatmap d'Exploration

6.1.3 Interprétation des Résultats de la Console

Exemple de Sortie Console

Explication Ligne par Ligne

1. Informations sur le Graphe

2. Tableau de Comparaison

3. Analyse Détaillée

Points Clés à Retenir

6.2 Points Forts

7. Application Web

7.1 Fonctionnalités

7.2 Lancement

7.3 Guide d'Utilisation de l'Application Web

Démonstration Interactive de l'Application

Étape 2 : Configuration des Paramètres

Étape 3 : Sélection des Points

Avantages de l'Application Web

8. Conclusion