Calculs d'itinéraires

Les applications de géolocalisation et de calcul d'itinéraires sont omniprésentes dans notre quotidien. Elles permettent de rechercher l'itinéraire le plus rapide ou le plus court mais aussi le moins cher ou le plus écologique.

Comment calculer le meilleur itinéraire ?

Les applications de cartographie

Les applications de cartographie sur Internet, smarphones ou dans les GPS de voiture calculent le « meilleur » itinéraire suivant des critères définis. Elles utilisent de nombreuses informations (préenregistrées ou téléchargées en temps réel) pour calculer les itinéraires : distance, limitation de vitesse, travaux, temps de trajet réel enregistré, trafic en temps réel, accident, etc.

Exemple

  • Pourquoi les deux applications proposent-elles des itinéraires différents ?

  • Quels sont selon vous les critères retenus dans chaque cas pour déterminer le meilleur itinéraire ?

Graphe d'un réseau routier

Un réseau de villes et les routes qui les relient peuvent être représentés par un graphe[1] . Le temps de trajet (exprimé en minute) est alors indiqué sur l' arête[2] (lien) entre deux villes.

Exemple

  • Quel est le temps de parcours de Montpellier à Lyon en passant par Clermont-Ferrand ?

  • en passant par Saint- Étienne ?

  • en passant par Avignon et Valence ?

  • Quel est le meilleur parcours ?

Algorithme pour déterminer un itinéraire

L' algorithme[3] simplifié suivant détermine un itinéraire en choisissant systématiquement la ville suivante (non choisie précédemment) la plus proche de la précédente.

D'autres algorithmes plus complexes et plus efficaces sont utilisés par les systèmes de cartographie, comme l'algorithme de Dijkstra qui recherche à chaque étape le meilleur prédécesseur.

Exemple

  • Appliquer l'algorithme de recherche d'itinéraire dans le graphe de Montpellier à Lyon, puis de Lyon à Montpellier. Cet algorithme donne-t-il l'itinéraire le plus court ? Pourquoi ?

CONCLUSION.

  • En quoi les algorithmes et le traitement de l'information permettent-ils de trouver le meilleur itinéraire ?