7.4 - Calculs d'itinéraires

Comme vous avez pu le constater quand vous avez travaillé sur Open Street Map, il est possible de définir les voies de communication (principalement les routes). La base de données OSM contient donc les routes (enfin, la plupart des routes...). En utilisant ces données, il est possible de développer des outils capables de calculer des itinéraires routiers (comme le propose tous les logiciels "GPS" : Waze, ViaMichelin, Mappy...) : vous renseignez votre lieu de départ, votre lieu d'arrivée puis le logiciel calcule votre itinéraire. Ce calcul d'itinéraire repose sur des algorithmes relativement complexes, par exemple l'algorithme de Dijkstra qui permet d'obtenir le plus court chemin entre deux points.

Veillez documenter votre progression sur Microsoft Word.

ACTIVITÉ 1 : Comprendre l'algorithme de Dijkstra.

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. Expliquez en quelques lignes le principe de l'algorithme de Dijkstra. 

ACTIVITÉ 2 : Calculer un itinéraire avec Python.

En utilisant le logiciel PyCharm, saisir le code ci-dessous. Ouvrez un nouveau projet Python nommé 'itinéraires'.  Ensuite, créez un nouveau fichier de Python nommé 'itin'.

Installez la bibliothèque pyroutelib3 et Folium.

File - Settings - Project - Python Interpreter - + - Cherchez " pyroutelib3" et "Folium" - Install Package

Code :

Quelques explications sur le programme proposé dans l'Activité 2 :

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

• La deuxiè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 permettent de définir le point de départ et le point d'arrivée. Nous avons "router.findNode(latitude, longitude)", il suffit de renseigner la latitude et la longitude du lieu.

• 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).

• La boucle 'for' qui permet de parcourir la liste de coordonnées (contenue dans la variable "routeLatLons") et d'ajouter un marqueur pour chaque couple de coordonnées. 

ACTIVITÉ 3 : Défi.

Modifiez le programme de l'Activité 2 pour qu'apparaisse sur une carte un itinéraire de votre choix (en définissant le point de départ, le point d'arrivée et le type de véhicule).