Calcul d'itinéraires

De nombreux sites et applications portables proposent de calculer un itinéraire entre deux points.

Il suffit de renseigner le point de départ et le point d'arrivée.

Le calcul d'itinéraires repose sur des algorithmes assez complexes.

Par exemple l'algorithme de Dijkstra permet d'obtenir le plus court chemin entre deux points

Sans entrer dans les détails, l'algorithme de Dijkstra travaille sur des graphes (chaque ville est un sommet du graphe et chaque route est une arête du graphe), visionnez cette vidéo pour en savoir plus.

Activités débranchées

En général, on recherche le chemin le moins long, le plus rapide, ou le moins cher ...

Tous les chemins mènent à Rome, mais pour un parmesan (un habitant de Parme !):

Quel est le moins long ?

Le plus rapide ?

Le moins cher ?

Est-ce le même chemin dans les trois cas ?

Une autre activité

Les deux cartes suivantes représentent 

  • à gauche : le trajet en miles du train Expressways in the Chicago area 

  • à droite la durée des différentes étapes.

  • Déterminer le plus court trajet de Buffalo Grove à South Holland.

  • Déterminer le trajet le plus rapide pour relier les deux mêmes villes.

Un programme...

La bibliothèque Python pyroutelib3 propose des outils pour calculer des itinéraires à partir de données d'Open Street Map

Pour cela il faut au minimum la version 3.6 de python.. ( 3.4 pour EduPython...à ce jour)

C'est pourquoi nous utiliserons Spyder lancé à partir de WinPython...

( WinPython s'installe sur une clé USB et est conçu pour fonctionner avec Windows)

  • Lancez Spyder.exe (attendre...)

Au lycée il contient déjà les bibliothèques dont nous avons besoin

Dans le cas contraire :

  • Dans le dossier WPy, lancez WinPython Command Prompt

  • Puis écrivez : pip install pyroutelib3 (attendre la fin de l'installation)

  • Recommencez avec : pip install geopy et pip install folium

Nous sommes prêts :

Voici un premier programme qui détermine une route ( en voiture) entre le lycée jean moulin de Draguignan et le lycée du val d'argens du Muy.

from pyroutelib3 import Router
lat1=43.53520
lon1=6.47070
lat2=43.47187
lon2=6.54500
router = Router("car")
depart = router.findNode(lat1, lon1)
arrivee = router.findNode(lat2,  lon2)
status, route = router.doRoute(depart, arrivee)
if status == 'success':
    routeLatLons = list(map(router.nodeLatLon, route))

Une fois l’exécution terminée ( cela peut -être long)...

Dans l'explorateur de variables regardez la variable routeLatLon.

Celle-ci contient 334 couples de coordonnées..

C'est à dire : Les différents points par lesquels il faut passer pour se rendre du point de départ jusqu'au point d'arrivée (en passant bien évidemment par les routes définies dans Open Street Map).

Quelques explications sur le programme proposé :

  • Nous commençons par importer la bibliothèque "pyroutelib3" avec la première ligne "from pyroutelib3 import Router"

  • Les 4 lignes suivantes initialisent les coordonnées du point de départ et d'arrivée

  • La cinquième ligne permet de définir le véhicule qui sera utilisé pour effectuer le trajet. Dans notre cas, nous utilisons une voiture ("car"), mais il est possible de choisir d'autres moyens de transport : cycle, foot, horse, tram, train

  • Les 2 lignes suivantes recherchent le point de départ et le point d'arrivée.

  • La ligne "status, route = router.doRoute(depart, arrivee)" permet d'effectuer le calcul de l'itinéraire.

  • La dernière ligne est exécutée uniquement si le calcul est mené à son terme ("if" de la ligne précédente). La variable "routeLatLons" contient la liste des coordonnées des points de cheminement (points qui constituent le chemin entre le point de départ et le point d'arrivée)

Modifiez ce programme pour voir le trajet proposé entre deux villes de votre choix ( ne les prenez pas trop éloignées..)

En faisant afficher une carte

Testez ce programme :

from pyroutelib3 import Router
import folium
import webbrowser
lat1=43.53520
lon1=6.47070
lat2=43.47187
lon2=6.54500
router = Router("car")
depart = router.findNode(lat1, lon1)
arrivee = router.findNode(lat2,  lon2)
status, route = router.doRoute(depart, arrivee)
if status == 'success':
    routeLatLons = list(map(router.nodeLatLon, route))
    
c= folium.Map(location=[lat1, lon1],zoom_start=10)
for indice,coord in enumerate(routeLatLons):
    if indice%10==0:
        coord=list(coord)
        folium.Marker(coord).add_to(c)
c.save('maCarte_2.html')
webbrowser.open('maCarte_2.html')

Modifiez le pour faire apparaître sur une carte un itinéraire entre deux villes de votre choix.. à pied, en vélo ou en voiture

AccueilIntroduction > Itinéraires > Calcul d'itinéraires< PrécédentSuivant >