Aller au contenu

Calcul et affichage d'itinéraires autour de Grenoble

On va travailler sur un graphe du réseau routier autour de Grenoble, dont les sommets sont représentés sur l'image suivante :

Ce graphe a été extrait depuis les données de la carte collaborative OpenStreetMap grâce à une bibliothèque python spécifique puis remis dans un format plus simple.

Code de création du graphe (juste pour information) 
import osmnx as ox

# lycée marie curie
location_point = (45.146073410460936, 5.717637790721994)

# create network from point, inside bounding box of N, S, E, W each 10km from point
G = ox.graph_from_point(location_point, dist=10000, dist_type="bbox", network_type="drive")

position_sommet = dict()

for i in G.nodes:
    lat = G.nodes[i]["y"]
    lon = G.nodes[i]["x"]
    position_sommet[i] = (lat,lon)

graph = { id : [] for id in position_sommet }

for a,b,c in G.edges:
    data = G.edges[a,b,c]
    longueur = float(data["length"])
    maxspeed = data["maxspeed"] if "maxspeed" in data else 50
    maxspeed = float(maxspeed if not isinstance(maxspeed,list) else maxspeed[0])
    oneway = data["oneway"]
    name = data["name"] if "name" in data else "Sans Nom"
    graph[a].append((b,longueur,maxspeed,name))
    if not oneway:
        graph[b].append((a,longueur,maxspeed,name))

import pickle
pickle.dump((position_sommet,graph),open("graph.raw","wb"))

# création de l'image affichée sur le site
ox.plot_graph(G,node_color="r",node_size=2,save=True,filepath="grenoble.png",show=False)

Vous pouvez télécharger ce graphe ici.

Créez un fichier python au même endroit que le fichier téléchargé, et récupérer les données avec :

import pickle
position_sommet, graph = pickle.load(open("graph.raw","rb"))

  • position sommet est un dictionnaire qui à chaque identifiant de sommet (un nombre) associe le tuple (latitude, longitude) correspondante.

  • graph est un dictionnaire qui à chaque identifiant de sommet associe la liste de ses voisins sous forme de tuples (identifiant du voisin, longueur en mètres de la route, vitesse maximale sur cette route, nom de la route).

De manière plus schématique avec les types :

position_sommet:dict { id:int -> (latitude:float, longitude:float)}

graph:dict { id:int -> list [ (id_voisin:int, longueur:float, vmax:float, nom:str) ] }

Rappel de la manière de parcourir ces structures :

# parcourir les positions des sommets :
for id_sommet in position_sommet:
    latitude, longitude = position_sommet[id_sommet]

# parcourir les voisins d'un sommet
# graph[id_sommet] étant une liste de tuple on peut mettre
# plusieurs variables qui prendront chaque valeur du tuple
# dans la boucle for
for id_voisin, longueur, vmax, nom in graph[id_sommet]:
    ...

1 : Trouver le sommet le plus proche des points de départ/arrivée

Comme il n'est pas très simple de faire sélectionner les points de départ/arrivée (les sommets ont juste des numéros et des positions), on va faire choisir le départ et l'arrivée avec des coordonnées GPS (latitude et longitude).

Étape 1: Créez une fonction id_plus_proche_sommet(latitude, longitude) qui prend en paramètre des coordonnées GPS (de type float chacune) et renvoie l'identifiant du sommet le plus proche.

conseil

Vous allez devoir parcourir tous les sommets, en mémorisant l'id et la distance de celui le plus proche.

Vous pouvez faire un calcul de distance très approximatif par exemple la distance de manhattan : abs(lat1 - lat2) + abs(lon1 - lon2).

Étape 2: Allez sur openstreetmap ici, et choisissez (à peu près dans la "zone" représentée par l'image au début) un point de départ et un point d'arrivée pour un calcul d'itinéraire. Pour cela clic-droit sur la carte et "Afficher l'adresse" puis dans la barre à gauche vous pouvez copier/coller les valeurs de latitude et longitude. Mettez les dans votre code dans des variables lat_depart, lon_depart, lat_arrivee, lon_arrivee. Puis utilisez votre fonction de l'étape 1 pour obtenir les identifiant des sommets id_depart et id_arrivee.

2 : Parcours en largeur

On va faire un parcours en largeur depuis le sommet de départ comme dans les TP précédents, pour cela on va utiliser comme structures de données :

# un dictionnaire qui à chaque sommet associe si il a été visité
dejavu = { id_sommet : False for id_sommet in position_sommet }

# un dictionnaire qui à chaque sommet associera le sommet qui a permis de l'atteindre
# cela permettra de recréer le chemin à la fin du parcours
precedent = dict()

# une file qui contient des tuples :
# (distance en étapes, id du sommet, id du sommet précédent)
from collections import deque
file = deque()
# pour ajouter dans la file le sommet de départ
# (qui n'a pas de sommet précédent donc on met None)
file.append((0, id_depart, None))

# pour récupérer un élément de la file on utilisera:
# (triple création de variable possible car popleft renvoie un tuple à 3 éléments)
# distance, id_sommet, id_precedent = file.popleft()

Etape 3: Codez le parcours en largeur en utilisant ces structures de données. On rappelle le pseudo-code de l'algorithme :

Créer une file avec le triplet du sommet de départ
Initialiser les dictionnaires dejavu et precedent
Tant que la file n'est pas vide (utilisez len):
    récupérer un sommet de la file
    le marquer comme vu dans dejavu
    marquer son sommet précédent dans precedent
    pour chacun de ses voisins:
        si ce voisin n'est pas déjà vu:
            rajouter le triplet associé dans la file
            marquer ce voisin comme déjà vu (pour ne pas les ré-enfiler)

Exécuter le code et vérifier à la fin que dejavu[id_arrivee] vaut True, ce qui signifie que le parcours a atteint le sommet d'arrivée.

Étape 4: On veut maintenant reconstruire le chemin, sous forme d'une liste de tuples (latitude, longitude) de chacun des sommets traversés.

Pour cela on procède à l'envers : partez avec comme chemin une liste vide, et une variable sommet qui contient l'id du sommet d'arrivée. Tant que la variable sommet n'est pas égale à l'id du sommet de départ, ajoutez les coordonnées du sommet à la fin de la liste chemin (grâce au dictionnaire position_sommet), et décalez le sommet d'un cran en arrière (grâce au dictionnaire precedent). À la fin vous pouvez renverser le chemin pour l'avoir dans le bon sens avec chemin.reverse() : cette méthode modifie la liste en place et ne renvoie rien.

Affichez un petit message avec la taille du chemin trouvé, et vérifiez que le contenu de la liste semble valable.

Étape 5: Pour visualiser le chemin sur une carte, on peut utiliser la bibliothèque folium qui permet de créer des cartes javascript avec un fond de d'openstreetmap dans une page html :

import folium
carte = folium.Map((45.14, 5.71))
folium.PolyLine(chemin).add_to(carte)
carte.save("carte.html")

Cela enregistre un fichier carte.html que vous pouvez ouvrir avec Firefox pour voir le chemin trouvé !

3 : Algorithme de Dijkstra pour le plus court chemin

Le parcours qu'on a fait donne le plus petit nombre d'étapes, mais il y a des routes plus longues que d'autres (on dit que le graphe est pondéré : les arêtes n'ont pas toutes le même poids).

L'algorithme de Dijkstra permet de modifier le parcours en largeur pour trouver quand même le plus court chemin. Il s'agit essentiellement de remplacer la file par une file à priorité.

Dijkstra

Le mathématicien et informaticien néerlandais Edsger Dijkstra (1930-2002) est à l'origine de cet algorithme, ainsi que de nombreux autres travaux sur les langages de programmation.

File à priorité

Une file à priorité (priority queue en anglais) permet :

  • d'enfiler un élément comme pour une file
  • de récupérer le plus petit élément présent dans la file

C'est à dire qu'au lieu de sortir les éléments dans l'ordre, on les sort le plus petit d'abord.

En python on peut utiliser le module heapq qui se sert des listes pour représenter une file à priorité. En pratique la structure est une liste mais on utilise des fonctions du module pour ajouter/enlever des élements:

from heapq import heappush, heappop
# une file à priorité vide = liste vide
file_a_priorite = []
# enfiler un élémént
heappush(file_a_priorite, element)
# sortir le plus petit élément
element = heappop(file_a_priorite)

Du parcours en largeur à Dijkstra

L'idée est juste de ne pas prendre à chaque fois le sommet qui avait été ajouté en premier, mais celui qui est le moins loin du sommet de départ. Comme on avais mis dans la file des tuples avec la distance en premier, et que python compare les tuples avec l'ordre lexicographique, le plus petit élément sera bien le plus proche du départ.

Autre changement : on ne peut pas marquer comme déjà vu un sommet juste après l'avoir mis dans la file car il se peut qu'on trouve un meilleur chemin ensuite. Du coup, c'est possible qu'un sommet soit inséré plusieurs fois dans la file. Grâce à la file à priorité, la première fois qu'on le sortira de la file sera celle du plus court chemin. On le marque comme déjà vu à ce moment là, et on ignorera les fois suivantes où on le sort de la file.

Le pseudo code modifié à partir du parcours en largeur :

Créer une file à priorité avec le triplet du sommet de départ
Initialiser les dictionnaires dejavu et precedent
Tant que la file n'est pas vide (utilisez len):
    récupérer un sommet de la file
    S'il n'est pas déjà vu:
        le marquer comme vu dans dejavu
        marquer son sommet précédent dans precedent
        pour chacun de ses voisins:
            si ce voisin n'est pas déjà vu:
                rajouter le triplet associé dans la file 
                (utilisez la vraie distance cette fois !)
                marquer ce voisin comme déjà vu (pour ne pas les ré-enfiler)

Étape 6: Copiez/collez votre code pour le parcours en largeur à la suite (le but est que votre programme fasse les deux pour pouvoir comparer), et faites les modifications pour qu'il devienne un algorithme de Dijkstra.

Affichez avec un print() la longueur du chemin trouvé (en mètres donc).

On récupère le chemin de la même manière, et vous pouvez l'ajouter à la même carte avec une autre couleur :

folium.PolyLine(chemin, color="green").add_to(carte)

Vous pouvez maintenant observer les deux trajets dans le navigateur !

4 Extensions

  1. Modifiez votre algorithme de Dijkstra pour qu'il renvoie l'itinéraire le plus court en temps si on roule à la vitesse maximale autorisée tout le temps (ce n'est bien sûr pas le cas en vrai).

  2. Faites un affichage avec des print du chemin à parcourir ("Faites 300m sur la Rue de la Paix", etc)

  3. Améliorez cet affichage avec les sens des virages, pour pouvoir dire "Tournez à droite sur la rue machin". Pour cela, si vous passez par trois points A,B,C, calculez les coordonnées des vecteurs AB et BC. Ensuite le sens droite/gauche est donné par le signe du produit vectoriel \(x_{AB}\times y_{BC} - x_{BC}\times y_{AB}\)

  4. Le module heapq implémente une structure de tas binaire : un tas (min) est un arbre dont la valeur de chaque noeud est inférieure à la valeur de ses enfants. La valeur minimale est donc toujours la racine. Pour obtenir une file à priorité il faut coder des opérations d'ajout, et d'extraction de la racine, qui conservent cette propriété. Lisez la page wikipédia sur cette structure et essayez de la coder et de la tester:

    • soit avec une classe TasBinaire
    • soit avec des listes python et des fonctions comme le fait le module heapq, avec l'astuce pour représenter un arbre binaire parfait dans un tableau (donnée sur la page wikipédia).