Dans les jours brumeux d'avant les années 2000, pour naviguer entre deux endroits, il fallait généralement que quelqu'un sorte une carte papier et détermine minutieusement l'itinéraire le plus optimal entre ceux-ci, en fonction du mode de transport choisi. Pour les générations d'aujourd'hui, de tels dispositifs ne sont pas nécessaires, la technologie ayant même effacé le besoin de dépenser beaucoup d'argent pour un appareil de navigation GPS et des mises à jour annuelles des cartes.
De nos jours, vous sortez un appareil informatique, ouvrez Google Maps ou équivalent, lui demandez comment vous devez voyager quelque part, et la plupart du temps, l'itinéraire fourni sera le bon, y compris les petits détails tels que le quai du train et les heures de départ. Mais comment fonctionne toute cette technologie de planification d’itinéraire apparemment magique ? On suppose souvent que l'algorithme de Dijkstra, ou l'algorithme de parcours de graphes A*, est utilisé, mais la réalité est que, bien que ces algorithmes de pure théorie des graphes soient résolument influents, ils ne peuvent pas être appliqués textuellement à la réalité du parcours de graphes entre des destinations dans le monde physique.
Une histoire de voyageurs
Le domaine de la théorie des graphes existe depuis 1736, lorsque Leonhard Euler a publié un article sur le thème des Sept Ponts de Königsberg (en Prusse, aujourd'hui Kaliningrad en Russie). Dans ce problème mathématique, il faut concevoir une promenade à travers la ville dans laquelle chacun des sept ponts traversant la rivière Pregel de la ville et reliant les deux îles de ladite rivière n'est traversé qu'une seule fois. Euler a observé que les seules informations pertinentes ici sont les masses terrestres (les nœuds) et les connexions entre elles (les ponts ou bords), ce qui réduit le problème à un simple graphique.
Sur ce graphique, un nœud de départ est sélectionné, avec un autre nœud comme nœud de fin. Comme chaque territoire est relié à un nombre impair de ponts (3 ou 5), cela signifie que ce problème n’a pas de solution. Le principal défi réside ici dans la conception d’une preuve mathématiquement acceptable de cette impossibilité, ce qui constitue le fondement de ce que nous appelons aujourd’hui la théorie des graphes.
À partir de là, la théorie des graphes s’est étendue et généralisée aux relations entre objets, trouvant une utilisation dans des domaines allant de l’informatique et de la chimie à la biologie et à la linguistique. Combiné avec des algorithmes capables de gérer de tels graphiques, c'est un excellent moyen non seulement de clarifier la structure de base d'un réseau, mais également de modéliser des structures et des systèmes. Naturellement, la recherche d’un itinéraire entre les nœuds reste une partie cruciale du domaine, avec un large éventail d’algorithmes de recherche de chemin développés au fil des siècles.
Le problème le plus courant de la théorie des graphes est peut-être celui du problème du voyageur de commerce (TSP), qui ressemble un peu au problème original des sept ponts d'Euler, mais demande à la place à un voyageur (un vendeur) d'être guidé entre un ensemble de villes de la manière la plus efficace possible. manière possible. L'astuce ici est qu'en essayant aveuglément chaque itinéraire, le nombre d'itinéraires possibles augmente rapidement avec chaque ville ajoutée. En modélisant les villes comme des nœuds, on peut alors concevoir un algorithme qui crée les bords entre les nœuds, en tenant compte du poids de chaque nœud, lié à sa position sur la carte.
Bien que la planification d'itinéraire simple ne soit pas aussi intimidante que TSP, il existe certaines similitudes, dans le sens où elle implique un graphe pondéré et non orienté, obligeant l'algorithme à prendre en compte le coût de chaque arête ainsi que le coût total, créant ainsi un arbre couvrant minimum. . L'un des premiers algorithmes à cet effet est l'algorithme de Jarník, du mathématicien tchèque Vojtěch Jarník en 1930. Plus tard, il a été redécouvert par Robert C. Prim en 1957 et en 1956 par Edsger W. Dijkstra (l'algorithme de Dijkstra).
Le poids attribué à chaque nœud est la distance euclidienne, permettant à l'algorithme de calculer la distance de tout nœud nouvellement découvert à son nœud actuel. Dans sa forme la plus simple d'algorithme de recherche de chemin, il essaie une ou plusieurs étapes dans approximativement la direction de la destination et sélectionne parmi celles-ci la branche la plus courte, répétant cette procédure jusqu'à ce que la destination soit atteinte et que quelque chose proche du chemin le plus court ait été trouvé.
L’amélioration la plus connue de cet algorithme de base est probablement l’algorithme A* (recherche dirigée par objectif géométrique), développé en 1968 au Stanford Research Institute. Plutôt qu'un simple algorithme nœud à nœud, A* considère l'intégralité des nœuds et peut ignorer les nœuds proches afin d'obtenir un chemin globalement plus court entre la source et la destination. L'un des inconvénients de A* est qu'il doit conserver tous les nœuds en mémoire, ce qui le rend beaucoup plus gourmand en mémoire que les alternatives. Malgré cela, A* a été le choix habituel pour trouver un chemin dans le monde réel.
GPS pour tous
Avant que les États-Unis n'autorisent une plus grande précision avec les satellites GPS en désactivant la disponibilité sélective (SA), la meilleure précision que vous pouviez espérer par défaut était d'environ 50 à 100 mètres. Ce n'était clairement pas suffisant pour la navigation en direct qui, avec les prix élevés des appareils de navigation par satellite dans les années 1990, laissait la planification d'itinéraire principalement dépendante de cartes papier et de notes griffonnées ainsi que de mises à jour occasionnelles de la part de locaux serviables. La planification d'itinéraires à l'aide de moyens automatisés était déjà utilisée à cette époque, mais la plus grande utilisation était celle des planificateurs d'itinéraires des chemins de fer, des entreprises de logistique, etc.
Avec le positionnement GPS très précis devenu disponible en 2000 sans avoir besoin d'algorithmes de correction SA, et plus tard, d'autres systèmes mondiaux de navigation par satellite (GNSS) étant devenus accessibles au public parallèlement à la baisse rapide des prix des appareils compatibles GNSS, il est soudainement devenu possible de combiner des cartes numériques. avec une navigation par satellite précise, bien au-delà de la portée des premiers appareils de navigation par satellite des années 1990. Cela conduirait éventuellement à l'essor des smartphones, avec leur connectivité Internet sans fil, leur prise en charge GNSS intégrée et des applications comme Google Maps qui mettraient littéralement un appareil de navigation par satellite dans votre poche.
Bien qu'il soit utile d'obtenir des mises à jour en direct à partir d'un serveur distant sur les changements survenus sur l'itinéraire, comme les travaux routiers, les accidents et les obstacles, vous pouvez généralement utiliser les cartes numériques hors ligne pour planifier un itinéraire couvrant une variété de méthodes de transport et avec de nombreuses options pour personnaliser l'itinéraire. itinéraire généré.
Planification d'itinéraire aujourd'hui
L'idée de sortir un appareil informatique portable et de demander à un logiciel de planification d'itinéraire de planifier rapidement un itinéraire aurait semblé futuriste dans les années 1990, mais de nos jours, nous y réfléchissons à peine, sans parler de la façon dont tout cela fonctionne. À ce stade, il devrait être évident qu'appliquer simplement un algorithme de traversée de graphiques de base comme celui de Dijkstra serait trop simpliste, alors qu'utilisent des services comme Google Maps et d'autres ?
Bien que la réponse générale soit « l'algorithme de Dijkstra » ou « A*, bien sûr », la vérité est que le premier ne joue pas un rôle réel dans la recherche d'itinéraire moderne et A* s'est vu largement remplacé par des versions qui l'optimisent encore davantage grâce, par exemple, à l'utilisation du prétraitement. Nous pouvons considérer par exemple l'aperçu 2009 (PDF) fourni par Daniel Delling et ses collègues intitulé Algorithmes de planification d’itinéraires d’ingénierie.
Une partie où le monde clair et net des nœuds et des bords se heurte à certains problèmes est celle où vous devez prendre en compte les nombreux détails lorsque, par exemple, tracez un parcours via un réseau routier. Après tout, dans le monde réel, toutes les routes ne sont pas identiques et nécessitent des heuristiques pour savoir quand inclure certains poids ou non. Ces heuristiques incluent des hiérarchies de contraction (CH) ainsi que des hiérarchies d'autoroutes (HH) et bien d'autres, ce qui accélère la recherche d'un itinéraire qui n'est pas nécessairement le plus court, mais aussi le plus rapide. En prétraitant le graphique, les sommets (intersections) et les arêtes sans importance peuvent être ignorés, ce qui entraîne une accélération majeure.
Il n'est peut-être pas surprenant que de tels algorithmes de planification d'itinéraire puissent être facilement intégrés dans votre propre logiciel, en utilisant des projets open source comme OSRM et RoutingKit, qui utilisent tous deux les données cartographiques d'OpenStreetMap (OSM). Avec les ordinateurs de poche portables d'aujourd'hui et ces algorithmes et heuristiques de planification d'itinéraire optimisés, il suffit de ces composants logiciels et d'une bonne réception GNSS pour créer votre propre GPS.
D'où d'ici
Bien qu’il semblerait que nous ayons à ce stade résolu à peu près tout le problème de la planification d’itinéraire, l’article de Delling et al. note un certain nombre de défis qui subsistent. Surtout, aller au-delà du routage statique point à point et prendre en compte des facteurs dépendants du temps reste un défi, car bon nombre des raccourcis et des prétraitements qui rendaient le routage statique « bon marché » ne fonctionnent pas ici. Au-delà de cela, la caractérisation des réseaux « bien élevés » est une considération. Bien que cet article ait été rédigé il y a près de quinze ans, il devrait être clair pour quiconque utilise régulièrement un logiciel de planification d'itinéraires qu'il n'est pas encore tout à fait parfait.
L'intégration d'informations plus détaillées relatives à des modes de déplacement spécifiques et la prévention des situations délicates où par exemple un camion se retrouve coincé dans un tunnel ou entre des haies sont probablement au premier plan des préoccupations de la plupart des gens. Maintenant que tout le monde semble penser qu'il suffit de sortir son smartphone, de planifier un itinéraire et de suivre sans réfléchir les instructions fournies, l'impact d'une heuristique glissant sur quelques sommets défectueux peut être plutôt majeur.
Bien qu'il soit libérateur de ne pas avoir à se débattre avec une carte papier dans la voiture lors d'un voyage vers sa destination de vacances, l'hypothèse la plus sûre est que, aussi incroyable que soit devenue la navigation par satellite, les algorithmes et les ensembles de données ne sont pas parfaits, vous devez toujours compter sur votre bon sens et vos yeux Mk-1 avant tout.
Crédit vignette : [betaveros] avec l'illustration a* la plus fantaisiste que l'on puisse trouver sur Internet.
