J’écris une simulation de messagerie / logistique sur les cartes OpenStreetMap et j’ai réalisé que l’algorithme de base A *, comme illustré ci-dessous, ne sera pas assez rapide pour les grandes cartes (comme le Grand Londres).
Les nœuds verts correspondent à ceux qui ont été placés dans la queue ouverte / prioritaire et, en raison du nombre énorme (la carte entière est d’environ 1-2 millions), il faut environ 5 secondes pour trouver l’itinéraire illustré. Malheureusement, 100 ms par route sont à peu près ma limite absolue.
Actuellement, les nœuds sont stockés à la fois dans une liste de contiguïté et dans un tableau 2D spatial 100×100.
Je suis à la recherche de méthodes permettant d’échanger du temps de pré-traitement, de l’espace et, si nécessaire, de l’optimalité de la route, pour des requêtes plus rapides. La formule de Haversine en ligne droite pour le coût heuristique est la fonction la plus coûteuse selon le profileur – j’ai optimisé mon A * de base autant que possible.
Par exemple, je pensais que si je choisissais un nœud arbitraire X dans chaque quadrant du tableau 2D et exécutais A * entre eux, je peux stocker les itinéraires sur le disque pour les simulations ultérieures. Lors de l’interrogation, je ne peux lancer une recherche A * que dans les quadrants, pour aller entre la route précalculée et le X.
Existe-t-il une version plus raffinée de ce que j’ai décrit ci-dessus ou peut-être une méthode différente que je devrais suivre? Merci beaucoup!
Pour mémoire, voici quelques résultats de référence pour pondérer arbitrairement le coût heuristique et calculer le chemin entre 10 paires de nœuds choisis au hasard:
Weight // AvgDist% // Time (ms) 1 1 1461.2 1.05 1 1327.2 1.1 1 900.7 1.2 1.019658848 196.4 1.3 1.027619169 53.6 1.4 1.044714394 33.6 1.5 1.063963413 25.5 1.6 1.071694171 24.1 1.7 1.084093229 24.3 1.8 1.092208509 22 1.9 1.109188175 22.5 2 1.122856792 18.2 2.2 1.131574742 16.9 2.4 1.139104895 15.4 2.6 1.140021962 16 2.8 1.14088128 15.5 3 1.156303676 16 4 1.20256964 13 5 1.19610861 12.9
En augmentant de façon surprenante le coefficient à 1,1, le temps d’exécution a presque été divisé par deux tout en gardant le même itinéraire.
Vous devriez être capable de le rendre beaucoup plus rapide en compensant l’optimalité. Voir Admissibilité et optimalité sur wikipedia.
L’idée est d’utiliser une valeur epsilon
qui conduira à une solution pas pire que 1 + epsilon
fois le chemin optimal, mais qui entraînera moins de nœuds dans l’algorithme. Notez que cela ne signifie pas que la solution retournée sera toujours 1 + epsilon
fois le chemin optimal. C’est juste le pire des cas. Je ne sais pas exactement comment cela se comporterait dans la pratique pour votre problème, mais je pense que cela vaut la peine d’être exploré.
Vous recevez un certain nombre d’algorithmes qui s’appuient sur cette idée sur Wikipedia. Je pense que c’est votre meilleur pari pour améliorer l’algorithme et qu’il a le potentiel de fonctionner dans votre limite de temps tout en conservant de bons chemins.
Puisque votre algorithme traite des millions de nœuds en 5 secondes, je suppose que vous utilisez également des segments binarys pour l’implémentation, n’est-ce pas? Si vous les implémentez manuellement, assurez-vous qu’ils sont implémentés en tant que tableaux simples et qu’ils sont des segments binarys.
Il existe des algorithmes spécialisés pour ce problème qui font beaucoup de pré-calcul. De la mémoire, le pré-calcul ajoute des informations au graphique qu’A * utilise pour produire une heuristique beaucoup plus précise que la distance en ligne droite. Wikipedia donne les noms d’un certain nombre de méthodes sur http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks et indique que Hub Labeling est le leader. Une recherche rapide à ce sujet apparaît http://research.microsoft.com/pubs/142356/HL-TR.pdf . Une version plus ancienne, utilisant A *, se trouve à l’ adresse http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf .
Devez-vous vraiment utiliser Haversine? Pour couvrir Londres, j’aurais pensé que vous auriez pu prendre une terre plate et utiliser Pythagore, ou stocker la longueur de chaque lien dans le graphique.
Il y a un très bon article que Microsoft Research a écrit sur le sujet:
http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx
Le document original est hébergé ici (PDF):
http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf
Essentiellement, vous pouvez essayer quelques choses:
GraphHopper fait deux choses de plus pour obtenir un routage rapide, sans heuristique et flexible (note: je suis l’auteur et vous pouvez l’essayer en ligne ici )
Donc, il devrait être possible de vous obtenir des itinéraires rapides pour le grand Londres.
De plus, le mode par défaut est le mode de vitesse qui rend tout plus rapide (par exemple 30ms pour les routes européennes), mais moins flexible, car il nécessite un prétraitement ( hiérarchies de contraction ). Si vous n’aimez pas cela, désactivez-le et affinez encore les rues incluses pour la voiture ou créez probablement un nouveau profil pour les camions – par exemple, excluez les rues de service et les pistes qui devraient vous donner 30% supplémentaires. Et comme avec tout algorithme bidirectionnel, vous pouvez facilement implémenter une recherche parallèle.
Je pense que ça vaut la peine de mettre au point votre idée avec des “quadrants”. Plus ssortingctement, je l’appellerais une recherche d’itinéraire à basse résolution.
Vous pouvez sélectionner X nœuds connectés suffisamment proches et les traiter comme un nœud basse résolution unique. Divisez tout votre graphique en de tels groupes et vous obtenez un graphique en basse résolution. Ceci est une étape de préparation.
Afin de calculer un itinéraire de la source à la cible, identifiez d’abord les noeuds basse résolution auxquels ils appartiennent, puis recherchez l’itinéraire à faible résolution. Améliorez ensuite votre résultat en trouvant l’itinéraire sur un graphique haute résolution, en limitant toutefois l’algorithme uniquement aux nœuds appartenant à des nœuds basse résolution de l’itinéraire basse résolution (vous pouvez également envisager des nœuds basse résolution voisins jusqu’à une certaine profondeur). ).
Cela peut également être généralisé à plusieurs résolutions, pas seulement haut / bas.
À la fin, vous devriez avoir un itinéraire suffisamment proche de l’optimum. C’est localement optimal, mais il peut être quelque peu pire qu’optimal dans son ensemble, ce qui dépend du saut de résolution (c’est-à-dire l’approximation que vous faites lorsqu’un groupe de nœuds est défini comme un seul nœud).
Il y a des dizaines de variantes A * qui peuvent correspondre à la facture ici. Vous devez penser à vos cas d’utilisation, cependant.
Nous n’avons aucun moyen de connaître tous les détails auxquels vous et votre employeur avez access. Votre première étape devrait donc être CiteSeer ou Google Scholar: recherchez des articles traitant du cheminement avec le même ensemble général de contraintes que vous.
Ensuite, sélectionnez trois ou quatre algorithmes, effectuez le prototypage, testez leur évolution et optimisez-les. Vous devez garder à l’esprit que vous pouvez combiner différents algorithmes dans la même routine de grand cheminement en fonction de la distance entre les points, du temps restant ou de tout autre facteur.
Comme cela a déjà été dit, en raison de la petite taille de votre zone cible, la chute de Haversine est probablement votre première étape, ce qui vous fait gagner un temps précieux lors d’évaluations sortinggonomésortingques coûteuses. NOTE: Je ne recommande pas d’utiliser la distance euclidienne en lat, les coordonnées lon – reprojetez votre carte dans un Mercator par exemple, près du centre et utilisez les coordonnées cartésiennes en mètres ou en mètres!
La précomputation est la seconde, et changer de compilateur peut être une troisième idée évidente (passer à C ou C ++ – voir https://benchmarksgame.alioth.debian.org/ pour plus de détails).
Des étapes d’optimisation supplémentaires peuvent inclure l’élimination de l’allocation de mémoire dynamic et l’utilisation d’une indexation efficace pour la recherche parmi les nœuds (pensez à R-tree et à ses dérivés / alternatives).
J’ai travaillé dans une grande entreprise de navigation, et je peux donc affirmer que 100 ms devraient vous permettre de vous rendre de Londres à Athènes, même sur un appareil embarqué. Le Grand Londres serait une carte de test pour nous, car il est commodément petit (rentre facilement dans la RAM – ce n’est pas vraiment nécessaire)
Tout d’abord, A * est entièrement obsolète. Son principal avantage est qu’il ne nécessite “pas de prétraitement”. En pratique, vous devez de toute façon pré-traiter une carte OSM, ce qui est un avantage inutile.
Les drapeaux arc sont la technique principale pour vous donner un énorme gain de vitesse. Si vous divisez la carte en sections de 5×6, vous pouvez atsortingbuer une position de 1 bit dans un entier de 32 bits pour chaque section. Vous pouvez maintenant déterminer pour chaque bord s’il est toujours utile lorsque vous voyagez à la section {X,Y}
d’une autre section. Très souvent, les routes sont bidirectionnelles, ce qui signifie qu’une seule des deux directions est utile. Donc, l’une des deux directions a ce bit et l’autre l’a effacée. Cela peut ne pas sembler être un réel avantage, mais cela signifie que sur de nombreuses intersections, vous réduisez le nombre de choix à prendre en compte de 2 à 1, et cela ne prend qu’une opération sur un seul bit.
Habituellement, A * s’accompagne d’une consommation de mémoire excessive plutôt que de contraintes temporelles.
Cependant, je pense qu’il pourrait être utile de commencer par calculer uniquement avec des nœuds qui font partie des “grandes rues”, vous choisiriez une autoroute plutôt qu’une minuscule allée.
Je suppose que vous pouvez déjà l’utiliser pour votre fonction de pondération, mais vous pouvez être plus rapide si vous utilisez une queue prioritaire pour décider du nœud à tester pour la suite du voyage.
Vous pouvez également essayer de réduire le graphe à des noeuds faisant partie des arêtes à faible coût, puis à trouver un moyen de commencer / terminer vers le plus proche de ces noeuds. Donc, vous avez deux chemins du début à la “grande rue” et la “grande rue” pour finir. Vous pouvez maintenant calculer le meilleur chemin entre les deux nœuds qui font partie des “grandes rues” dans un graphique réduit.
Ancienne question, mais encore:
Essayez d’utiliser différents tas que “tas binary”. “Le meilleur tas de complexité asymptotique” est sans aucun doute Feaponacci Heap et sa page wiki a un bon aperçu:
https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times
Notez que le tas binary a un code plus simple et qu’il est implémenté sur le tableau et que la traversée du tableau est prévisible, de sorte que le processeur moderne exécute les opérations du tas binary beaucoup plus rapidement.
Cependant, étant donné que le jeu de données est suffisamment grand, d’autres tas gagneront sur le tas binary, en raison de leur complexité …
Cette question semble être un jeu de données assez grand.