Calcul d'itinéraires
Comment votre GPS trouve-t-il le meilleur itinéraire parmi des millions de possibilités en quelques secondes ? Grâce aux graphes et à l'algorithme de Dijkstra !
Objectifs du cours
- Comprendre la modélisation d'un réseau routier en graphe
- Découvrir l'algorithme de Dijkstra (plus court chemin)
- Connaître les critères d'optimisation (distance, temps, trafic)
- Comprendre le calcul d'itinéraire en temps réel
- Identifier les données utilisées par les GPS modernes
Erreurs courantes à éviter
- Penser que le GPS cherche tous les chemins possibles (trop long !)
- Croire que le plus court chemin en distance est toujours le plus rapide
- Oublier que les cartes doivent être à jour (nouvelles routes, sens interdits)
- Ne pas comprendre que le trafic en temps réel nécessite Internet
**Du réseau routier au graphe mathématique**
Pour calculer un itinéraire, le GPS doit d'abord **modéliser** le réseau routier.
📐 **Qu'est-ce qu'un graphe ?**
Un **graphe** est une structure mathématique composée de :
**Sommets (ou nœuds)** : • Représentent les **intersections** • Chaque carrefour = 1 sommet • Points de départ/arrivée
**Arêtes (ou arcs)** : • Représentent les **routes** • Relient deux sommets • Peuvent être **orientées** (sens unique)
**Poids (ou coûts)** : • Valeur associée à chaque arête • Peut être : distance (km), temps (min), vitesse, coût (péages)
🗺️ **Exemple simple**
**Réseau routier réel** : ``` A ----5km---- B | | 3km 2km | | C ----4km---- D ```
**Graphe correspondant** : • Sommets : A, B, C, D (4 intersections) • Arêtes : AB, AC, BD, CD (4 routes) • Poids : 5, 3, 2, 4 (distances en km)
🚗 **Graphe orienté (sens uniques)**
Certaines routes sont à sens unique : • Arête A → B (sens unique de A vers B) • Arête B → A interdit
**Paris intra-muros** : • ~6 000 intersections (sommets) • ~15 000 segments de route (arêtes)
**France entière** : • ~10 millions d'intersections • ~25 millions de segments
**Europe** : • ~100 millions d'intersections • Graphe gigantesque !
🏷️ **Types de poids**
**1. Distance (km)** : • Poids = longueur de la route • Cherche le **trajet le plus court** • Ne tient pas compte de la vitesse
**2. Temps (minutes)** : • Poids = temps de parcours • Temps = distance / vitesse limite • Cherche le **trajet le plus rapide**
**3. Temps réel (avec trafic)** : • Poids = temps de parcours actuel • Intègre les embouteillages • Mis à jour en temps réel
**4. Multi-critères** : • Combinaison distance + temps + péages + type de route • Optimisation complexe
📊 **Calcul du poids temporel**
Pour une route de 10 km à 50 km/h : • Temps = 10 km ÷ 50 km/h = 0.2 h = **12 minutes**
Pour une route de 5 km à 130 km/h (autoroute) : • Temps = 5 km ÷ 130 km/h ≈ 0.038 h = **2.3 minutes**
**Paradoxe** : • Autoroute : 2× plus longue (10 km vs 5 km) mais 5× plus rapide ! • Le chemin le plus court ≠ le chemin le plus rapide
🚦 **Contraintes du graphe**
**Sens uniques** : • Arête orientée A → B • Graphe **orienté**
**Interdictions de tourner** : • De A vers B interdit • Arête supprimée
**Restrictions** : • Hauteur (pont bas) • Poids (poids lourd) • Largeur (rue étroite)
**Fermetures temporaires** : • Travaux • Événements • Accidents
💾 **Stockage des données**
**Format des données GPS** :
Sommet (intersection) : ```json { "id": 12345, "lat": 48.8584, "lon": 2.2945, "type": "intersection" } ```
Arête (route) : ```json { "id": 67890, "from": 12345, "to": 12346, "distance": 1.2, "vitesse_max": 50, "temps": 1.44, "sens_unique": true, "nom_rue": "Avenue des Champs-Élysées" } ```
**Taille des données** :
• **Carte France** : ~2 GB • **Carte Europe** : ~8 GB • **Carte Monde** : ~50 GB
Les GPS embarqués stockent ces cartes localement.
🔄 **Mise à jour des cartes**
**Fréquence** : • Nouvelles routes construites • Routes fermées • Changements de sens • Limitations de vitesse modifiées
**GPS moderne** : • Mises à jour trimestrielles • Téléchargement automatique (si connecté)
**Importance** : • Carte obsolète → mauvais itinéraires • Peut vous envoyer sur une route inexistante !
# Modélisation d'un réseau routier en graphe
class Sommet:
def __init__(self, nom, latitude=None, longitude=None):
self.nom = nom
self.lat = latitude
self.lon = longitude
def __str__(self):
return self.nom
class Arete:
def __init__(self, depart, arrivee, distance, vitesse_max=50):
self.depart = depart
self.arrivee = arrivee
self.distance = distance # km
self.vitesse_max = vitesse_max # km/h
self.temps = (distance / vitesse_max) * 60 # minutes
def __str__(self):
return f"{self.depart} → {self.arrivee} ({self.distance}km, {self.temps:.1f}min)"
class Graphe:
def __init__(self):
self.sommets = []
self.aretes = []
def ajouter_sommet(self, sommet):
self.sommets.append(sommet)
def ajouter_arete(self, arete):
self.aretes.append(arete)
def voisins(self, sommet):
"""Retourne tous les voisins d'un sommet."""
return [a for a in self.aretes if a.depart == sommet]
def afficher(self):
print("GRAPHE DU RÉSEAU ROUTIER:\n")
print(f"Sommets (intersections): {len(self.sommets)}")
for s in self.sommets:
print(f" • {s.nom}")
print(f"\nArêtes (routes): {len(self.aretes)}")
for a in self.aretes:
print(f" • {a}")
# Créer un réseau routier simple
print("=== CRÉATION D'UN GRAPHE ROUTIER ===\n")
# Créer les sommets (intersections)
A = Sommet("A - Place République", 48.8671, 2.3636)
B = Sommet("B - Place Bastille", 48.8532, 2.3690)
C = Sommet("C - Gare de Lyon", 48.8443, 2.3736)
D = Sommet("D - Nation", 48.8482, 2.3965)
E = Sommet("E - Porte de Vincennes", 48.8473, 2.4103)
# Créer le graphe
graphe = Graphe()
# Ajouter les sommets
for sommet in [A, B, C, D, E]:
graphe.ajouter_sommet(sommet)
# Ajouter les arêtes (routes)
graphe.ajouter_arete(Arete(A, B, 2.1, 50)) # Boulevard Beaumarchais
graphe.ajouter_arete(Arete(B, C, 1.5, 50)) # Rue de Lyon
graphe.ajouter_arete(Arete(A, D, 3.2, 50)) # Boulevard Voltaire
graphe.ajouter_arete(Arete(B, D, 2.8, 50)) # Faubourg Saint-Antoine
graphe.ajouter_arete(Arete(C, D, 1.9, 50)) # Avenue Daumesnil
graphe.ajouter_arete(Arete(D, E, 1.7, 70)) # Cours de Vincennes (plus rapide)
# Afficher le graphe
graphe.afficher()
# Analyse du graphe
print("\n\n=== ANALYSE DU GRAPHE ===\n")
print(f"Nombre d'intersections: {len(graphe.sommets)}")
print(f"Nombre de routes: {len(graphe.aretes)}")
distance_totale = sum(a.distance for a in graphe.aretes)
print(f"Distance totale du réseau: {distance_totale:.1f} km")
# Voisins d'un sommet
print(f"\nVoisins de {A.nom}:")
for arete in graphe.voisins(A):
print(f" → {arete.arrivee.nom} ({arete.distance}km, {arete.temps:.1f}min)")
# Comparaison distance vs temps
print("\n\n=== DISTANCE VS TEMPS ===\n")
routes_test = [
("Route nationale", 100, 90),
("Autoroute", 120, 130),
("Ville", 10, 50),
("Périphérique", 35, 70)
]
print(f"{'Type de route':<20} {'Distance':<12} {'Vitesse':<12} {'Temps':<15}")
print("-" * 65)
for nom, distance, vitesse in routes_test:
temps = (distance / vitesse) * 60
print(f"{nom:<20} {distance:>3} km{' ':<6} {vitesse:>3} km/h{' ':<4} {temps:>5.1f} min")
print("\n→ L'autoroute de 120km est parcourue plus vite que la nationale de 100km !")
# Graphe orienté (sens uniques)
print("\n\n=== GRAPHE ORIENTÉ (SENS UNIQUES) ===\n")
graphe_oriente = Graphe()
# Sommets
S1 = Sommet("S1")
S2 = Sommet("S2")
S3 = Sommet("S3")
graphe_oriente.ajouter_sommet(S1)
graphe_oriente.ajouter_sommet(S2)
graphe_oriente.ajouter_sommet(S3)
# Arêtes avec sens uniques
graphe_oriente.ajouter_arete(Arete(S1, S2, 2.0, 50)) # S1 → S2 autorisé
graphe_oriente.ajouter_arete(Arete(S2, S3, 1.5, 50)) # S2 → S3 autorisé
graphe_oriente.ajouter_arete(Arete(S3, S1, 3.0, 50)) # S3 → S1 autorisé
# Pas de S2 → S1 (sens unique)
print("Routes disponibles:")
print(" • S1 → S2 (autorisé)")
print(" • S2 → S3 (autorisé)")
print(" • S3 → S1 (autorisé)")
print(" • S2 → S1 (INTERDIT - sens unique)")
print("\nPour aller de S2 à S1:")
print(" Impossible directement → doit passer par S3")
print(" Itinéraire forcé: S2 → S3 → S1")
# Taille des graphes réels
print("\n\n=== TAILLE DES GRAPHES RÉELS ===\n")
graphes_reels = [
("Quartier parisien", 100, 300, "0.1 MB"),
("Paris intra-muros", 6000, 15000, "50 MB"),
("Île-de-France", 50000, 150000, "500 MB"),
("France", 10000000, 25000000, "2 GB"),
("Europe", 100000000, 250000000, "8 GB"),
("Monde", 500000000, 1000000000, "50 GB")
]
print(f"{'Zone':<25} {'Sommets':<15} {'Arêtes':<15} {'Taille données':<15}")
print("-" * 75)
for zone, sommets, aretes, taille in graphes_reels:
print(f"{zone:<25} {sommets:>12,}{' ':<2} {aretes:>12,}{' ':<2} {taille:>12}")
print("\n→ Les GPS embarqués stockent ces gigantesques graphes !")Quiz de validation
1. Dans un graphe routier, que représentent les sommets ?
2. Quel est le principe de l'algorithme de Dijkstra ?
3. Pourquoi le chemin le plus court en distance n'est pas toujours le plus rapide ?
4. Combien d'intersections environ contient le graphe de Paris intra-muros ?
5. Quelle optimisation moderne accélère le calcul d'itinéraire sur longue distance ?
