Quels algorithmes calculent les directions du point A au point B sur une carte?
Comment cartographier les fournisseurs (tels que Google ou Yahoo! Cartes) suggérer des directions?
Je veux dire, ils ont probablement des données réelles sous une forme ou une autre, y compris certainement les distances, mais aussi peut-être des choses comme la vitesse de conduite, la présence de trottoirs, les horaires des trains, etc. Mais supposons que les données étaient dans un format plus simple, disons un très grand graphique dirigé avec des poids de bord reflétant les distances. Je veux être capable de calculer rapidement des directions d'un point arbitraire à un autre. Parfois, ces les points seront rapprochés (dans une ville) alors que parfois ils seront éloignés (cross-country).
Les algorithmes de graphique comme l'algorithme de Dijkstra ne fonctionneront pas car le graphique est énorme. Heureusement, les algorithmes heuristiques comme un* fonctionneront probablement. Cependant, nos données sont très structurées, et peut-être une sorte d'approche à plusieurs niveaux pourrait fonctionner? (Par exemple, stockez les directions précalculées entre certains points "clés" éloignés, ainsi que certaines directions locales. Puis directions pour deux les points lointains impliqueront des directions locales vers des points clés, des directions globales vers un autre point clé, puis des 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 de cartographie en ligne. Contrairement à l'inégalité du triangle, Google Maps pense parfois que X-Z prend plus de temps et est plus loin que d'utiliser un point intermédiaire comme dans X-Y-Z. Mais peut être leurs directions de marche optimiser pour un autre paramètre, aussi?
PPS. Voici une autre violation de l'inégalité du triangle qui suggère (pour moi) qu'ils utilisent une sorte d'approche à plusieurs niveaux: X-Z versus X-Y-Z. Le premier semble utiliser le boulevard de Sébastopol bien qu'il soit légèrement à l'écart.
Edit : aucun de ces exemples ne semble fonctionner plus, mais les deux l'ont fait au moment de la publication originale.
18 réponses
Parlant comme quelqu'un qui a passé 18 mois à travailler dans une société de cartographie, ce qui comprenait le travail sur l'algorithme de routage... Oui, de Dijkstra fonctionne, avec quelques modifications:
- au lieu de faire Dijkstra Une fois de la source à dest, vous commencez à chaque extrémité, et développez les deux côtés jusqu'à ce qu'ils se rencontrent au milieu. Ceci élimine à peu près 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 destination, vous pouvez avoir plusieurs couches de données cartographiques: une couche "autoroutes" qui ne contient que des autoroutes, une couche "secondaire" qui ne contient que des rues secondaires, et ainsi de suite. Ensuite, vous n'explorez que des sections plus petites des couches plus détaillées, en les élargissant si nécessaire. Évidemment, cette description laisse beaucoup de détails, mais vous obtenez l'idée.
Avec des modifications dans ce sens, vous pouvez faire même un routage cross-country dans un délai très raisonnable.
Cette question a été un domaine de recherche actif au cours des dernières années. L'idée principale est de faire un prétraitement sur le graphe une fois, à accélérer tous les requêtes suivantes. Avec cette information supplémentaire, les itinéraires peuvent être calculés très rapidement. Pourtant, L'algorithme de Dijkstra est la base de toutes les optimisations.
Arachnid décrit l'utilisation de la recherche bidirectionnelle et de l'élagage des arêtes à partir d'informations hiérarchiques. Ces speedup les techniques fonctionnent assez bien, mais les algorithmes les plus récents surpassent ces techniques par tous les moyens. Avec les algorithmes actuels, les chemins Les plus courts peuvent être calculés en moins de temps que une milliseconde sur un réseau routier continental. Une implémentation rapide de L'algorithme non modifié de Dijkstra nécessite environ 10 secondes .
Les algorithmes connus les plus rapides 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 d'itinéraire. Cette précalculation peut ensuite être utilisée pour élaguer la recherche: loin du départ et de la destination les routes lentes n'ont pas besoin d'être prises en compte lors de L'algorithme de Dijkstra. Les avantages sont très Bonne performance et uneexactitude garantie pour le résultat.
Les premiers algorithmes de planification d'itinéraires optimisés 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 dans la pratique, puisque nous voulons prendre en compte des informations dynamiques telles que les embouteillages ou les restrictions dépendantes du véhicule. Les derniers algorithmes peuvent également traiter de tels problèmes, mais il y a encore des problèmes à résoudre et la recherche est en cours sur.
Si vous avez besoin des distances de chemin les plus courtes pour calculer une solution pour le TSP , alors vous êtes probablement intéressé par les matrices qui contiennent toutes les distances entre vos sources et destinations. Pour cela, vous pouvez envisager de calculer des chemins Les plus courts de plusieurs à plusieurs en utilisant des hiérarchies D'autoroutes . Notez que cela a été amélioré par de nouvelles approches au cours des 2 dernières années.
Juste aborder les violations de l'inégalité du triangle, espérons que le facteur supplémentaire pour lequel ils optimisent est le bon sens. On ne veut pas nécessairement le plus court ou le plus rapide, itinéraire, car il peut conduire à chaos et destruction. Si vous voulez que vos directions préfèrent les routes principales qui sont compatibles avec les camions et peuvent faire face à l'envoi de tous les pilotes sat-nav-suivants, vous supprimez rapidement l'inégalité du triangle [1].
Si Y est une résidence étroite rue entre X et Z, vous ne voulez probablement utiliser le raccourci via Y que si l'utilisateur demande explicitement X-Y-Z. S'ils demandent X-Z, ils devraient s'en tenir aux routes principales même si c'est un peu plus loin et prend un peu plus de temps. C'est similaire au paradoxe de Braess - si tout le monde essaie de prendre la route la plus courte et la plus rapide, la congestion qui en résulte signifie que ce n'est plus la route la plus rapide pour quiconque. De là, nous nous éloignons de la théorie des graphes en théorie des jeux.
[1] en fait, tout espoir que les distances produites seront une fonction de distance dans le sens mathématique meurt lorsque vous autorisez les routes à Sens Unique et perdre l'exigence de symétrie. Perdre l'inégalité du triangle aussi est juste frotter le sel dans la plaie.
Voici les algorithmes de routage les plus rapides du monde comparés et éprouvés pour l'exactitude:
Http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf
Voici un google tech talk sur le sujet:
Http://www.youtube.com/watch?v=-0ErpE8tQbw
Voici une implémentation de l'algorithme highway-hierarchies comme discuté par schultes (actuellement à berlin seulement, j'écris l'interface et une version mobile est en cours de développement comme bien):
Les algorithmes de graphe comme l'algorithme de Dijkstra ne fonctionneront pas parce que le graphe est énorme.
Cet argument ne tient pas nécessairement parce que Dijkstra ne regarde généralement pas le graphe complet mais plutôt juste un très petit sous-ensemble (plus le graphe est interconnecté, plus ce sous-ensemble est petit).
Dijkstra peut effectivement fonctionner plutôt bien pour les graphiques bien comportés. D'un autre côté, avec une paramétrisation soigneuse, A* fonctionnera toujours aussi bien, ou mieux. Avoir vous avez déjà essayé comment cela fonctionnerait sur vos données?
Cela dit, je serais également très intéressé d'entendre parler des expériences des autres peuples. Bien sûr, des exemples importants comme la recherche de Google Map sont particulièrement intéressants. Je pourrais imaginer quelque chose comme une heuristique dirigée plus proche voisin.
Je n'ai pas travaillé sur Google ou Microsoft ou Yahoo Maps avant, donc je ne peux pas vous dire comment ils fonctionnent.
Cependant, j'ai conçu un système d'optimisation de la chaîne d'approvisionnement personnalisé pour une entreprise énergétique qui comprenait une application de planification et de routage pour leur flotte de camions. Cependant, nos critères sur le routage étaient beaucoup plus spécifiques à l'entreprise que lorsque la construction ou le trafic ralentit ou la fermeture de voies.
Nous avons utilisé une technique appelée ACO (ant colony optimization) pour planifier et route des camions. Cette technique est une technique AI qui a été appliquée au problème de vendeur ambulant pour résoudre les problèmes de routage. L'astuce 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 google ACO ou TSP pour en savoir plus sur cette technique. Je n'ai utilisé aucun des outils D'IA open-source pour cela, donc je ne peux pas en Suggérer un (même si J'ai entendu SWARM était assez complet).
L'état actuel de la technique en termes de temps de requête pour les réseaux routiers statiques est l'algorithme D'étiquetage du 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 été récemment 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 Hub fournit le plus rapide requêtes pour les réseaux routiers statiques, mais nécessite une grande quantité de ram pour fonctionner (18 GiB).
Le routage des nœuds de Transit est légèrement plus lent, bien qu'il ne nécessite qu'environ 2 Go de mémoire et dispose d'un temps de prétraitement plus rapide.
Les hiérarchies de Contraction offrent un bon compromis entre les temps de prétraitement rapides, les faibles besoins en espace (0,4 GiB) et les temps de requête rapides.
Aucun algorithme est complètement dominer...
Ce Google tech talk par Peter Sanders peut être d'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 à KIT. http://algo2.iti.kit.edu/english/routeplanning.php
Aussi un billet de blog facilement accessible écrit par Microsoft sur l'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. Cet algorithme fonctionne très bien comme celui de Dijkstra. il a aussi une fonctionnalité très intéressante qui est qu'il vous permet de calculer aussi longtemps que vous souhaitez continuer à autoriser des sommets plus intermédiaires. Ainsi, il trouvera naturellement les routes qui utilisent des autoroutes ou des autoroutes assez rapidement.
Je l'ai fait beaucoup de fois, en fait, en essayant plusieurs méthodes différentes. Selon la taille (géographique) de la carte, vous pouvez envisager d'utiliser la fonction haversine comme heuristique.
La meilleure solution que j'ai faite était d'utiliser un* avec une distance en ligne droite comme fonction heuristique. Mais alors vous avez besoin d'une sorte de coordonnées pour chaque point (intersection ou Sommet) sur la carte. Vous pouvez également essayer différentes pondérations pour la fonction heuristique, c'est-à-dire
f(n) = k*h(n) + g(n)
Où k est une constante supérieure à 0.
Probablement similaire à la réponse sur les routes pré-calculées entre les principaux emplacements et les cartes en couches, mais je crois comprendre que dans les jeux, pour accélérer un*, vous avez une carte très grossière pour la navigation macro, et une carte à grain fin pour la navigation à la limite des directions macro. Vous avez donc 2 petits chemins à calculer, et donc votre espace de recherche est beaucoup plus petit que de simplement faire un seul chemin vers la destination. Et si vous êtes dans l'entreprise de le faire beaucoup, vous auriez un beaucoup de données pré-calculées pour au moins une partie de la recherche est une recherche de la pré-calculé de données, plutôt que de chercher un chemin.
J'ai eu quelques réflexions à ce sujet:
1) Rappelez-vous que les cartes représentent une organisation physique. Stockez la latitude / longitude de chaque intersection. Vous n'avez pas besoin de vérifier bien au-delà des points qui se trouvent dans la direction de votre cible. Ce n'est que si vous vous trouvez Bloqué que vous devez aller au-delà de cela. Si vous stockez une superposition de connexions supérieures, vous pouvez la limiter encore plus-vous ne traverserez normalement jamais l'une de celles-ci d'une manière qui s'éloigne de votre finale destination.
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. Trouvez les zones dans lesquelles se trouvent Votre source et votre cible, pour l'itinéraire de la zone de début et de fin de votre emplacement à chaque point de connexion, pour les zones entre les points de connexion. (Je soupçonne que beaucoup de ce dernier est déjà pré-calculé.)
Notez que les zones peuvent être plus petites qu'une zone métropolitaine. Toute ville avec terrain les caractéristiques qui le divisent (disons, une rivière) seraient plusieurs zones.
J'étais très curieux des heuristiques utilisées, quand il y a quelque temps, nous avons eu des itinéraires du même point de départ près de Santa Rosa, à deux terrains de camping différents dans le Parc National de Yosemite. Ces différentes destinations ont produit des routes assez différentes (Via I-580 ou CA-12) malgré le fait que les deux routes ont convergé sur les 100 derniers milles (le long de CA-120) avant de diverger à nouveau de quelques milles à la fin. C'était assez reproductible. Les deux routes étaient jusqu'à 50 miles de distance pour environ 100 miles, mais les distances/temps étaient assez proches les uns des autres comme vous le souhaitez.
Hélas, je ne peux pas reproduire cela - les algorithmes ont dû changer. Mais il m'a fait curieux au sujet de l'algorithme. Tout ce que je peux spéculer, c'est qu'il y avait une taille directionnelle qui était extrêmement sensible à la minuscule différence angulaire entre les destinations vues de loin, ou qu'il y avait différents segments précalculés sélectionnés par le choix de la destination finale.
En parlant de GraphHopper , un planificateur d'itinéraire open Source rapide basé sur OpenStreetMap, j'ai lu un peu de littérature et implémenté certaines méthodes. La solution la plus simple est un Dijkstra et une amélioration simple est un Dijkstra bidirectionnel qui explore à peu près seulement la moitié des nœuds. Avec Dijkstra bidirectionnel un itinéraire à travers toute L'Allemagne prend déjà 1sec( pour le mode voiture), en C, il serait probablement seulement 0.5 S ou plus ;)
J'ai créé un gif animé d'une recherche de chemin réel avec Dijkstra bidirectionnel ici . Il y a aussi d'autres idées pour rendre Dijkstra plus rapide comme faire un*, qui est un "Dijkstra orienté vers les objectifs". J'ai aussi créé un gif-animation pour cela.
Mais comment le faire (beaucoup) plus vite?
Le problème est que pour une recherche de chemin tous les nœuds entre les emplacements doivent être explorés et cela est vraiment coûteux car déjà en Allemagne il y en a plusieurs millions. Mais un point de douleur supplémentaire de Dijkstra etc. est - ce que ces recherches utilisent beaucoup de RAM.
Il existe des solutions heuristiques mais aussi des solutions exactes qui organzisent 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é certains dans cette réponse .
Pour GraphHopper, j'ai décidé d'utiliser hiérarchies de Contraction car il est relatif "facile" à mettre en œuvre et ne prend pas de temps pour la préparation du graphique. Il en résulte toujours très rapide temps de réponse comme vous pouvez tester à notre instance en ligne GraphHopper Maps . Par exemple de L'Afrique du Sud à la Chine orientale {[2] } qui se traduit par une distance de 23000 km et près de 14 jours de conduite pour la voiture et n'a pris que ~ 0.1 s sur le serveur.
C'est de la pure spéculation de ma part, mais je suppose qu'ils peuvent utiliser une structure de données de carte d'influence superposant 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 voyage souhaité est long.
Étant donné qu'il s'agit D'une application Google, il est également raisonnable de supposer que beaucoup de magie se fait via une mise en cache étendue. :) Je ne serais pas surpris si la mise en cache du top 5% des demandes D'Itinéraire Google Map les plus courantes autorisé pour un gros morceau (20%? 50%?) des demandes auxquelles il faut répondre par une simple recherche.
J'ai travaillé sur le routage pendant quelques années, avec une récente explosion d'activité provoquée par les besoins de mes clients, et j'ai trouvé Qu'A* est facilement assez rapide; il n'y a vraiment pas besoin de chercher des optimisations ou des algorithmes plus complexes. Routage sur un énorme graphique n'est pas un problème.
Mais la vitesse dépend d'avoir l'ensemble du réseau de routage, par lequel je veux dire le graphique dirigé des arcs et des nœuds représentant respectivement des segments de route et des jonctions, en mémoire. Le principal temps les frais généraux sont le temps nécessaire pour créer ce réseau. Quelques chiffres approximatifs basés sur un ordinateur portable ordinaire fonctionnant sous Windows, et le routage sur toute L'Espagne: temps nécessaire pour créer le réseau: 10-15 secondes; temps nécessaire pour calculer un itinéraire: trop court pour mesurer.
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 d'une manière ou d'une autre pour enregistrer la meilleure route (coût total du nœud actuel et meilleur arc à il) - comme il doit dans un* - vous devez réinitialiser ou effacer cette ancienne information. Plutôt que de parcourir des centaines de milliers de nœuds, il est plus facile d'utiliser un système de numéro de génération. Marquez chaque nœud avec le numéro de génération de ses données; incrémentez le numéro de génération lorsque vous calculez une nouvelle route; 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 dans L'OP:
Regardez l'itinéraire avec le point intermédiaire spécifié: L'itinéraire recule légèrement à cause de cette route qui n'est pas droite.
Si leur algorithme ne recule pas, il ne verra pas l'itinéraire le plus court.
Un algorithme de chemin le plus court de toutes les paires calcule les chemins Les plus courts entre tous les sommets d'un graphe. Cela permettra aux chemins d'être pré-calculés au lieu d'exiger 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 de toutes les paires.
Les cartes ne prennent jamais en considération la carte entière. Ma conjecture est:- 1. Selon votre emplacement, ils chargent un lieu et les points de repère sur cet endroit. 2. Lorsque vous recherchez la destination, c'est quand ils chargent l'autre partie de la carte et font un graphique de 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 être utilisée dans le calcul des chemins Les plus courts. Vous pouvez également vous référer à cela.