Question Quels algorithmes calculent les directions du point A au point B sur une carte?


Comment les fournisseurs de cartes (tels que Google ou Yahoo!

Je veux dire, ils ont probablement des données du monde réel sous une forme ou une autre, y compris des distances, mais aussi des vitesses de conduite, des trottoirs, des horaires de train, etc. Mais supposons que les données soient plus simples. avec des poids de bord reflétant les distances. Je veux pouvoir calculer rapidement les directions d'un point arbitraire à un autre. Parfois, ces points seront rapprochés (au sein d'une même ville) alors que parfois ils seront éloignés (cross-country).

Les algorithmes de graphes comme l'algorithme de Dijkstra ne fonctionneront pas car le graphique est énorme. Heureusement, les algorithmes heuristiques comme A * fonctionneront probablement. Cependant, nos données sont très structurées et une approche à plusieurs niveaux pourrait peut-être fonctionner? (Par exemple, stocker des directions précalculées entre certains points «clés» éloignés, ainsi que des directions locales. Ensuite, les directions pour deux points lointains impliqueront des directions locales vers des points clés, des directions globales vers un autre point clé, puis locales. directions à nouveau.)

Quels algorithmes sont réellement utilisés dans la pratique?

PS. Cette question a été motivée par trouver des bizarreries dans les directions de cartographie en ligne. Contrairement à l'inégalité triangulaire, 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 optimisent pour un autre paramètre, aussi?

PPS. Voici une autre violation de l'inégalité triangulaire qui suggère (pour moi) qu'ils utilisent une sorte d'approche à plusieurs niveaux: X-Z contre X-Y-Z. La première semble utiliser le boulevard de Sébastopol, même si c'est un peu à l'écart.

modifier: Aucun de ces exemples ne semble plus fonctionner, mais les deux l’ont fait au moment de la publication initiale.


509
2018-01-09 23:35


origine


Réponses:


Parler de quelqu'un qui a passé 18 mois à travailler dans une entreprise de cartographie, y compris travailler sur l'algorithme de routage ... oui, Dijkstra fonctionne, avec quelques modifications:

  • Au lieu de faire Dijkstra une fois de la source à la dest, vous commencez à chaque extrémité, et développez les deux côtés jusqu'à ce qu'ils se rencontrent au milieu. Cela é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 votre destination, vous pouvez disposer de plusieurs couches de données cartographiques: une couche "autoroutes" qui contient uniquement des autoroutes, une couche "secondaire" qui ne contient que des rues secondaires, etc. Ensuite, vous explorez uniquement les plus petites sections des couches plus détaillées, en les élargissant si nécessaire. Évidemment, cette description laisse beaucoup de détails, mais vous avez l’idée.

Avec des modifications dans ce sens, vous pouvez même faire du routage à travers le pays dans des délais très raisonnables.


476
2018-01-11 12:41



Cette question a été un domaine de recherche actif ces dernières années. L'idée principale est de faire un prétraitement sur le graphique une fois que, à accélérer tout requêtes suivantes. Avec ces informations supplémentaires, les itinéraires peuvent être calculés très rapidement. Encore, L'algorithme de Dijkstra est la base de toutes les optimisations.

Arachnide décrit l'utilisation de la recherche bidirectionnelle et de l'élagage des contours sur la base d'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, 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.

L'article Ingénierie Algorithmes de planification d'itinéraires rapides donne un aperçu des progrès de la recherche dans ce domaine. Voir les références de ce document pour plus d'informations.

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 hiérarchie propre optimisée pour accélérer la planification d'itinéraire. Ce précalcul peut ensuite être utilisé pour élaguer la recherche: Loin du départ et de la destination, les routes lentes ne doivent pas être considérées pendant l'algorithme de Dijkstra. Les avantages sont très bons performance et un exactitude garantie pour le résultat.

Les premiers algorithmes de planification d'itinéraire optimisés ne traitaient que des réseaux routiers statiques, ce qui signifie qu'une arête dans le graphique a une valeur de coût fixe. Cela n'est pas vrai dans la pratique, puisque nous voulons prendre en compte des informations dynamiques comme les embouteillages ou les restrictions liées aux véhicules. Les derniers algorithmes peuvent également traiter de tels problèmes, mais il reste des problèmes à résoudre et la recherche est en cours.

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 vos destinations. Pour cela, vous pouvez envisager Calcul des chemins les plus courts en plusieurs à plusieurs en utilisant les hiérarchies de routes. Notez que cela a été amélioré par les nouvelles approches au cours des 2 dernières années.


102
2018-02-21 22:12



Juste en s'attaquant aux violations de l'inégalité triangulaire, j'espère que le facteur supplémentaire pour lequel ils optimisent est le bon sens. Vous ne voulez pas nécessairement l'itinéraire le plus court ou le plus rapide, car cela peut conduire à le chaos  et  destruction. Si vous voulez que vos directions préfèrent les routes principales qui sont favorables aux camions et peuvent faire en sorte que tous les pilotes sat-nav-following les envoient, vous rejetez rapidement l'inégalité triangulaire [1].

Si Y est une rue résidentielle étroite 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 rester sur les routes principales même si c'est un peu plus loin et prend un peu plus de temps. C'est similaire à Le 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 qui que ce soit. De là, nous nous écartons de la théorie des graphes pour la 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 des routes à sens unique et perdez l'exigence de symétrie. Perdre l'inégalité de triangle est aussi juste de frotter le sel dans la plaie.


16
2018-02-24 23:52



Voici les algorithmes de routage les plus rapides au monde comparés et éprouvés pour leur exactitude:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

Voici une discussion tech de google sur le sujet:

http://www.youtube.com/watch?v=-0ErpE8tQbw

Voici une implémentation de l'algorithme highway-hierarchies tel que discuté par schultes (actuellement à Berlin seulement, j'écris l'interface et une version mobile est en cours de développement):

http://tom.mapsforge.org/


14
2017-10-26 17:37



Les algorithmes de graphes comme l'algorithme de Dijkstra ne fonctionneront pas car le graphique est énorme.

Cet argument ne tient pas nécessairement parce que Dijkstra ne regarde généralement pas le graphe complet mais plutôt un très petit sous-ensemble (plus le graphe est interconnecté, plus ce sous-ensemble est petit).

Dijkstra peut effectivement se comporter plutôt bien pour les graphes bien élevés. D'un autre côté, avec une paramétrisation minutieuse, 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é d'entendre parler des expériences des autres. Bien entendu, des exemples importants comme la recherche de Google Map sont particulièrement intéressants. Je pourrais imaginer quelque chose comme une heuristique dirigée par le plus proche voisin.


8
2018-01-10 00:47



Je n'ai jamais travaillé sur Google, Microsoft ou Yahoo Maps auparavant, 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 compagnie d'énergie qui comprenait une application d'ordonnancement et de routage pour leur flotte de camions. Cependant, nos critères d'acheminement étaient beaucoup plus spécifiques à l'entreprise que les ralentissements de construction ou de circulation ou les fermetures de voies.

Nous avons utilisé une technique appelée ACO (optimisation des colonies de fourmis) pour planifier et acheminer les camions. Cette technique est une technique AI qui a été appliquée au problème du voyageur de commerce 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 de sorte que le modèle de résolution de graphe sache quand il faut 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 (bien que j'ai entendu que SWARM était assez complet).


8
2018-02-25 14:50



L'état actuel de la technique en termes de temps de requête pour les réseaux routiers statiques est l'algorithme d'étiquetage de Hub proposé par Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . Une étude approfondie et très bien écrite du domaine a récemment été publiée en tant que rapport technique Microsoft. http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

La version courte est ...

L'algorithme d'étiquetage du Hub fournit les requêtes les plus rapides pour les réseaux routiers statiques, mais nécessite une grande quantité de RAM pour fonctionner (18 Gio).

Le routage des nœuds de transit est légèrement plus lent, bien qu'il ne nécessite que 2 Go de mémoire et qu'il ait un temps de prétraitement plus rapide.

Les hiérarchies de contraction offrent un bon compromis entre les temps de prétraitement rapides, les besoins en espace réduits (0,4 Gio) et les temps de requête rapides.

Aucun algorithme n'est complètement dominant ...

Ce discours technique de Google par Peter Sanders peut être intéressant

https://www.youtube.com/watch?v=-0ErpE8tQbw

Aussi cette conférence par Andrew Goldberg

https://www.youtube.com/watch?v=WPrkc78XLhw

Une mise en œuvre 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

Aussi un 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/


7
2017-08-25 18:55



Je suis un peu surpris de ne pas voir L'algorithme de Floyd Warshall mentionné ici. Cet algorithme ressemble beaucoup à celui de Dijkstra. Il a aussi une très belle fonctionnalité qui vous permet de calculer tant que vous souhaitez continuer à autoriser d'autres sommets intermédiaires. Ainsi, il trouvera naturellement les routes qui utilisent les autoroutes ou autoroutes assez rapidement.


7
2017-12-09 00:04



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 A * 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.


6
2017-11-02 17:29



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 A *, vous avez une carte qui est très grossière pour la navigation macro, et une carte fine pour navigation vers 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 avez l'habitude de faire cela beaucoup, vous auriez beaucoup de ces données pré-calculées donc au moins une partie de la recherche est une recherche de données pré-calculées, plutôt qu'une recherche d'un chemin.


4
2018-02-26 01:21



J'ai eu d'autres réflexions à ce sujet:

1) Rappelez-vous que les cartes représentent une organisation physique. Stocke la latitude / longitude de chaque intersection. Vous n'avez pas besoin de vérifier beaucoup au-delà des points qui se trouvent dans la direction de votre cible. Seulement si vous vous trouvez bloqué devez-vous aller au-delà de cela. Si vous stockez une superposition de connexions supérieures, vous pouvez la limiter encore plus - normalement, vous ne traverserez jamais l'une d'entre elles d'une manière qui s'éloigne de votre destination finale.

2) Divisez le monde en un ensemble 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 la route de la zone de début et de fin, de votre position à chaque point de connexion, pour les zones entre simplement la carte 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 des caractéristiques de terrain qui la divisent (disons, une rivière) serait plusieurs zones.


3
2018-02-21 23:31