pgRouting comme aide à la décision des Services d'Incendie et de Secours

Le 17 juin, Camptocamp participe au PG Day France 2021. Cette rencontre, organisée par la communauté francophone de PostgreSQL, était pour nous l’occasion de présenter nos travaux réalisés autour du routing (calculs routiers). Ces travaux ont été menés auprès de l’Agence du Numérique de la Sécurité Civile (ANSC) et dans le cadre du projet NexSIS 18-112.

Sauver des vies, comment ça marche ?

Imaginons une situation toute simple : Grand-Mère est tombée d’une échelle, elle est allongée par terre et ne répond plus. Heureusement, elle n’était pas seule : Papy appelle immédiatement le 112. Un opérateur prend son appel, et lui demande de décrire la situation. L'opérateur va alors renseigner les circonstances (Quoi ?), les victimes (Qui ?) et la localisation (Où ?) de cette situation d'urgence. Cela permettra d'adresser l'affaire aux intervenants compétents (pompiers, police, etc.) et en charge du secteur géographique concerné.

Une fois l’affaire transmise aux pompiers, on parle d’opération. Traiter une opération, c’est mettre en œuvre des moyens adaptés (ça ne sert à rien d’envoyer une grande échelle sur une crise cardiaque par ex.), mais aussi les plus rapides possibles.

Rien ne sert de courir ...

… sauf quand des vies sont en jeu. Enfin, plutôt que courir, on cherche surtout à parcourir le plus court chemin possible.

Historiquement, le territoire était découpé en “Listes De Défenses” (LDD), qui correspondent à des zones de proximité par rapport à des casernes. Une opération qui tombe dans la zone d’une caserne est affectée en priorité à cette caserne. Si la caserne en question n’est pas disponible, la LDD indique la prochaine caserne à laquelle affecter l’opération, et ce jusqu’à trouver une caserne de disponible. Ces LDD sont calculées d’avance, sans possibilité de tenir compte de l’évolution du réseau routier ou des moyens à disposition à l’instant T.

Mais revenons à Grand-Mère et Papy. Imaginons qu’un camion revienne d’une intervention en passant par leur rue, justement quand Papy appelle le 112. Ce camion pourrait arriver sur les lieux quelques minutes après l’appel, mais aujourd’hui, ce n’est pas possible sans l’intervention manuelle d’un opérateur.

Les calculs d’itinéraires à la rescousse

Pour être en mesure d’envoyer la réponse la plus rapide possible, on va se servir de ce qu’on appelle des “Temps de Transit Dynamiques” (TTD). Il s’agit de calculer le temps de parcours d’un ensemble de véhicules (parmi ceux les plus proches de l’opération), vers le lieu de l’opération.

Ces calculs doivent être performants, mais pouvoir s’adapter aux spécificités des véhicules d’urgence. On cherche alors un moteur de calcul d’itinéraire performant, mais aussi très flexible.

Quand on commence à se renseigner sur les moteurs de calculs d’itinéraires open source, performants mais flexibles, avec des fonctionnalités avancées et une communauté active, trois candidats principaux sortent du lot :

En se basant sur des retours en interne à Camptocamp et sur différents articles de blog (gis-ops.com, curiosio.medium.com ou encore jakobmiksch.eu), il est apparu que, pour avoir un maximum de flexibilité tout en gardant des performances acceptables (sur des petites distances), pgRouting était la solution à retenir.

Des algo en veux-tu ? En voilà !

pgRouting est une extension de la base de données PostgreSQL, accompagnée de sa cartouche spatiale PostGIS. C’est une véritable boîte à outils pour travailler avec un réseau routier ou autre.

Parmi les nombreux algorithmes proposés par pgRouting, ceux qui nous intéressent sont ceux qui permettent de calculer un itinéraire depuis un noeud de départ vers un noeud d’arrivée :

Dijkstra
C’est l’Algorithme (avec un grand A) de calcul du plus court chemin. Malheureusement, il n’est pas performant face à un graphe volumineux
A*
L’algorithme A* a été conçu pour optimiser le calcul d’itinéraire d’un point A vers un point B, en orientant la recherche le long de l’axe A-B. Sur un graphe homogène (ce qui n’est pas le cas du réseau routier, qui présente de grandes différences de vitesses entre chaque type de routes), le premier chemin trouvé sera aussi l’un des plus courts.
Turn Restriction Shortest Path (TRSP)
Presque aussi performant que A*, il permet de tenir compte des interdictions de virage sur le réseau routier. Mais pour qu’il soit intéressant, il faut connaître de façon précise ces interdictions de tourner, et il faut que les véhicules se soucient de ce genre de restrictions (je pose la botte “Véhicule Prioritaire”, plus de feu rouges, plus de limites de vitesse :D)

Nous retiendrons l’algorithme A*, car c’est le plus performant, et d’autres optimisations sur le graphe feront que celui-ci est suffisamment homogène.

En parlant d’optimisation

L’optimisation la plus importante consiste à réduire le nombre de tronçons que le moteur d’itinéraire doit parcourir pour trouver le chemin reliant le départ à l’arrivée. Pour cela, il faut être capable de définir de façon intelligente les tronçons les plus probables de servir à l’itinéraire :

tronçons majeurs à vitesse élevée
tronçons mineurs à proximité du départ et de l’arrivée

Mais attention, il faut retenir suffisamment de tronçons pour que le calcul d’itinéraire reste possible du départ vers l’arrivée, et qu’il reste parmi les plus courts.

La sélection de ces tronçons d'intérêt doit aussi se faire de façon optimisée, grâce à l’utilisation d’index spatiaux.

Parmi les optimisations, la contraction d’un graphe permet de nettoyer les tronçons que l’on sait d’avance inutiles (cul de sac), et de réduire le nombre de tronçons, quand ils partagent les mêmes informations. La contraction est particulièrement intéressante dans notre cas, où nous allons sélectionner un sous-graphe des tronçons majeurs (sous-graphe => nœuds inutiles de jonction vers des tronçons non retenus).

Le graphe d’origine

Après la contraction des impasses

Après la contraction linéaire sur le graphe ci-dessus

Les nœuds 2, 4, 10 et 12 ont été retirés car ils n’apportent pas d’informations supplémentaires aux relations du graphe. Par exemple, il est toujours possible de rejoindre le noeuds 5 depuis le noeud 3, en empruntant le nouveau tronçon -1 qui portent les informations des anciens tronçons 1 et 2.

Une autre optimisation passe par le fait de partager une partie des ressources pour de multiples calculs, en utilisant la fonction de signature many-to-one : un seul appel à la BD pour le calcul de n itinéraires, et un seul chargement du graphe en mémoire.

Finalement, il ne faut pas négliger les requêtes d’exploitation du calcul (projection des coordonnées de départ et d’arrivée sur les tronçons du réseau), qui doivent aussi se faire de façon optimisée (CTE, tables temporaires).

Encore plus flexible qu’Elasti-Girl

N’oublions pas notre besoin de départ : avoir un calcul plus réaliste et dynamique que les LDD. Pour cela, une des grandes forces de pgRouting est sa capacité à s'appuyer pleinement sur le moteur SQL de PostgreSQL. Il est ainsi possible de sélectionner aussi finement que nécessaire les tronçons d'intérêt, tant que le SQL le permet. On peut imaginer de fermer des tronçon pour travaux (prévisible sur une période), pour le marché du dimanche matin (prévisible récurrent), ou dans le cas d’une inondation (imprévisible). On peut aussi imaginer de faire évoluer la vitesse de certains tronçons (état de la route qui force à ralentir, ou au contraire, véhicules prioritaires qui dépassent les limitations de vitesses). Avec les données adéquates, il deviendrait même possible de tenir compte d’informations de trafic.