CC By Sa Constantin Litvak

OpenStreetMap

Pour recontextualiser, OpenStreetMap est un projet de cartographie participatif et sous licence libre. L’objectif premier était de cartographier les rues du monde entier, aujourd’hui il va bien au-delà de cette thématique. La base de données OpenStreetMap contient un réseau de voiries annotées d’attributs tel que le nom, le type - rue, autoroutes… - ou encore des limitations de vitesse. Contrairement aux autres « fournisseurs » de données cartographiques, la mise à disposition des modifications est immédiate : pas de validation à priori et diffusion en continue des flux de modifications.

Calcul d’itinéraires

Un calculateur d’itinéraires est un logiciel qui va utiliser un réseau de voiries - graphe - pour déterminer le chemin le plus approprié. Ce chemin est rarement le plus court en distance. Par exemple, en voiture le conducteur souhaite utiliser le chemin le plus rapide. En conséquence, il utilise des voies plus longues mais où il se déplace plus vite, il doit de fait respecter des contraintes telles que les sens uniques. Nous allons donc chercher à calculer l’itinéraire dont le « coût » est le plus faible. À chaque segment du graphe est associé un coût. Celui-ci est notamment calculé en fonction de la longueur et des attributs tel que le type de voie. Le calcul d'itinéraires peut aussi inclure par exemple le fait que la route monte lorsque qu'il est réalisé pour un déplacement en vélo.

Le calcul de matrice fait également partie des fonctionnalités de bases récurrentes. C’est un « distancier » - en unité de coût- qui donne par exemple le temps de parcours entre un ensemble de villes.

Calculateurs d’itinéraires avec OpenStreetMap

L’écosystème d’OpenStreetMap contient plusieurs logiciels dédiés à cette tache. Ils sont optimisés pour réduire le temps de calcul d’un itinéraire de point à point, c’est le cas d’usage nominal. Le corollaire de cette vitesse d’exécution est qu’elle est la conséquence d’un pré-calcul coûteux en temps et qui réduit la flexibilité des demandes de calculs possibles. Ces solutions étant aptes uniquement à traiter des données OpenStreetMap, elles fournissent des « profils ». Ces profils décrivent qu’elles sont les données d’OpenStreetMap à retenir parmi celles disponibles et comment calculer le « coût » de chaque segment.

Parmi ces calculateurs fait pour répondre rapidement à des demandes à grande échelle on trouve :

• OSRM : implémentant les algorithmes de Dijkstra Multi-Niveau (MLD) et de Contraction de Hiérarchie (CH),
• Graphhopper : implémentant les algorithmes de Dijkstra et de Contraction de Hiérarchie (CH),
• Valhala : implémentant l'algorithme de Dijkstra Multi-Niveau (MLD).

Dans les faits, ce n’est pas l’algorithme de Dijkstra qui est directement implémenté, mais ce sont des améliorations, typiquement un A-star bidirectionnel.

Calculateur d’itinéraires génériques

À côté de ces solutions spécialisées, d’autres utilisant des sources de données génériques existent. La plus répandue est pgRouting. Du fait de sa généricité elle ne vient pas avec un importeur de données, ni des profils ou des fonctions de coût, ni même avec son propre système de stockage. pgRouting est un module pour la base de données Postgres. Il est donc nécessaire d’importer au préalable les données en base, de préparer le graphe et de l’extraire à la demande pour le fournir avec le coût des segments à pgRouting, qui va alors faire le calcul.

À l’exception de l’import des données et de la mise sous forme de graphe routable, pgRouting n’utilise pas de pré-calcul. Le temps de préparation est court mais le temps unitaire de calcul d’un itinéraire est donc plus long. En conséquence, les calculs utilisent des algorithmes simples dérivés de Dijkstra. Cette approche permet toutefois beaucoup plus de flexibilité : la fonction de coût ainsi que le graphe à router peuvent être dynamiques selon la demande de calcul à faire (« je veux bien prendre des pentes modérées en vélo avec ma remorque, mais je ne veux pas passer par le centre-ville »).

Import de données OpenStreetMap pour pgRouting

Importeurs génériques de données OpenStreetMap

Plusieurs outils de l’écosystème existent pour lire un fichier d’extrait d’OpenStreetMap (.pbf), le filtrer, l’importer en base de données et appliquer des post-traitements. Ils peuvent également importer des fichiers de mise à jour de données qui sont disponibles toutes les minutes ou quotidiennement.

• Osmosis
• osm2pgrouting
• imposm

Le schéma des données en base est fonction de l’outil et du paramétrage. Mais dans tous les cas, ces outils génériques n’importent pas directement un graphe de voirie nécessaire pour pouvoir utiliser pgRouting efficacement.

pgRouting nécessite en entrée pour son calcul une liste de segments décrits par un identifiant de départ, un identifiant d’arrivée et le coût que représente la traversée du segment. Le calcul passe de segment en segment en utilisant l’identifiant d’arrivée d’un segment qui est également l’identifiant de départ des segments suivants potentiels. pgRouting ne nécessite pas la géométrie des segments.

L’étape qui fait suite à l’import est donc logiquement de constituer la liste de ces segments depuis les données OpenStreetMap importées.

osm2pgRouting

La solution osm2pgRouting est justement un importeur de données OpenStreetMap pour pgRouting. Celui-ci lit l’ancien format de données XML et comprend l’ontologie des données OpenStreetMap. Il ne contient cependant pas de profil d’interprétation des données pour le calcul du coût des segments.

Cette solution est peu maintenue et ne possède en particulier pas la capacité d’utiliser le nouveau format de fichiers binaires d’extraits d’OpenStreetMap (.pbf), ni la capacité de charger de gros volumes de données. Pour finir, il ne permet pas de faire des mises à jour depuis OpenStreetMap.

Utiliser un importeur générique, le paramétrer et créer le graphe de segments

L'objectif est de pourvoir faire des calculs d’itinéraires de courtes distances sur un réseau de voirie OpenStreetMap sur de grandes zones. Les données doivent être maintenues à jour très régulièrement de façon à pouvoir les corriger dans OpenStreetMap si le résultat d’un calcul d’itinéraire n’est pas satisfaisant et de profiter quasiment immédiatement de la correction dans le calculateur d’itinéraire (1 minute maximum de délai).

Pour atteindre cet objectif, l'utilisation de pgRouting est nécessaire, car il n'a pas besoin de phase de pré-calcul. Des mises à jour rapides depuis les données OpenStreetMap avec un importeur de données générique sont également nécessaires. Au vu de l’utilisation d’un importeur générique, il va également falloir réaliser la création du graphe de segments.

Import avec Imposm

Imposm est l’outil le plus récent pour lire des données d’OpenStreetMap et les importer en base de données. Comme osm2pgsql, il est orienté pour la production de cartes mais peut être utilisé pour d’autres tâches.

Les données d’OpenStreetMap sont constituées de nœuds (nodes, points), de lignes brisées (ways), de relations (groupes d’objets) et d’attributs libres (tags). Nous nous intéressons ici à un réseau de voirie qui est constitué dans OpenStreetMap de « ways » annotées avec certains « tags » (la voirie est décrite par les tags ayant pour clé highway). Un fichier de mapping Imposm est utilisé décrivant l’import de données OpenStreetMap à réaliser.

tables:
  ways:
    type: linestring
    mapping:
      highway: [__any__]
    columns:
    - name: osm_id
      type: id
    - name: geometry
      type: geometry
    - name: tags
      type: hstore_tags

Configuration de Imposm pour charger les lignes brisées (« linestring ») avec un tag highway=* dans une table (« ways » préfixé automatiquement par « osm_ », soit « osm_ways ») contenant l’identifiant OpenStreetMap, la géométrie et l’ensemble des tags de l’objet

Créer un réseau navigable

Il est ensuite nécessaire de convertir cet ensemble de lignes brisées en segments. Il existe une différence de topologie entre les données importées et celles nécessaires aux calculs d’itinéraires. Pour les calculs, nous avons besoin de segments allant d’une intersection à la suivante. Cependant, les lignes brisées d’OpenStreetMap n’imposent pas cette structure. Une ligne brisée peut passer une intersection sans s’y terminer et peut également très bien se terminer entre deux intersections.

Topologie des données dans OpenStreetMap et découpage aux intersections.

La première étape est donc d’extraire toutes les intersections. Il ne s’agit pas des intersections géométriques des lignes brisées, mais des intersections aux sens topologiques du réseau de voirie d’OpenStreetMap. C’est-à-dire quand des lignes brisées sont explicitement connectées entres elles par un nœud. Ces intersections sont numérotées et sont nommées « sommets » du graphe. En particulier, on ne veut pas pouvoir sauter d’un pont à une voie passant en dessous à la verticale à l’endroit où elles se croisent spatialement.

SELECT
    (ST_DumpPoints(geometry)).geom AS point
FROM
    import.osm_ways
GROUP BY
    point
HAVING
    count(*) >= 2

Collecte des intersections

La seconde étape est de découper les lignes brisées d’OpenStreetMap selon ces mêmes intersections. Ce passage de lignes brisées à des segments ou tronçons est nommé « Segementize » en anglais. Pour cela nous n’utilisons pas la fonction ST_Segmentize() de PostGIS, car elle sert à découper suivant une longueur. La fonction appropriée à notre cas est ST_Split() qui découpe une géométrie suivant une autre.

SELECT
    osm_id,
    (ST_Dump(ST_Split(geometry, ST_Collect(osm_ways_junctions.point)))).geom AS geometry,
    tags
FROM
    import.osm_ways
    JOIN imposm2pgr.osm_ways_junctions ON
        osm_ways_junctions.point && osm_ways.geometry
GROUP BY
    osm_id,
    geometry,
    tags

Découpe de lignes brisées suivant les intersections - de voirie topologique - qui intersectent spatialement sa géométrie

Les extrémités de chaque segment doivent ensuite être rapprochées des numéros d’intersections.

Pour chaque segment, il ne reste plus qu’à le traiter comme un élément du réseau sur lequel on souhaite calculer des itinéraires. Cela revient à le stocker, en extrayant les tags OpenStreetMap souhaités et calculer éventuellement le coût pour traverser le segment (si ce coût n’est pas dynamique lors de la requête).

Pour ce faire nous pouvons utiliser la définition de table de base de données suivante :

CREATE TABLE  network (
    id serial PRIMARY KEY,
    osm_id bigint NOT NULL, -- required field, for update
    source_vertex_id int, --required field, for routing
    target_vertex_id int, -- required field, for routing
    geometry geometry(LineString,3857) NOT NULL, -- Advised, for display
    cost float,
    highway varchar,
    name varchar
);

Si l’on souhaite par exemple faire un calculateur d’itinéraire au plus court, le coût peut simplement être la longueur du segment : ST_Length(geometry). Le nom de la voie va être extrait des tags d’OpenStreetMap s’il est disponible avec tags->'name' (en utilisant la syntaxe de l’extension hstore de Postgres).

Mise à jour

Imposm permet de se mettre en attente de mise à jour des données OpenStreetMap et de les appliquer lorsqu’elles sont disponibles. Il va donc les télécharger et les appliquer en base de données en fonction du mapping défini lors de l’import. Les modifications sont effectuées sur la table des lignes brisées d’OpenStreetMap. Il convient de les répercuter sur les segments du graphe.

Pour cela un trigger de la base de données collecte les modifications faites sur les lignes brisées par Imposm. À la fin de la transaction, il supprime tous les segments impactés et en recalcule une nouvelle version en passant par les étapes d’extraction des intersections et de découpage en segments. Cette procédure de mise à jour est minimale dans le sens où elle ne modifie que les segments du graphe réellement modifiés dans OpenStreetMap et est donc rapide.

Calculer un itinéraire avec pgRouting

Il est ensuite possible d’utiliser le graphe chargé et mis à jour en continu pour calculer des itinéraires à l’aide uniquement de pgRouting utilisé de façon classique.

SELECT
    ST_Collect(network.geometry) AS geometry,
    sum(path.cost) AS total_cost
FROM
    pgr_dijkstra('SELECT * FROM selected_network', 1480, 1503, true) AS path
    JOIN network ON
        network.id = path.edge

Calcul de la géométrie d’un itinéraire

Visualisation de l’itinéraire sur le graphe

ImpOsm2pgRouting

La nouvelle approche décrite ici est implémentée dans le projet « ImpOsm2pgRouting ». Il se veut une alternative pour pouvoir charger de gros volumes de données OpenStreetMap en base de données et les utiliser avec pgRouting tout en maintenant la base de données synchronisée avec OpenStreetMap. Cette synchronisation peut être faite avec un retard maximum d’une minute et ainsi permettre de corriger la voirie dans OpenStreetMap et d’en profiter quasiment immédiatement dans le calcul d’itinéraire.

Ce projet permet de charger et garder à jour les données. Il ne force pas la façon dont doit être stocké le graphe du réseau, ni comment il doit être utilisé. Cela reste à la charge de l’utilisateur.

Il peut être utilisé comme une brique externe de gestion des données du réseau sur un nouveau projet ou un projet existant, notamment en l’utilisant sous forme de container Docker.

Le projet est disponible sur Github et ouvert à la contribution :

https://github.com/makinacorpus/ImpOsm2pgRouting

Vous rencontrez des problématiques de calcul d’itinéraires ? Contactez-nous, nous pouvons vous aider !