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

Comment les fournisseurs de cartes (tels que Google ou Yahoo! Maps) suggèrent-ils des itinéraires?

Je veux dire, ils ont probablement des données du monde réel sous une certaine forme, y compris certainement les distances mais aussi peut-être des choses comme les vitesses de conduite, la présence de trottoirs, les horaires des trains, etc. Mais supposons que les données soient dans un format plus simple, disons un très grand graphique dirigé avec des poids d'arête reflétant les distances. Je veux pouvoir calculer rapidement des directions d'un point arbitraire à un autre. Parfois ces points seront rapprochés (au sein d'une même ville) tandis que parfois ils seront éloignés (cross-country).

Les algorithmes graphiques comme l'algorithme de Dijkstra ne fonctionneront pas car le graphique est énorme. Heureusement, des algorithmes heuristiques comme A * fonctionneront probablement. Cependant, nos données sont très structurées, et peut-être qu'une sorte d'approche à plusieurs niveaux pourrait fonctionner? (Par exemple, stockez des directions précalculées entre certains points «clés» très éloignés, ainsi que certaines directions locales. Ensuite, les directions pour deux points éloignés impliqueront des directions locales vers un point clé, 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 était 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 XZ prend plus de temps et est plus loin que l'utilisation d'un point intermédiaire comme dans XYZ . Mais peut-être que leurs directions de marche optimisent également pour un autre paramètre?

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: XZ contre XYZ . Le premier semble utiliser le boulevard de Sébastopol, même s'il est légèrement à l'écart.

Edit : Aucun de ces exemples ne semble plus fonctionner, mais les deux fonctionnaient au moment de la publication d'origine.

Parlant comme quelqu'un qui a passé 18 mois à travailler dans une société de cartographie, ce qui comprenait un travail sur l'algorithme de routage ... oui, Dijkstra fonctionne, avec quelques modifications:

• Au lieu de faire une fois de Dijkstra de la source au dest, vous commencez à chaque extrémité et développez 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 '' qui ne contient que des autoroutes, une couche `` secondaire '' qui ne contient que des rues secondaires, etc. Ensuite, vous explorez uniquement des sections plus petites des couches plus détaillées, en les développant si nécessaire. Évidemment, cette description laisse de côté beaucoup de détails, mais vous avez l'idée.

Avec des modifications dans ce sens, vous pouvez même effectuer un routage entre pays 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 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. Pourtant, l'algorithme de Dijkstra est la base de toutes les optimisations.

Arachnid a décrit l'utilisation de la recherche bidirectionnelle et de l'élagage des bords 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 trajets les plus courts peuvent être calculés en beaucoup moins de temps qu'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 Engineering Fast Route Planning Algorithms 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 autoroute 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: Loin des routes lentes de départ et de destination, il n'est pas nécessaire de prendre en compte l'algorithme de Dijkstra. Les avantages sont de très bonnes performances et une garantie d' exactitude 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. Ce n'est pas vrai dans la pratique, car 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 se poursuit.

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 les chemins les plus courts de plusieurs à plusieurs à l'aide des hiérarchies d'autoroute . Notez que cela a été amélioré par de nouvelles approches au cours des 2 dernières années.

S'attaquer uniquement aux violations des inégalités du triangle, espérons 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 au chaos et à la destruction . Si vous souhaitez que vos directions préfèrent les itinéraires principaux qui sont adaptés aux camions et peuvent faire en sorte que tous les conducteurs de navigation par satellite soient envoyés, vous éliminez rapidement l'inégalité du triangle [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 XYZ. S'ils demandent XZ, 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 l'itinéraire le plus court et le plus rapide, la congestion qui en résulte signifie que ce n'est plus l'itinéraire le plus rapide pour quiconque. De là, nous nous éloignons de la théorie des graphes dans la théorie des jeux.

[1] En fait, tout espoir que les distances produites seront une fonction de distance au sens mathématique meurt lorsque vous autorisez des routes à sens unique et perdez l'exigence de symétrie. Perdre l'inégalité du triangle, c'est simplement frotter du sel dans la plaie.

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 présentation technique de Google sur le sujet:

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

Voici une implémentation de l'algorithme autoroute-hiérarchie tel que discuté par schultes (actuellement à berlin uniquement, j'écris l'interface et une version mobile est également en cours de développement):

http://tom.mapsforge.org/

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

Nous avons utilisé une technique appelée ACO (Ant colony optimisation) pour planifier et acheminer les camions. Cette technique est une technique d'IA 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 afin que le modèle de résolution de graphique sache quand quitter (quand l'erreur est-elle suffisamment petite).

Vous pouvez google ACO ou TSP pour en savoir plus sur cette technique. Je n'ai cependant 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 que SWARM était assez complet).

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

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

Dijkstra peut en fait plutôt bien fonctionner pour les graphiques bien comportés. D'un autre côté, avec un paramétrage soigneux, A * fonctionnera toujours aussi bien, voire mieux. Avez-vous déjà essayé comment cela se produirait sur vos données?

Cela dit, je serais également très intéressé d'entendre parler des expériences des autres. Bien sûr, des exemples importants comme la recherche sur Google Map sont particulièrement intéressants. Je pourrais imaginer quelque chose comme une heuristique dirigée du plus proche voisin.

L'état actuel de la technique en termes de temps de requête 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 étude approfondie et parfaitement é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 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 Gio de mémoire et 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 Gio) et les temps de requête rapides.

Aucun algorithme ne domine complètement ...

Cette conférence technique de Google par Peter Sanders peut être intéressante

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

Aussi cette conférence d'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 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 également une fonctionnalité très intéressante qui vous permet de calculer aussi longtemps que vous souhaitez continuer à autoriser plus de sommets intermédiaires. Il trouvera donc naturellement les itinéraires empruntant les autoroutes ou les autoroutes assez rapidement.

Je l'ai fait plusieurs 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.-à-d.

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 emplacements et les cartes en couches, mais je crois comprendre que dans les jeux, pour accélérer A *, vous avez une carte très grossière pour la navigation macro et une carte à grain fin pour navigation jusqu'à la limite des macro-directions. 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 souvent en train de faire cela, 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 de chemin.

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 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 se fait via une mise en cache étendue. :) Je ne serais pas surpris si la mise en cache des 5% des demandes d'itinéraire Google Map les plus courantes permettait de répondre à une grande partie (20%? 50%?) Des demandes par une simple recherche.

J'avais encore quelques réflexions à ce sujet:

1) N'oubliez pas que les cartes représentent une organisation physique. Enregistrez 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 plus loin. 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. Trouvez les zones dans lesquelles se trouvent votre source et votre cible, pour l'itinéraire de début et de fin de votre emplacement à chaque point de connexion, pour les zones entre simplement mapper 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 avec des caractéristiques de terrain qui la divisent (disons une rivière) serait constituée de plusieurs zones.

J'étais très curieux au sujet de l'heuristique utilisée, quand il y a quelque temps nous avons eu des itinéraires du même endroit 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 itinéraires très différents (via la I-580 ou la CA-12) malgré le fait que les deux routes ont convergé sur les 100 derniers kilomètres (le long de la CA-120) avant de diviser à nouveau de quelques kilomètres à la fin. C'était assez répétable. Les deux itinéraires étaient distants jusqu'à 50 miles sur environ 100 miles, mais les distances / temps étaient assez proches l'un de l'autre comme vous vous en doutez.

Hélas, je ne peux pas reproduire cela - les algorithmes doivent avoir changé. Mais cela m'a intéressé par l'algorithme. Tout ce que je peux supposer, c'est qu'il y avait un élagage directionnel 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 mis en œuvre certaines méthodes. La solution la plus simple est un Dijkstra et une amélioration simple est un Dijkstra bidirectionnel qui n'explore à peu près que la moitié des nœuds. Avec bidirectionnelle Dijkstra, un itinéraire à travers toute l'Allemagne prend déjà 1 seconde (pour le 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 y a aussi d'autres idées pour rendre Dijkstra plus rapide comme faire A *, qui est un "Dijkstra orienté objectif". J'ai également créé une animation gif pour cela.

Mais comment 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 problème supplémentaire de Dijkstra, etc., est que ces 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, à la fois ont des avantages et des inconvénients et résolvent principalement le problème de vitesse et de RAM. J'en ai énuméré certains dans cette réponse .

Pour GraphHopper, j'ai décidé d'utiliser les hiérarchies de contraction car il est relativement «facile» à mettre en œuvre et ne prend pas beaucoup de temps pour la préparation du graphique. Il en résulte toujours des temps de réponse très rapides comme vous pouvez le tester sur notre instance en ligne GraphHopper Maps . Par exemple, de l'Afrique du Sud à l'est de la Chine, ce qui entraîne une distance de 23 000 km et près de 14 jours de temps de conduite pour la voiture et n'a pris que ~ 0,1 s sur le serveur.

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é que A * est facilement assez rapide; il n'y a vraiment pas besoin de chercher des optimisations ou des algorithmes plus complexes. Le routage sur un énorme graphique n'est pas un problème.

Mais la vitesse dépend de la mise en mémoire de l'intégralité du réseau de routage, c'est-à-dire du graphique dirigé des arcs et des nœuds représentant respectivement les segments et les jonctions de routage. Le temps système principal est le temps nécessaire pour créer ce réseau. Quelques chiffres approximatifs basés sur un ordinateur portable ordinaire exécutant Windows et un 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 ê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 d'une manière ou d'une autre pour enregistrer le meilleur itinéraire (coût total pour le nœud actuel et meilleur arc vers celui-ci) - comme il le doit dans 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 de numéros 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 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 dans l'OP:

Regardez l'itinéraire avec le point intermédiaire spécifié: L'itinéraire va légèrement en arrière en raison de cette route qui n'est pas droite.

Si leur algorithme ne revient pas en arrière, il ne verra pas l'itinéraire le plus court.

Un algorithme de chemin le plus court toutes 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 Floyd-Warshall est un algorithme de chemin le plus court toutes paires.

Les cartes ne prennent jamais en compte l'ensemble de la carte. Ma conjecture est: - 1. Selon votre emplacement, ils chargent un endroit 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 à deux endroits, puis appliquent les algorithmes de chemin le plus court.

En outre, il existe une technique importante de programmation dynamique qui, je le soupçonne, est utilisée dans le calcul des chemins les plus courts. Vous pouvez également vous y référer.