Avec le temps, Oslandia a pu appliquer son expertise SIG de nombreuses fois dans le domaine des transports, et plus particulièrement, celui des calculs d’itinéraires. Si le développement logiciel et les bases de données sont nos portes d’entrée naturelles dans la thématique, nous ne perdons pas de vue les questions algorithmiques !
Ainsi, nous nous intéressons depuis peu à l’algorithme-roi dans la discipline, permettant d’atteindre des performances en temps de calcul parmi les plus intéressantes : les Contractions Hiérarchiques.
Les Contractions Hiérarchiques, qu’est-ce que c’est ?
L’algorithme des Contractions Hiérarchiques repose sur une phase de pré-traitement permettant d’accélérer drastiquement les requêtes de plus court chemin.
Les caractéristiques principales de cet algorithme sont les suivantes :
- Des arcs virtuels, dits « raccourcis », sont définis pour compacter l’information contenue dans le graphe. Les noeuds court-circuités par ces raccourcis sont dits « contractés ».
- Les noeuds sont classés par ordre d’importance pendant le pré-traitement, de telle façon que les noeuds les plus hauts dans la hiérarchie seront les plus susceptibles d’être empruntés par les meilleurs chemins (typiquement, des grands carrefours urbains ou des sections autoroutières fréquentées), et les moins susceptibles d’être contractés.
Mécanisme de création de raccourcis : on contracte un noeud intermédiaire « u » uniquement s’il est plus bas que la source « s » et la destination « d » dans la hiérarchie « l », et s’il n’existe pas de meilleur chemin alternatif « P » (cas (c) et (g)).
- La recherche de plus court chemin exploite la hiérarchie des noeuds et les raccourcis définis pendant le pré-traitement, et se découpe en deux composantes : une recherche en avant à partir de la source, et une recherche à rebours à partir de la destination. Ces deux composantes convergent au plus haut niveau dans la hiérarchie des noeuds.
Type de chemin mis en valeur par la procédure des contractions hiérarchiques, entre une source « s » et une destination « d »
Est-ce utilisable dans une base de données PostgreSQL ?
Il existe des implémentations des Contractions Hiérarchiques dans plusieurs projets Open Source. Citons par exemple RoutingKit, un projet initié par l’équipe de recherche à l’origine des Contractions Hiérarchiques, ou encore le projet OSRM.
Côté PostgreSQL, le moyen le plus rapide pour bénéficier des algorithmes de routing est l’extension pgRouting. Malheureusement, cette extension n’inclut aujourd’hui pas les Contractions Hiérarchiques.
PgRouting propose toutefois des algorithmes de contraction plus légers, qui permettent de gérer les impasses ainsi que les corridors (enchaînement de tronçons consécutifs sans carrefour).
Dans cet exemple tiré de la documentation de pgRouting, le noeud 1 sera par exemple contracté en temps qu’impasse, et le noeud 8 en temps que corridor.
Pour l’illustration, un test grandeur nature sur les données de la BDCarto pour la France métropolitaine peut être effectué. Le graphe de départ contient environ 1.12M noeuds et 1.65M arcs. Après application de ces deux types de contraction, le graphe résultat comporte environ 0.86M noeuds et 1.48M arcs, soit des réductions de respectivement 22.9 % et 10.2 %.
Exemples de résultat des contractions sur la BD Carto, en rouge le réseau avant traitement et en noir après
Les gains de temps de calcul à attendre sont donc limités avec un algorithme de type Dijkstra, au maximum de l’ordre de 30 %. Les contractions hiérarchiques, elles, permettent des améliorations bien plus importantes, et constituent donc une contribution de choix dans pgRouting.
Oslandia, Open source et Contractions Hiérarchiques
Comme évoqué dans un précédent article, Oslandia consacre des jours de développement aux projets Open Source de l’écosystème SIG. pgRouting entre pleinement dans ce cadre, et l’intégration des Contractions Hiérarchiques dans cette extension PostgreSQL nous apparaît comme un challenge particulièrement attrayant !
Si vous êtes intéressés par le sujet, et que vous souhaitez nous accompagner dans cette aventure, n’hésitez pas à nous contacter à l’adresse info@oslandia.com !
