Le routage open-source, c’est maintenant

L’objet de ce billet est d’expliquer comment calculer l’itinéraire optimal entre deux points du globe. Sur le plan pratique, chacun sait évidemment comment s’y prendre. Mais ce que l’on cherche à comprendre ici, c’est comment construire soi-même l’outil de calcul. Il existe plusieurs API commerciales pour y parvenir : celle de Google (Google Distance Matrix), celle de Bing (Bing Routes) ou encore celle d’AOL (MapQuest). Le problème, c’est que ces solutions sont… commerciales, c’est-à-dire que leur gratuité comporte des limites. Celles-ci sont de trois ordres : limites d’extraction, d’utilisation et de diffusion des données. C’est pourquoi notre propos est ici d’envisager la création d’un outil 100% open-source.

Calculer l’itinéraire optimal entre 2 points du globe, c’est construire une matrice de distances ou de durées. Pour ce faire, nous avons besoin de 7 composants essentiels, que nous voulons donc tous open-source.

• Un réseau routier open-source : ce sera le projet OpenStreetMap (OSM).
• Un outil de manipulation de données OSM open-source : ce sera Osmosis.
• Un serveur de tuiles cartographiques open-source : ce sera Mapnik ou Osmarender.
• Un moteur de routage open-source : ce sera GraphHopper ou OSRM
• Un outil d’interrogation de données OSM par nom (reverse geocoding) open-source : ce sera Nominatim.
• Une librairie de visualisation open-source : ce sera OpenLayers ou Leaflet.
• Une distribution open-source : ce sera une Ubuntu Linux, disons la version 12.04 ou supérieure.

Détaillons les 6 premiers composants, relatifs à la géolocalisation proprement dite.

OpenStreetMap (OSM) est un projet qui a pour but de constituer une base de données géographiques libre du monde. C’est un vaste projet collaboratif qui s’inscrit dans le courant de la culture libre, auquel chacun est libre de contribuer, et qui permet à chacun de créer de cartes sous licence libre, sur l’unique base du volontariat. OpenStreetMap utilise le système GPS et diverses sources de données directement importables (comme le réseau routier des Pays-Bas ou la base de données américaine TIGER). Le projet est né en 2004 sous l’impulsion de Steve Coast, au University College de Londres. Le projet OpenStreetMap relève de la géomatique 2.0 et est aussi une contribution à ce qui est appelé la néogéographie, dont les outils composent le GeoWeb.

Osmosis est, selon le wiki qui lui est consacré, une application java en ligne de commande pour la manipulation des données OSM. L’application se compose d’une série d’outils qui peuvent être chaînés pour effectuer une opération de grande envergure. Par exemple, il comporte des éléments de lecture et d’écriture de la base de données ou d’un fichier, des composants pour calculer et appliquer un ensembles de modifications aux sources de données, des composants pour le tri des données, etc. Il a été rédigé de façon à ce qu’il soit facile d’ajouter de nouvelles fonctionnalités sans ré-écriture des tâches courantes telles que la manipulation de fichiers ou de bases de données.

GraphHopper et OSRM (Open Source Routing Machine) sont des moteurs de routage Java, destinés aux applications serveur, bureau et mobile (Android, iOS). Leur rôle est de calculer le plus court chemin, en temps ou en distance, entre un point A et un point B, par des modes différents : en voiture, à pied, à vélo, à cheval. La différence entre GraphHopper et OSRM tient principalement dans les algorithmes utilisés pour résoudre le problème du plus court chemin. Il existe principalement trois algorithmes. L’algorithme de Dijkstra interprète le réseau routier comme un graphe connexe pondéré (à poids positifs). L’avantage est qu’il trouve systématiquement le chemin le plus court, mais au prix d’une complexité algorithmique importante. Ce n’est donc pas le plus rapide. L’algorithme A* est une variante de l’algorithme de Dijkstra qui explore préférentiellement les lieux situés dans la direction du point final. Il est donc plus rapide que l’algorithme de Dijkstra, mais ne garantit pas de trouver le chemin optimal. L’algorithme de contraction de hiérarchies utilise une méthode plus complexe pour accélérer le calcul du plus court chemin, en créant une version pré-calculée et contractée du graphe représentant le réseau : il commence par réduire le graphe routier en éliminant les nœuds inutiles et en introduisant des raccourcis, il calcule ensuite le plus court chemin avec l’algorithme Dijkstra, puis étend le graphe pour obtenir le plus court chemin sans les raccourcis. C’est la méthode utilisée par OSRM, alors que GraphHopper peut utiliser au choix les trois méthodes.

Nominatim est un outil permettant de chercher des données OSM par leur nom (d’où son nom qui signifie en latin « par le nom ») et leur adresse et de générer des adresses potentielles à partir d’un point OSM. Il s’agit donc d’un géocodage inversé, qui attribue des coordonnées géographiques à une adresse correctement renseignée. Cette fonction est indispensable aux applications de géolocalisation, puisque la plupart des utilisateurs humains effectuent des recherches par adresse (ville, arrondissement, rue, code postal, lieu dit…). Nominatim gère donc la partie géocodage de l’interaction entre la base de données géographiques et le client (la partie rendu des tuiles étant gérée par la couche Mapnik).

Les serveurs de tuiles Mapnik et Osmarender sont plus délicats à décrire et à mettre en place, car ils comprennent eux-mêmes plusieurs sous-composants. Un serveur de tuiles comporte pas moins de 5 composants :

• Un outil de conversion de données OSM en données SQL : osm2pgsql.
• Une base de données : postgreSQL ou postGIS.
• un logiciel de rendu de carte : Mapnik, Osmarender.
• Un démon de rendu : Renderd ou Tirex.
• Un module pour gérer l’envoi des tuiles au client via Apache.

Enfin, OpenLayers et Leaflet sont les bibliothèques de fonctions JavaScript permettant la visualisation des tuiles de façon fluide sur un site web, en ajoutant un certain nombre de fonctions ergonomiques. Dans sa version 3, OpenLayers se recentre sur les fonctionnalités essentielles de l’API (à savoir la visualisation) et intègre désormais des éléments graphiques de type WebGL, afin d’exploiter au mieux l’accélération matérielle du processeur graphique du terminal. Leaflet, qui est aujourd’hui la bibliothèque officiellement utilisée par le projet OpenStreetMap, est une alternative plus simple et plus légère, ce qui la rend très adaptée aux smartphones et tablettes.

Voilà en gros comment est structuré un serveur de routage. Bien sûr, c’est en réalité plus compliqué que cela car il manque les relations entre les composants et la façon dont on les implémente. Pour avoir une vision de l’architecture précise d’ensemble, je reproduis ici le diagramme des composants d’un projet OSM tel qu’il est représenté sur le wiki du projet OSM.

Composants d’une architecture OSM

Pour en savoir plus, je vous recommande d’ailleurs la lecture du wiki du projet OpenStreetMap, assez complet pour réaliser soi-même un serveur de routage open-source.