Quels algorithmes calculent les directions d'un point A à un point B sur une carte?
https://stackoverflow.com/questions/430142
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment les fournisseurs de cartes (tels que Google ou Yahoo! Maps) suggèrent-ils des indications?
Je veux dire, ils ont probablement des données du monde réel sous une forme quelconque, incluant certainement les distances mais aussi des choses comme la vitesse de conduite, la présence de trottoirs, les horaires de train, etc. Mais supposons que les données soient dans un format plus simple, disons très grand graphe orienté avec des poids de bords reflétant des distances. Je veux être capable de calculer rapidement les directions d'un point à un autre. Parfois, ces points seront proches les uns des autres (dans une même ville), parfois ils seront éloignés l'un de l'autre (cross-country).
Des algorithmes de graphes comme celui de Dijkstra ne fonctionneront pas car le graphe est énorme. Heureusement, des algorithmes heuristiques comme A * fonctionneront probablement. Cependant, nos données sont très structurées et peut-être une approche à plusieurs niveaux pourrait-elle fonctionner? (Par exemple, stockez les directions précalculées entre certains "points clés" distants, ainsi que certaines directions locales. Ensuite, les directions relatives à deux points éloignés impliquent des directions locales vers un point clé, des directions globales vers un autre point clé, puis directions locales à nouveau.)
Quels algorithmes sont réellement utilisés dans la pratique?
PS. Cette question a été motivée par la recherche de bizarreries dans les directions cartographiques en ligne. Contrairement à l’inégalité triangulaire, Google Maps pense parfois que et est plus loin que l’utilisation d’un point intermédiaire comme dans XYZ . Mais peut-être que leurs directions de marche s’optimiseront également pour un autre paramètre?
PPS. Voici une autre violation de l'inégalité triangulaire qui suggère (selon moi) qu'ils utilisent une sorte d'approche à plusieurs niveaux: XZ contre XYZ . Le premier semble utiliser le boulevard de Sébastopol, bien qu’il soit légèrement éloigné.
Modifier : aucun de ces exemples ne semble plus fonctionner, mais les deux l'étaient au moment de la publication d'origine.
La solution
Parlant en tant que personne ayant travaillé pendant 18 mois dans une société de cartographie, ce qui incluait notamment un travail sur l'algorithme de routage ... oui, Dijkstra fonctionne, avec quelques modifications:
- Au lieu de faire Dijkstra une fois de la source à la destination, vous commencez à chaque extrémité, et élargir les deux côtés jusqu'à ce qu'ils se rencontrent au milieu. Cela élimine environ la moitié du travail (2 * pi * (r / 2) ^ 2 vs pi * r ^ 2).
- Pour éviter d'explorer les ruelles de chaque ville entre votre source et votre destination, vous pouvez avoir plusieurs couches de données cartographiques: une couche "autoroutes" contenant uniquement des autoroutes, une couche "secondaire" contenant uniquement des rues secondaires et etc. Ensuite, vous explorez uniquement des sections plus petites des couches plus détaillées, en développant si nécessaire. Évidemment, cette description laisse beaucoup de détails, mais vous avez l’idée.
Avec des modifications allant dans ce sens, vous pouvez même effectuer l'acheminement entre pays dans un délai très raisonnable.
Autres conseils
Cette question a été un domaine de recherche actif au cours des dernières années. L'idée principale est d'effectuer un prétraitement sur le graphique une fois pour accélérer toutes les requêtes suivantes . Avec cette information supplémentaire, les itinéraires peuvent être calculés très rapidement. Néanmoins, l'algorithme de Dijkstra constitue la base de toutes les optimisations.
Arachnid a décrit l'utilisation de la recherche bidirectionnelle et de l'élagage des bords en fonction des informations hiérarchiques. Ces techniques d'accélération fonctionnent assez bien, mais les algorithmes les plus récents surpassent ces techniques par tous les moyens. Avec les algorithmes actuels, un plus court chemin peut être calculé en moins de temps qu'un une milliseconde sur un réseau routier continental. Une implémentation rapide de l’algorithme non modifié de Dijkstra nécessite environ 10 secondes .
L'article Algorithmes d'ingénierie de planification d'itinéraires rapides donne un aperçu de l'état d'avancement du recherche dans ce domaine. Voir les références de cet article pour plus d'informations.
Les algorithmes les plus rapides connus n’utilisent pas d’informations sur l’état hiérarchique de la route dans les données, c’est-à-dire s’il s’agit d’une route ou d’une route locale. Au lieu de cela, ils calculent dans une étape de prétraitement une propre hiérarchie optimisée pour accélérer la planification des itinéraires. Ce pré-calcul peut ensuite être utilisé pour élaguer la recherche: Les routes lentes éloignées du début et de la destination ne doivent pas être prises en compte lors de l’algorithme de Dijkstra. Les avantages sont très bons performances et une exactitude du résultat.
Les premiers algorithmes optimisés de planification d'itinéraire traitaient uniquement des réseaux routiers statiques, ce qui signifie qu'un bord du graphique a une valeur de coût fixe. Ce n'est pas vrai en pratique, car nous voulons prendre en compte des informations dynamiques telles que les embouteillages ou les restrictions liées aux véhicules. Les algorithmes les plus récents peuvent également traiter de tels problèmes, mais il reste encore des problèmes à résoudre et les recherches se poursuivent.
Si vous avez besoin des distances de chemin les plus courtes pour calculer une solution pour le TSP , vous êtes probablement intéressé par les matrices contenant toutes les distances entre vos sources et vos destinations. Pour cela, vous pouvez envisager de calculer plusieurs chemins parmi les plus courts à l'aide de hiérarchies routières . Notez que cela a été amélioré par de nouvelles approches au cours des deux dernières années.
En ce qui concerne les violations de l’inégalité des triangles, espérons que le facteur supplémentaire pour lequel elles sont optimisées relève du bon sens. Vous ne voulez pas nécessairement l'itinéraire le plus court ou le plus rapide, car cela peut entraîner un chaos et destruction . Si vous souhaitez que vos instructions préfèrent les grandes routes qui acceptent les poids lourds et que l’envoi de chaque conducteur suivant soit renvoyé, supprimez rapidement l’inégalité du triangle [1].
Si Y est une rue résidentielle étroite entre X et Z, vous ne voudrez probablement utiliser le raccourci via Y que si l'utilisateur demande explicitement X-Y-Z. S'ils demandent X-Z, ils devraient rester sur les routes principales même si c'est un peu plus loin et prend un peu plus longtemps. Cela ressemble au paradoxe de Braess - si tout le monde essaie de prendre l'itinéraire le plus court et le plus rapide, la congestion qui en résulte signifie que ce n’est plus la voie la plus rapide pour qui que ce soit. De là, nous passons de la théorie des graphes à la théorie des jeux.
[1] En fait, tout espoir que les distances produites soient une fonction de distance au sens mathématique s'éteint lorsque vous autorisez les routes à sens unique et que vous perdez l'exigence de symétrie. Perdre aussi l’inégalité triangulaire, c’est tout simplement salir la plaie.
Voici les algorithmes de routage les plus rapides au monde comparés et éprouvés en matière de correction:
http://algo2.iti.uka.de/schultes/hwy/ schultes_diss.pdf
Voici un exposé technique de Google sur le sujet:
http://www.youtube.com/watch?v=-0ErpE8tQbw
Voici une implémentation de l'algorithme autoroute-hiérarchies telle que discutée par schultes (pour le moment uniquement à berlin, j'écris l'interface et une version mobile est en cours de développement):
Je n'ai jamais travaillé sur Google, Microsoft ou Yahoo Maps, je ne peux donc pas vous dire comment ils fonctionnent.
Cependant, j’ai conçu un système d’optimisation de la chaîne logistique personnalisé pour une entreprise du secteur de l’énergie, qui comprenait une application de planification et d’acheminement de leur parc de camions. Toutefois, nos critères d’acheminement étaient bien plus spécifiques aux entreprises qu’à la construction, au ralentissement de la circulation ou à la fermeture de voies.
Nous avons utilisé une technique appelée ACO (optimisation de la colonie de fourmis) pour planifier et acheminer les camions. Cette technique est une technique d'intelligence artificielle qui a été appliquée au problème du voyageur de commerce pour résoudre les problèmes de routage. Le truc avec ACO est de construire un calcul d’erreur basé sur des faits connus du routage afin que le modèle de résolution de graphe sache quand quitter (quand l’erreur est-elle assez petite).
Vous pouvez utiliser Google ACO ou TSP pour en savoir plus sur cette technique. Je n’ai utilisé aucun des outils d’intelligence artificielle open-source pour cela, donc je ne peux pas en suggérer un (même si j’ai entendu dire que SWARM était assez complet).
Des algorithmes de graphes tels que celui de Dijkstra ne fonctionneront pas car le graphe est énorme.
Cet argument ne tient pas nécessairement car Dijkstra ne regarde généralement pas le graphique complet, mais plutôt un très petit sous-ensemble (plus le graphique est interconnecté, plus ce sous-ensemble est petit).
Dijkstra peut en fait assez bien fonctionner pour les graphes bien comportés. Par contre, avec une paramétrisation soignée, A * fonctionnera toujours aussi bien, voire mieux. Avez-vous déjà essayé comment cela fonctionnerait sur vos données?
Cela dit, je serais également très intéressé par les expériences des autres. Bien entendu, des exemples notables tels que la recherche dans Google Map sont particulièrement intéressants. Je pourrais imaginer quelque chose comme une heuristique dirigée vers le plus proche voisin.
L’état actuel de la technique en matière de temps d’interrogation pour les réseaux routiers statiques est l’algorithme d’étiquetage Hub proposé par Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642- 20662-7_20 . Une enquête approfondie et parfaitement écrite sur le terrain a récemment été publiée sous la forme d’un rapport technique Microsoft http: / /research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .
La version courte est ...
L'algorithme d'étiquetage du concentrateur fournit les requêtes les plus rapides pour les réseaux routiers statiques, mais nécessite une grande quantité de RAM pour s'exécuter (18 Go).
Le routage des noeuds de transit est légèrement plus lent, bien qu'il ne nécessite que 2 Go de mémoire environ et que le temps de prétraitement soit plus court.
Les hiérarchies de contraction offrent un bon compromis entre des temps de prétraitement rapides, un faible espace requis (0,4 Go) et des temps de requête rapides.
Aucun algorithme n'est complètement dominé ...
Cette conférence technique de Peter Sanders sur Google Tech pourrait présenter un intérêt
https://www.youtube.com/watch?v=-0ErpE8tQbw
Aussi cette conférence par Andrew Goldberg
https://www.youtube.com/watch?v=WPrkc78XLhw
Une implémentation open source des hiérarchies de contraction est disponible sur le site Web du groupe de recherche Peter Sanders au KIT. http://algo2.iti.kit.edu/english/routeplanning.php
Également un article de blog facilement accessible écrit par Microsoft sur leur utilisation de l'algorithme CRP ... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/
Je suis un peu surpris de ne pas voir l'algorithme de Floyd Warshall . mentionné ici. Ce travail d'algorithme est très semblable à celui de Dijkstra. Il possède également une fonctionnalité très intéressante: il vous permet de calculer aussi longtemps que vous souhaitez continuer à autoriser davantage de sommets intermédiaires. Il trouvera donc naturellement les itinéraires qui empruntent assez rapidement les autoroutes ou les autoroutes.
J'ai fait cela assez souvent, en fait, en essayant plusieurs méthodes différentes. En fonction de la taille (géographique) de la carte, vous pouvez envisager d’utiliser la fonction haversine comme une heuristique.
La meilleure solution que j'ai faite consistait à utiliser A * avec une distance en ligne droite comme fonction heuristique. Mais vous avez besoin d'une sorte de coordonnées pour chaque point (intersection ou sommet) de la carte. Vous pouvez également essayer différentes pondérations pour la fonction heuristique, à savoir
f(n) = k*h(n) + g(n)
où k est une constante supérieure à 0.
Probablement similaire à la réponse sur les itinéraires pré-calculés entre les principaux sites et les cartes superposées, mais si je comprends bien, dans les jeux, pour accélérer A *, vous avez une carte très grossière pour la navigation macro et une carte grainée pour la navigation à la limite des directions macro. Donc, vous avez deux petits chemins à calculer, et votre espace de recherche est donc beaucoup plus petit que de simplement faire un seul chemin vers la destination. Et si vous faites beaucoup de choses là-dessus, beaucoup de ces données sont pré-calculées de sorte qu'une partie au moins de la recherche consiste en une recherche de données pré-calculées, plutôt qu'en un chemin.
C’est une pure spéculation de ma part, mais je suppose qu’ils peuvent utiliser une structure de données de carte d’influence superposée à la carte dirigée afin de restreindre le domaine de recherche. Cela permettrait à l’algorithme de recherche de diriger le chemin vers les routes principales lorsque le trajet souhaité est long.
Étant donné qu'il s'agit d'une application Google, il est également raisonnable de supposer qu'une grande partie de la magie est réalisée via une mise en cache étendue. :) Je ne serais pas surpris si la mise en cache des 5% de demandes les plus courantes sur l'itinéraire Google Map permettait de traiter un grand nombre de demandes (20%? 50%?) Par simple recherche.
J'ai eu quelques réflexions supplémentaires à ce sujet:
1) N'oubliez pas que les cartes représentent une organisation physique. Stocker la latitude / longitude de chaque intersection. Vous n'avez pas besoin de vérifier beaucoup au-delà des points situés dans la direction de votre cible. Si vous êtes bloqué, vous devez aller au-delà. Si vous stockez une superposition de connexions supérieures, vous pouvez la limiter encore plus - vous ne rencontrerez normalement jamais l'une de ces connexions d'une manière qui s'éloigne de votre destination finale.
2) Divisez le monde en un tas de zones définies par une connectivité limitée, définissez tous les points de connectivité entre les zones. Recherchez les zones dans lesquelles se trouvent votre source et votre cible, pour l'itinéraire des zones de début et de fin, de votre emplacement à chaque point de connexion, pour les zones situées simplement entre les points de connexion. (Je soupçonne que beaucoup de ces derniers sont déjà pré-calculés.)
Notez que les zones peuvent être plus petites qu’une zone métropolitaine. Toute ville dont les caractéristiques de terrain la diviseraient (par exemple une rivière) constituerait plusieurs zones.
J’étais très curieux des heuristiques utilisées, il ya quelque temps, nous avions des itinéraires depuis le même lieu de départ, près de Santa Rosa, vers deux campings différents dans le parc national de Yosemite. Ces différentes destinations ont produit des itinéraires assez différents (via l'I-580 ou le CA-12) malgré le fait que les deux itinéraires ont convergé sur les 100 derniers miles (le long du CA-120) avant de diverger à nouveau de quelques kilomètres à la fin. C'était assez répétable. Les deux itinéraires étaient distants de 100 km environ, mais les distances / temps étaient assez proches l'un de l'autre, comme on pouvait s'y attendre.
Hélas, je ne peux pas reproduire cela - les algorithmes doivent avoir changé. Mais il m'a curieux de connaître l'algorithme. Tout ce que je peux supposer, c’est qu’il existait une taille directionnelle extrêmement sensible à la petite différence angulaire entre les destinations vue de loin ou à différents segments précalculés sélectionnés selon le choix de la destination finale.
En parlant de GraphHopper , un planificateur d'itinéraire rapide Open Source basé sur OpenStreetMap, j'ai lu un peu de littérature et mis en œuvre des méthodes. La solution la plus simple est un Dijkstra et une amélioration simple est un Dijkstra bidirectionnel qui explore en gros seulement la moitié des nœuds. Avec bidirctional Dijkstra, un itinéraire à travers toute l’Allemagne prend déjà 1 seconde (en mode voiture), en C il ne serait probablement que de 0,5 seconde environ;)
J'ai créé un gif animé d'une recherche de chemin réel avec Dijkstra bidirectionnel ici . Il existe également d'autres idées pour accélérer Dijkstra comme faire A *, qui est un "Dijkstra axé sur les objectifs". J'ai également créé un gif-animation .
Mais comment faire (beaucoup) plus rapidement?
Le problème est que pour une recherche de chemin, tous les nœuds situés entre les sites doivent être explorés, ce qui est très coûteux, car il en existe déjà plusieurs millions en Allemagne. Mais un autre problème de Dijkstra, etc., est que de telles recherches utilisent beaucoup de RAM.
Il existe des solutions heuristiques mais aussi des solutions exactes qui organisent le graphe (réseau routier) en couches hiérarchiques, les deux ont des avantages et des inconvénients et résolvent principalement le problème de la vitesse et de la RAM. J'en ai énuméré quelques-unes dans cette réponse .
Pour GraphHopper, j’ai décidé d’utiliser Hiérarchies de contraction , car il est relativement facile à mettre en œuvre. et ne prend pas des siècles pour la préparation du graphique. Il en résulte toujours des temps de réponse très courts, comme vous pouvez le tester sur notre instance en ligne GraphHopper Maps . Par exemple. de l'Afrique du Sud à la Chine de l'Est , qui en résulte sur une distance de 23 000 km et près de 14 jours de conduite d'une voiture et n'a pris que ~ 0,1 s sur le serveur.
Je travaille sur le routage depuis quelques années, avec un regain d'activité récent impulsé par les besoins de mes clients, et j'ai constaté qu'A * est assez rapide; il n'est vraiment pas nécessaire de rechercher des optimisations ou des algorithmes plus complexes. Le routage sur un graphique énorme n’est pas un problème.
Mais la vitesse dépend de la présence de l’ensemble du réseau de routage, c’est-à-dire du graphe orienté des arcs et des noeuds représentant respectivement les segments et les jonctions de la route, en mémoire. La surcharge de temps principale est le temps pris pour créer ce réseau. Quelques chiffres approximatifs basés sur un ordinateur portable ordinaire fonctionnant sous Windows et routant sur l’ensemble de l’Espagne: temps nécessaire pour créer le réseau: 10 à 15 secondes; temps pris pour calculer un itinéraire: trop court pour être mesuré.
L’autre chose importante est de pouvoir réutiliser le réseau pour autant de calculs de routage que vous le souhaitez. Si votre algorithme a marqué les nœuds de manière à enregistrer le meilleur itinéraire (coût total pour le nœud actuel et meilleur arc de cercle) - comme cela doit être le cas en A * - vous devez réinitialiser ou effacer ces anciennes informations. Plutôt que de passer par des centaines de milliers de nœuds, il est plus facile d’utiliser un système à numéro de génération. Marquez chaque noeud avec le numéro de génération de ses données; incrémenter le numéro de génération lorsque vous calculez un nouvel itinéraire; tout nœud avec un numéro de génération plus ancien est périmé et ses informations peuvent être ignorées.
Je vois ce qui se passe avec les cartes du PO:
Regardez l'itinéraire avec le point intermédiaire spécifié: l'itinéraire recule légèrement car cette route n'est pas rectiligne.
Si leur algorithme ne revient pas en arrière, il ne verra pas la route la plus courte.
Un algorithme de chemin le plus court pour toutes les paires calculera le chemin le plus court entre tous les sommets d'un graphique. Cela permettra aux chemins d'être pré-calculés au lieu de demander qu'un chemin soit calculé chaque fois que quelqu'un veut trouver le chemin le plus court entre une source et une destination. L'algorithme de Floyd-Warshall est un algorithme de chemin le plus court pour toutes les paires.
Les cartes ne prennent jamais en compte la totalité de la carte. Ma conjecture est:- 1. En fonction de votre emplacement, ils chargent une place et les points de repère sur cette place. 2. Lorsque vous recherchez la destination, c’est lorsqu’ils chargent l’autre partie de la carte et créent un graphique à deux endroits, puis appliquent les algorithmes de chemin le plus court.
En outre, il existe une technique importante de programmation dynamique que je soupçonne d’être utilisée dans le calcul des chemins les plus courts. Vous pouvez également vous référer à cela.
