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 :
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.
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.
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
.
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 :
.osm
)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.
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 :
area_1.geojson
, area_2.geojson
, area_3.geojson
…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.
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
).
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 :
cost
et reverse_cost
).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 !
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 :
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.