Article rédigé par Ignacio « Nacho » Correas, directeur de l’innovation technologique chez Skymantics -
Il y a deux compromis à trouver avec soin : la précision et les performances. Il est inutile pour un moteur de routage de générer rapidement des itinéraires sous-optimaux, mais il est tout aussi peu pratique de générer des itinéraires optimaux qui nécessitent un temps de calcul long. Le premier point critique à examiner dans le moteur de routage est l'algorithme de routage.
Algorithmes de routage
Skymantics a expérimenté des algorithmes de chemin le plus court, en particulier Dijkstra et A* (A-star), dans trois modes : unidirectionnel, bidirectionnel et avec optimisation des hiérarchies de contraction (CH). La mise en œuvre d'une version unidirectionnelle et basique de ces algorithmes est assez simple, et il existe de nombreux tutoriels sur Internet pour vous aider à comprendre comment procéder. En règle générale, la création d'algorithmes bidirectionnels (en d'autres termes, le chemin est calculé simultanément à partir de l'origine et de la destination) fournira l'itinéraire optimal 5 à 10 fois plus rapidement que l'unidirectionnel, même si le choix du nœud de jonction optimal (où le chemin de l'origine rencontre le chemin de la destination) présente ses propres problèmes. Cependant, choisir entre Dijkstra et A* et entre bidirectionnel ou avec CH n'est pas simple.
Quand utiliser A*
En théorie, A* devrait être un algorithme plus efficace, car il nécessite moins de calculs : il s'agit en fait d'un Dijkstra dirigé qui ne prend en compte que les nœuds du graphe qui aident à se déplacer dans la direction vers la destination. Cependant, cela nécessite de calculer la direction et les distances heuristiques, ce qui est une opération de calcul plus coûteuse qu'une itération de Dikjstra, et cela peut être contre-productif. En général, pour des maillages très denses de rues/routes de la même hiérarchie, A* peut être un meilleur choix. Pour tout le reste, Dijkstra sera probablement suffisant.
Quand utiliser CH
Pour les itinéraires longs et transcontinentaux, vous avez besoin d'une sorte d'optimisation telle que les hiérarchies de contraction. Cette optimisation donnera la priorité aux itinéraires de hiérarchie supérieure et ignorera les alternatives de hiérarchie inférieure, réduisant considérablement les calculs pour trouver l'itinéraire le plus court de manière très efficace. Voici un exemple d'un itinéraire de 265 km (165 miles) traversant la Belgique : il faut 35 secondes pour calculer avec l'algorithme bidirectionnel de Dijkstra, mais seulement 0.1 seconde avec l'optimisation des hiérarchies de contraction.
Quand utiliser Bi-direction Dijkstra
Pour les itinéraires urbains plus courts, les hiérarchies de contraction peuvent donner lieu à un itinéraire sous-optimal, car l'algorithme peut faire des détours s'il trouve un itinéraire de hiérarchie supérieure à proximité. Il est possible de réduire cet effet, voire de le supprimer complètement, en modifiant soigneusement les hiérarchies routières et en autorisant l'algorithme à effectuer quelques itérations supplémentaires. Mais si l'application de routage concerne uniquement une zone urbaine spécifique, il peut être plus simple d'utiliser simplement un Dijkstra bidirectionnel. Voici un exemple d'itinéraire dans le centre-ville de Providence, Rhode Island, qui devrait être une simple ligne droite, mais qui se fait avoir par les hiérarchies de contraction et fait un détour par la rue principale à proximité. Le temps de calcul pour CH est de 1 milliseconde contre 1.5 milliseconde pour Dijkstra bidirectionnel, ce qui démontre qu'il existe une marge de manœuvre pour des itérations supplémentaires afin d'éviter cet effet de détour.
Les algorithmes de routage peuvent garantir la précision et améliorer les performances dans une certaine mesure. En réalité, ils parcourent un maillage de routes définies dans un ensemble de données cartographiques, et les résultats dépendent fortement de la précision de ces ensembles de données et de la manière dont ils ont été prétraités.
Prétraitement des ensembles de données
Les jeux de données et le prétraitement sont le moyen le plus important d'améliorer la précision et les performances d'un algorithme de routage. Il est difficile de souligner suffisamment ce point. Je vais essayer de résumer les principaux aspects à prendre en compte dans les points suivants :
- Tous les ensembles de données n’ont pas le même niveau de précision. OpenStreetMap est un bon exemple ; elle couvre pratiquement le monde entier et est téléchargeable et utilisable gratuitement, mais elle manque d'informations importantes telles que de nombreuses limitations de vitesse, des limites de taille/poids ou des manœuvres interdites. Dans certains cas, elle peut même contenir de fausses informations concernant la direction des rues à sens unique ou les connexions, pour n'en citer que quelques-unes. D'autres cartes, telles que ICI, offrent un niveau de précision bien meilleur, mais ont un prix. Curieusement, les coordonnées des rues ne correspondent pas à 100 % dans différents ensembles de données et vous pouvez découvrir que les mêmes coordonnées sont considérées comme faisant partie de différentes rues en fonction de l'ensemble de données que vous utilisez.
- En fonction de l'application de votre moteur de routage, de nombreux segments de rue ou de route fournis dans un ensemble de données peuvent être fusionnés en une seule arête, réduisant parfois la taille du graphique jusqu'à 90 %. Par exemple, des raccourcis peuvent être créés pour sauter par-dessus des intersections de hiérarchie inférieure, accélérant ainsi le calcul de l'itinéraire sur de longues distances.
- Une partie essentielle du prétraitement consiste à décider comment classer la hiérarchie des liaisons routières : relient-elles des routes de hiérarchie inférieure à des routes de hiérarchie supérieure ? Relient-elles les routes de la même hiérarchie ? Il s'agit d'un aspect particulièrement important pour les carrefours d'autoroutes, car les routes reliant les autoroutes doivent avoir la hiérarchie la plus élevée (pour accélérer les hiérarchies de contraction), mais définir toutes les liaisons routières d'une autoroute sur la hiérarchie la plus élevée ralentira les calculs en raison du trop grand nombre d'intersections.
Les algorithmes de routage, les jeux de données et le prétraitement sont les aspects clés à prendre en compte pour créer un algorithme de routage précis et performant. Mais il existe d'autres aspects qui peuvent faire la différence entre un moteur de routage utile et un moteur de routage inutile.
Bonnes pratiques de programmation
Je considère comme acquis que de bonnes pratiques de programmation sont en place et qu'un langage de programmation approprié est choisi pour la tâche. Il y a trois points essentiels à prendre en compte lors du déploiement et de l'exploitation d'un moteur de routage :
- Les données graphiques doivent résider en mémoire pour des performances maximales. Certaines parties d'une base de données peuvent contenir des données géographiques, par exemple, pour aider à trouver les nœuds les plus proches de l'origine et de la destination, mais l'algorithme de routage doit fonctionner avec des données en mémoire, sinon il risque de ne pas être performant pour les cartes légèrement plus grandes qu'un centre-ville.
- Le moteur de routage doit précharger toutes les données requises et doit utiliser le threading pour les tâches secondaires qui prennent du temps, comme l'enregistrement de l'itinéraire généré sur le disque. Sinon, ces temps s'accumulent, réduisant les performances globales.
- Cela peut paraître évident, mais si le moteur de routage doit être proposé en tant que service distant, la vitesse de connexion sera cruciale. Il ne sert à rien d'accélérer le calcul du routage si le goulot d'étranglement se situe dans le canal de communication. La latence et le débit sont essentiels pour un service API performant.
Et c'est tout. Construire un moteur de routage peut être une tâche passionnante, pleine de défis et de plaisir. Même si votre objectif n'est pas d'en construire un, mais que vous devez utiliser le routage de manière intensive, il est bon d'en comprendre les aspects clés. J'espère que vous avez eu autant de plaisir à lire cette série d'articles que j'en ai eu à les écrire. Santé !
