Calculs d'itinéraires à grande échelle avec PgRouting

Les calculs d’itinéraires sont un type d’analyse spatiale très classique, permettant de connaître l’itinéraire le plus court d’un point A à un point B. Pour réaliser ces calculs, nous devons nous appuyer sur des données géographiques de bonne qualité. Cet article va vous présenter comment réaliser des calculs d’itinéraires à grande échelle simplement avec :

PostgreSQL, la base de données libre de référence pour les données relationnelles volumineuses
PostGIS, l’extension pour l’analyse géospatiale sur PostgreSQL
PgRouting, l’extension pour les calculs d’itinéraires sur PostgreSQL
OpenStreetMap, la base de données géographique mondiale de référence
Osm2PgRouting, l’outil d’import de données OpenStreetMap pour PgRouting
Osmium, un outil de traitement de données OpenStreetMap pour convertir le format de fichier, filtrer les données et découper en plusieurs zones.

Notez que d’autres outils existent pour réaliser des calculs d’itinéraires à grande échelle sur des réseaux complexes. Ces outils sont plus pertinents dans les cas d’usages classiques (calculs pour affichage sur une page web). Ici, utiliser PgRouting présente plusieurs avantages, notamment une mise en place simple (faible besoin en compétences d’administration système) et la gestion centralisée de toutes les données dans PostgreSQL.

Vue d’ensemble de la chaîne de traitement

Je passe volontairement sur l’installation des différents outils, qui est documenté sur leurs sites respectifs. L’installation dépend largement du système d’exploitation utilisé, mais reste la plus simple à mon avis sous GNU/Linux.

La logique de traitement que nous allons mettre en place est la suivante :

Extrait des données OpenStreetMap avec Geofabrik, découpage et filtre avec Osmium, import en base avec Osm2PgRouting, calcul d’itinéraire en base avec PgRouting

Commençons tout de suite par la récupération des données.

Télécharger un extrait OSM sur Geofabrik

Geofabrik est une société allemande spécialisée sur OpenStreetMap. Cette société propose des extraits quotidiens de la base OpenStreetMap, découpés par régions (continent, pays, région administrative). Vous pouvez donc télécharger la zone de votre choix, au format .osm.pbf (le plus compact et rapide à traiter). Ici, on récupère le fichier france-latest.osm.pbf.

Filtre thématique avec Osmium

L’outil d’import Osm2PgRouting est bien pratique, mais présente deux limitations qui ont leur importance dans le choix des traitements à mettre en place :

Il lit uniquement des fichiers OSM XML (format .osm)
Il charge l’intégralité des données d’entrée en mémoire vive pour réaliser son analyse avant import en base de données.

Nous devons donc nous assurer que les fichiers en entrée de cet outil soient les plus légers possibles. Heureusement, il est possible de réaliser l’import de manière progressive en découpant par zones géographiques distinctes nos données. C’est pourquoi on utilise l’outil Osmium : pour filtrer et découper le fichier PBF téléchargé en plusieurs fichiers OSM XML correspondants au réseau par zone géographique.

On commence donc par filtrer les données OpenStreetMap pour ne garder uniquement le réseau routier. À noter qu’il est possible de s’intéresser à d’autres réseaux (eau, électricité, gaz, Internet, chemins de fer…), à condition de changer quelques configurations. La commande pour filtrer avec Osmium est la suivante :

osmium tags-filter \
	france-latest.osm.pbf \
	w/highway=motorway,motorway_link,trunk,trunk_link,primary,primary_link,secondary,secondary_link,tertiary,tertiary_link,unclassified,residential \
	-f pbf,add_metadata=false \
	-o france-roads.pbf

On peut modifier les options de cette commande pour prendre par exemple toutes les routes (au lieu d’une sélection ici), ou justement sélectionner d’autres types d’objets. Le fichier en sortie france-roads.pbf contient donc uniquement le réseau routier.

Découpage géographique avec Osmium

Nous allons désormais découper ce fichier en plusieurs zones distinctes. Cette étape est fastidieuse car vous devez définir le découpage à mettre en œuvre. L’idée est d’avoir un fichier GeoJSON par zone distincte, plus un fichier JSON décrivant votre découpage pour Osmium. Pour vos zones, vous pouvez utiliser des découpages administratifs, ou créer une grille régulière avec QGIS. Au final, vous devez avoir :

Plusieurs fichiers GeoJSON, contenant chacun la géométrie de la zone concernée. On peut les nommer area_1.geojson, area_2.geojson, area_3.geojson…
Un fichier de configuration global nommé areas.json

Pour ce fichier areas.json, il doit avoir la structure suivante :

{
	"directory": "/tmp/",
	"extracts": [
		{
			"output": "area_1.osm",
			"polygon": {
				"file_name": "area_1.geojson",
				"file_type": "geojson"
			}
		},
		{
			"output": "area_2.osm",
			"polygon": {
				"file_name": "area_2.geojson",
				"file_type": "geojson"
			}
		},
		{
			"output": "area_3.osm",
			"polygon": {
				"file_name": "area_3.geojson",
				"file_type": "geojson"
			}
		}
	]
}

Vous devez avoir autant d’objets dans le tableau extracts que vous avez de zone à prendre en compte. Chacun de ces objets permet de connaître le nom du fichier GeoJSON à utiliser, et le nom du fichier OSM XML en sortie. Une fois tous ces fichiers en place, vous pouvez lancer la commande Osmium suivante :

osmium extract -c areas.json france-roads.pbf

Après quelques instants, vos fichiers filtrés et découpés, au format XML, seront disponibles dans le dossier de sortie choisi. On peut désormais créer la base de données.

Création de la base de données PostgreSQL

On commence donc par mettre en place la base et ses extensions :

CREATE DATABASE osmroads;
CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting;
CREATE EXTENSION hstore;

La base est désormais prête pour l’import des données. On utilise l’outil osm2pgrouting, qui transforme directement les données brutes OSM filtrées en données utilisables en base pour réaliser des calculs d’itinéraires. De nombreuses options sont disponibles, nous utiliserons ici les commandes suivantes :

# Import des premières zones
osm2pgrouting \
	-f /tmp/area_1.osm \
	-c /usr/local/share/osm2pgrouting/mapconfig_for_cars.xml \
	--tags \
	--addnodes \
	--no-index \
	-d osmroads -U postgres

# Import de la dernière zone (avec création des index)
osm2pgrouting \
	-f /tmp/area_n.osm \
	-c /usr/local/share/osm2pgrouting/mapconfig_for_cars.xml \
	--tags \
	--addnodes \
	-d osmroads -U postgres

La première commande est à répéter autant de fois que vous avez de zones lors du découpage. La dernière zone à importer utilise la seconde commande, qui lance la création des index en base de données. L’option --addnodes est essentielle pour permettre l’import progressif des données. Ces commandes peuvent prendre un certain temps à s’exécuter selon les capacités de votre machine.

Vous avez désormais à disposition une base prête à réaliser des calculs d’itinéraires pour automobile (principalement avec la table ways).

Calculer un premier itinéraire

L’extension PgRouting dispose de nombreuses fonctions pour réaliser toutes sortes de calculs. Ici, on va réaliser un premier calcul en utilisant l’algorithme A*. Il permet d’obtenir un chemin relativement court de manière efficace. Le calcul est à lancer en SQL de cette façon :

SELECT *
FROM pgr_bdAstar(
	'SELECT gid AS id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM ways', -- Requête de sélection
	2365623, -- ID noeud de départ
	1779025 -- ID noeud d'arrivée
) p;

La fonction pgr_bdAstar prend trois paramètres :

Une requête SQL, permettant de récupérer les chemins à prendre en compte. On peut ici par exemple filtrer certains chemins non-pertinents, ou changer les valeurs de coûts de traversée (cost et reverse_cost).
Deux identifiants de nœuds (point de départ et d’arrivée). Ceux-ci correspondent à la colonne id de la table ways_vertices_pgr. Ce sont les intersections et extrémités de chemins de votre réseau routier.

La requête va vous retourner ce type de réponse :

 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |    8 |    1 |        1
   3 |        3 |    6 |    9 |    1 |        2
   4 |        4 |    9 |   16 |    1 |        3
   5 |        5 |    4 |    3 |    1 |        4
   6 |        6 |    3 |   -1 |    0 |        5
(6 rows)

Chaque ligne correspond à un point de passage sur le graphe routier. Le premier est le point de départ, le deuxième le premier nœud intermédiaire, le troisième est le deuxième nœud intermédiaire… Jusqu’au nœud d’arrivée. À noter que si la requête ne renvoie pas de résultats, c’est qu’aucun itinéraire n’a été trouvé entre les deux points précisés. On retrouve en colonnes l’ordre de passage, le nœud visité, le segment visité, le coût de traversée du segment, et enfin le coût agrégé de l’itinéraire. Ce type d’interrogation simple peut être réalisé graphiquement à l’aide de QGIS et PgRoutingLayer.

Si l’on souhaite obtenir un résultat plus concis, à savoir la géométrie du parcours et son coût total, on peut joindre la table ways au résultat et fusionner les segments :

SELECT ST_LineMerge(ST_Union(w.the_geom)) AS geom, MAX(a.agg_cost) AS total_cost
FROM pgr_bdAstar(
	'SELECT gid AS id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM ways', -- Requête de sélection
	2365623, -- ID noeud de départ
	1779025 -- ID noeud d'arrivée
) a
LEFT JOIN ways w ON a.edge != -1 AND w.gid = a.edge;

Voilà, vous avez créé votre premier itinéraire !

Aller plus loin

Grâce à ces quelques conseils, vous êtes désormais en mesure de réaliser des calculs d’itinéraires à grande échelle avec un ensemble de logiciels plutôt portables. Vous pouvez adapter ce scénario à différents cas d’usages, et par exemple :

Changer de type de réseau : électrique, hydrographique, piéton, vélo… Vous pouvez imaginer toutes sortes de cas d’usages. La seule contrainte est d’adapter le fichier mapconfig.xml de osm2pgrouting selon les attributs utilisés.
Réaliser des calculs d’itinéraires en lot. Les fonctions “Many to many” de PgRouting permettent de calculer de n’importe quel point de départ vers n’importe quel point d’arrivée. Si vous êtes sur une logique de combinaisons départ > arrivée plus restreinte, l’idéal est de passer sur une fonction PLPgSQL pour boucler sur vos combinaisons.

Envie d’être accompagné sur ce sujet ? Je vous propose des formations sur ces thématiques, ou contactez-moi pour que nous discutions de vos besoins précis.

Calculs d’itinéraires à grande échelle avec PgRouting