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

Question

Comment faire une carte de fournisseurs (tels que Google ou Yahoo! Des cartes), de proposer des orientations?

Je veux dire, ils ont probablement des données du monde réel dans une certaine forme, certainement, y compris des distances, mais aussi peut-être des choses comme la vitesse de conduite, la présence de trottoirs, les horaires de train, etc. Mais supposons que les données sont dans un format plus simple, dire un très grand graphe orienté avec le bord de pondérations reflétant les distances. Je veux être en mesure de calculer les directions à partir d'un point arbitraire à un autre. Parfois, ces points seront proches (dans une ville), tandis que parfois, ils seront éloignés (cross-country).

Algorithmes de graphes comme l'algorithme de Dijkstra ne fonctionnera pas car le graphique est énorme. Heureusement, des algorithmes heuristiques comme Un* fonctionnera probablement. Cependant, nos données sont très structurés, et peut-être un certain genre d'approche pourrait fonctionner? (Par exemple, de stocker précalculées directions entre certaines "clés" des points éloignés, ainsi que certaines directions locales. Ensuite, les directions de deux loin des points d'impliquer les directions à l'un des points clés, des orientations globales à un autre point clé, puis directions locales de nouveau.)

Quels algorithmes sont effectivement utilisés dans la pratique?

PS. Cette question a été motivée par la constatation bizarreries dans la cartographie en ligne les directions. Contrairement au triangle inégalités, parfois Google Maps pense que X-Z prend plus de temps et est plus loin que l'utilisation d'un point intermédiaire comme dans X-Y-Z. Mais peut-être que leurs trajets à pied pour optimiser un autre paramètre, trop?

PPS. Voici une autre violation du triangle de l'inégalité qui suggère (pour moi) qu'ils utilisent un certain type d'approche à plusieurs niveaux: X-Z par rapport à X-Y-Z. Le premier semble utiliser éminent Boulevard de Sébastopol, même si c'est légèrement hors de la voie.

Edit: aucun de ces exemples semblent fonctionner, mais les deux ont fait à l'époque de l'original post.

Answer 1

Parlant comme quelqu'un qui a passé 18 mois de travail à une société de cartographie, qui a notamment travaillé sur l'algorithme de routage... oui, Dijkstra est fonctionne, avec un couple de modifications:

• Au lieu de faire de Dijkstra est une fois de la source à la destination, vous commencez à chaque extrémité, et de développer des 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 l'arrière-allées de chaque ville entre votre source et de destination, vous pouvez avoir plusieurs couches de données de la carte: Une des "routes" de la couche qui contient uniquement les routes, un "secondaires" de la couche qui contient uniquement des rues secondaires, et ainsi de suite. Ensuite, vous n'examiner que les plus petites sections des couches plus détaillées, de l'expansion en tant que de besoin. Évidemment, cette description laisse beaucoup de détails, mais vous obtenez l'idée.

Avec des modifications le long de ces lignes, vous pouvez le faire même de cross-country de routage dans un très des délais raisonnables.

Answer 2

Cette question a été un domaine de recherche actif dans les dernières années. L'idée principale est de faire un prétraitement sur le graphique une fois, pour accélérer toutes les requêtes suivantes. Avec cette information supplémentaire itinéraires peuvent être calculées très rapide. Encore, l'Algorithme de Dijkstra est la base de toutes les optimisations.

Arachnid décrit l'utilisation de l'bidirectionnel de recherche et de bord de l'élagage basé sur la hiérarchie des informations. Ces accélération des techniques de travail très bien, mais le plus récent des algorithmes de surpasser ces techniques par tous les moyens. Avec les algorithmes actuels d'un des chemins les plus courts peuvent être calculées considérablement moins de temps qu' une milliseconde sur un petit réseau routier. Une mise en œuvre rapide de la non modifiée de l'algorithme de Dijkstra a besoin d'environ 10 secondes.

L'article de l'Ingénierie de Parcours Rapide de la Planification des Algorithmes donne un aperçu de l'avancement de la recherche dans ce domaine. Voir les références de ce document pour de plus amples informations.

Le plus rapide des algorithmes de ne pas utiliser les informations relatives à la hiérarchie de l'état de la route, dans les données, c'est à dire si c'est une autoroute ou d'une route locale. Au lieu de cela, ils calculent dans une étape de prétraitement une hiérarchie qui optimisée pour accélérer la planification de l'itinéraire. Ce précalcul peut ensuite être utilisé pour tailler la recherche: Loin de départ et de destination des voies lentes ne doivent pas être considérés lors de l'Algorithme de Dijkstra. Les prestations sont de très bonnes performances et une exactitude de garantie pour la suite.

Le premier itinéraire optimisé, planification des algorithmes de ne traitait que de la statique des réseaux routiers, ce qui signifie une arête dans le graphe a un coût fixe de la valeur. Ce n'est pas vrai en pratique, car nous voulons prendre des informations dynamiques comme les embouteillages ou d'un véhicule dépendant de restrictrions en compte. Derniers algorithmes pouvez également faire face à de tels problèmes, mais il y a encore des problèmes à résoudre et de la recherche est en cours.

Si vous avez besoin de la trajectoire la plus courte des distances pour calculer une solution pour le TSP, alors vous êtes probablement intéressé par les matrices qui contiennent toutes les distances entre les sources et les destinations. Pour cela, vous pourrait envisager de Calcul de plusieurs-à-Plusieurs plus courts Chemins à l'Aide de l'Autoroute Hiérarchies. Notez que cela a été améliorée par de nouvelles approches dans les 2 dernières années.

Answer 3

Voir cet article :

http://avglab.com/Andrew/pub/alenex06.pdf

L’anomalie de Google Maps est vraiment étrange, que je me demande quel chemin est effectivement mieux.

Answer 4

Juste aborder le triangle de l'inégalité des violations, j'espère que le facteur extra ils sont l'optimisation de la pour est de bon sens. On ne veut pas nécessairement le plus court ou le plus rapide, itinéraire, car il peut conduire à de chaos et de destruction. Si vous souhaitez que vos directives à préférer les principaux itinéraires de camions peut faire face à avoir à tous les sat-nav-pilote suivant envoyé vers le bas, vous avez rapidement jeter le triangle de l'inégalité[1].

Si Y est une étroite rue résidentielle entre X et Z, vous probablement ne voulez seulement utiliser le raccourci via Y si l'utilisateur le demande explicitement X-Y-Z. S'ils le demandent pour X-Z, ils devraient s'en tenir à de grandes routes, même si c'est un peu plus loin et prend un peu plus longtemps. Il est similaire à l' paradoxe de Braess - si tout le monde essaie de prendre le plus court, le plus rapide de l'itinéraire, la congestion qui signifie que ce n'est pas l'itinéraire le plus rapide pour toute personne de plus. De là, nous nous éloignons de la théorie des graphes dans la théorie des jeux.

[1] En fait, tout l'espoir que les distances produite sera une fonction de distance dans le sens mathématique meurt lorsque vous autorisez les routes à sens unique et de perdre la symétrie exigence. Perdre le triangle de l'inégalité est trop juste frotter de sel dans la plaie.

Answer 5

Voici les plus rapides du monde algorithmes de routage par rapport et prouvé l'exactitude de l':

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 mise en œuvre de l'autoroute-les hiérarchies de l'algorithme, comme discuté par schultes (actuellement à berlin, je suis en train d'écrire l'interface et une version mobile est en cours de développement en tant que bien):

http://tom.mapsforge.org/