ALLO SNT
ÉLÈVES, PARENTS & PROFS
Connexion
Retour a Localisation

Calcul d'Itineraires

Quand Google Maps vous propose '3 itineraires', il explore des milliers de chemins possibles en quelques millisecondes. Decouvrez les algorithmes qui rendent cela possible : Dijkstra, A*, et les techniques d'optimisation des GPS modernes !

Difficulte:
40 min
+40 XP

Objectifs du cours

  • Comprendre les algorithmes de calcul d'itineraires (Dijkstra, A*)
  • Decouvrir la structure des donnees routieres (graphes)
  • Maitriser les facteurs d'optimisation (distance, temps, peages)
  • Implementer un algorithme de recherche de chemin en Python
  • Connaitre les services d'API de routage (Google, OpenRouteService)

Erreurs courantes a eviter

  • Confondre distance a vol d'oiseau et distance routiere
  • Oublier que le plus court n'est pas forcement le plus rapide
  • Ignorer les contraintes (sens uniques, restrictions, horaires)
  • Sous-estimer la complexite du calcul d'itineraire en temps reel

**Modelisation mathematique du reseau routier**

Pour calculer des itineraires, on represente le reseau routier sous forme de graphe :

**Les noeuds (sommets)** : - Intersections - Ronds-points - Points d'interet (POI) - Changements de caractéristiques de route

**Les aretes (arcs)** : - Segments de route entre deux noeuds - Caracteristiques : distance, temps, type de voie - Peuvent etre orientees (sens uniques)

**Exemple concret** :

Paris centre = environ 50 000 intersections Ile-de-France = environ 1 million de noeuds France entiere = environ 25 millions de noeuds

**Poids des aretes** :

Chaque segment de route a des "poids" qui mesurent son cout :

| Critere | Description | Unite | |---------|-------------|-------| | Distance | Longueur du segment | metres | | Temps | Duree de parcours | secondes | | Cout | Peages, carburant | euros | | Confort | Type de route | score |

**Donnees OpenStreetMap** :

OpenStreetMap (OSM) est la base de donnees cartographique libre : - 8 milliards de noeuds dans le monde - Mise a jour par des contributeurs benevoles - Utilisee par de nombreuses applications GPS - Format : XML/PBF

**Attributs d'une route OSM** : - highway : type (motorway, primary, residential...) - maxspeed : vitesse limite - oneway : sens unique - surface : revetement - lanes : nombre de voies

Python
# Representation d'un reseau routier en graphe
import math

print("=== RESEAU ROUTIER COMME GRAPHE ===\n")

# Structure de donnees pour un graphe routier
class GrapheRoutier:
    def __init__(self):
        self.noeuds = {}  # id -> (lat, lon, nom)
        self.aretes = {}  # (id1, id2) -> {distance, temps, type}

    def ajouter_noeud(self, id, lat, lon, nom=""):
        self.noeuds[id] = {"lat": lat, "lon": lon, "nom": nom}

    def ajouter_route(self, id1, id2, distance_m, vitesse_kmh, type_route):
        temps_s = (distance_m / 1000) / vitesse_kmh * 3600
        self.aretes[(id1, id2)] = {
            "distance": distance_m,
            "temps": temps_s,
            "type": type_route,
            "vitesse": vitesse_kmh
        }
        # Route bidirectionnelle par defaut
        self.aretes[(id2, id1)] = self.aretes[(id1, id2)]

    def voisins(self, noeud):
        """Retourne les noeuds voisins accessibles."""
        voisins = []
        for (n1, n2), attrs in self.aretes.items():
            if n1 == noeud:
                voisins.append((n2, attrs))
        return voisins

# Creation d'un petit graphe exemple
print("Creation d'un graphe routier simplifie :\n")

g = GrapheRoutier()

# Noeuds (intersections)
noeuds = [
    ("A", 48.8566, 2.3522, "Place de la Republique"),
    ("B", 48.8606, 2.3376, "Louvre"),
    ("C", 48.8530, 2.3499, "Notre-Dame"),
    ("D", 48.8738, 2.2950, "Arc de Triomphe"),
    ("E", 48.8584, 2.2945, "Tour Eiffel")
]

for id, lat, lon, nom in noeuds:
    g.ajouter_noeud(id, lat, lon, nom)
    print(f"  Noeud {id}: {nom}")

print("\nRoutes :")
routes = [
    ("A", "B", 1500, 30, "urbain"),
    ("A", "C", 800, 30, "urbain"),
    ("B", "C", 600, 30, "urbain"),
    ("B", "D", 3000, 50, "avenue"),
    ("B", "E", 2500, 50, "avenue"),
    ("D", "E", 1000, 50, "avenue"),
    ("C", "E", 3500, 40, "urbain")
]

for id1, id2, dist, vit, type_r in routes:
    g.ajouter_route(id1, id2, dist, vit, type_r)
    temps = (dist/1000) / vit * 60  # en minutes
    print(f"  {id1} <-> {id2}: {dist}m, {vit}km/h, {temps:.1f}min")

# Afficher les voisins d'un noeud
print("\nVoisins de B (Louvre) :")
for voisin, attrs in g.voisins("B"):
    print(f"  -> {voisin}: {attrs['distance']}m en {attrs['temps']/60:.1f}min")

# Statistiques typiques
print("\n\n=== STATISTIQUES RESEAUX ROUTIERS ===\n")

stats = [
    ("Paris intra-muros", "~50 000", "~120 000"),
    ("Ile-de-France", "~1 000 000", "~2 500 000"),
    ("France", "~25 000 000", "~60 000 000"),
    ("OpenStreetMap mondial", "~8 000 000 000", "~9 000 000 000")
]

print(f"{'Zone':<25} {'Noeuds':<20} {'Aretes':<20}")
print("-" * 65)
for zone, noeuds, aretes in stats:
    print(f"{zone:<25} {noeuds:<20} {aretes:<20}")

Quiz de validation

1. Comment represente-t-on un reseau routier en informatique ?

2. Que garantit l'algorithme de Dijkstra ?

3. Quelle est la principale amelioration de A* par rapport a Dijkstra ?

4. Quelle heuristique utilise-t-on typiquement dans A* pour le GPS ?

5. Quelle base de donnees cartographique libre est utilisee par OpenRouteService ?

Pixel