Le routage de cartes, à la Google Maps?

Translate

J'ai toujours été intrigué par Map Routing, mais je n'ai jamais trouvé de didacticiel de niveau d'introduction (ou même avancé!). Quelqu'un a-t-il des pointeurs, des indices, etc.?

Mettre à jour:Je recherche principalement des pointeurs sur la manière dont un système de carte est implémenté (structures de données, algorithmes, etc.).

This question and all comments follow the "Attribution Required."

Toutes les réponses

Translate

Jetez un œil auprojet de plan de rue ouvertpour voir comment ce genre de chose est abordé dans un projet de logiciel véritablement libre utilisant uniquement des données fournies par l'utilisateur et souswiki contenant des éléments que vous pourriez trouver intéressants.

Il y a quelques années, les gars impliqués étaient assez faciles à vivre et ont répondu à beaucoup de questions que j'avais, donc je ne vois aucune raison pour laquelle ils ne sont toujours pas un bon groupe.

La source
Translate

Barry Brumitt, l'un des ingénieurs de la fonction de recherche d'itinéraire de Google Maps, a écrit un article sur le sujet qui pourrait être intéressant:

La voie vers un meilleur cheminement06.11.2007 à 15:47:00

La source
Translate

A * est en fait beaucoup plus proche des algorithmes de cartographie de production. Cela nécessite un peu moins d'exploration par rapport à l'algorithme original de Dijikstra.

La source
Translate

Par Map Routing, vous voulez dire trouver le chemin le plus court le long d'un réseau routier?

L'algorithme du plus court chemin de Dijkstra est le plus connu. Wikipédia n'a pas une mauvaise intro:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Il y a une applet Java ici où vous pouvez la voir en action:http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.htmlet Google, vous vous dirigez vers le code source dans à peu près n'importe quelle langue.

Toute mise en œuvre réelle pour générer des itinéraires de conduite comprendra un certain nombre de données sur le réseau routier qui décrivent les coûts associés aux liaisons et aux nœuds de traversée - hiérarchie du réseau routier, vitesse moyenne, priorité aux intersections, liaison des feux de circulation, virages interdits, etc.

La source
Translate

Au lieu d'apprendre les API à chaque fournisseur de services de carte (comme Gmaps, Ymaps api), il est bon d'apprendreMapstraction

"Mapstraction est une bibliothèque qui fournit une API commune pour diverses API de mappage javascript"

Je vous suggère d'aller à l'URL et d'apprendre une API générale. Il existe également une bonne quantité de How-Tos.

La source
Translate

Je n'ai pas encore trouvé de bon tutoriel sur le routage mais il y a beaucoup de code à lire:

Il existe des applications de routage GPL qui utilisent des données Openstreetmap, par exempleGosmorequi fonctionne sur Windows (+ mobile) et Linux. Il existe un certain nombre d'applications intéressantes [utilisant les mêmes données, mais gosmore a quelques utilisations intéressantespar exemple, interface avec des sites Web.

Le plus gros problème avec le routage est de mauvaises données, et vous n'obtenez jamais des données assez bonnes. Donc, si vous voulez l'essayer, gardez votre test très local afin de mieux contrôler les données.

La source
Translate

D'un point de vue conceptuel, imaginez faire tomber une pierre dans un étang et observer les ondulations. Les itinéraires représenteraient l'étang et la pierre votre position de départ.

Bien sûr, l'algorithme devrait rechercher une certaine proportion de n ^ 2 chemins à mesure que la distance n augmente. Vous prendriez votre position de départ et vérifieriez tous les chemins disponibles à partir de ce point. Appelez ensuite récursivement les points à la fin de ces chemins et ainsi de suite.

Vous pouvez augmenter les performances, en ne double-backing sur un chemin, en ne revérifiant pas les routes à un point s'il a déjà été couvert et en abandonnant les chemins qui prennent trop de temps.

Une autre manière consiste à utiliser l'approche de la phéromone des fourmis, où les fourmis rampent au hasard à partir d'un point de départ et laissent une trace d'odeur, qui s'accumule plus les fourmis traversent un chemin donné. Si vous envoyez (suffisamment) des fourmis à la fois du point de départ et des points d'arrivée, le chemin avec le parfum le plus fort sera finalement le plus court. En effet, le chemin le plus court aura été visité plus de fois dans une période donnée, étant donné que les fourmis marchent à un rythme uniforme.

MODIFIER @ Spikie

Pour expliquer davantage comment mettre en œuvre l'algorithme de bassin, les structures de données potentielles nécessaires sont mises en évidence:

Vous devrez stocker la carte en tant que réseau. Ceci est simplement un ensemble denodesetedgesentre eux. Un ensemble denodesconstituent unroute. Une arête joint deux nœuds (éventuellement les deux le même nœud), et a un associécosttel quedistanceoutimepour traverser le bord. Un bord peut être bidirectionnel ou unidirectionnel. Le plus simple est probablement d'avoir des arêtes unidirectionnelles et de doubler pour un trajet bidirectionnel entre les nœuds (c'est-à-dire un bord de A à B et un autre pour B à A).

A titre d'exemple, imaginez trois gares ferroviaires disposées en triangle équilatéral pointant vers le haut. Il y a aussi trois autres stations chacune à mi-chemin entre elles. Les bords joignent toutes les stations adjacentes ensemble, le diagramme final aura un triangle inversé assis à l'intérieur du plus grand triangle.

Étiquetez les nœuds en partant du bas à gauche, de gauche à droite et en haut, comme A, B, C, D, E, F (F en haut).

Supposons que les bords peuvent être traversés dans les deux sens. Chaque bord a un coût de 1 km.

Ok, nous souhaitons donc acheminer de la partie inférieure gauche A vers la gare supérieure F. Il existe de nombreux itinéraires possibles, y compris ceux qui se replient sur eux-mêmes, par exemple ABCEBDEF.

Nous avons une routine à dire,NextNode, qui accepte unnodeet uncostet s'appelle lui-même pour chaque nœud vers lequel il peut voyager.

Clairement, si nous laissons cette routine s'exécuter, elle découvrira finalement toutes les routes, y compris celles qui sont potentiellement infinies (par exemple ABABABAB, etc.). Nous empêchons cela de se produire en comparant lescost. Chaque fois que nous visitons un nœud qui n'a pas été visité auparavant, nous plaçons à la fois le coût et le nœud d'où nous venons contre ce nœud. Si un nœud a été visité avant de vérifier le coût existant et si nous sommes moins chers, nous mettons à jour le nœud et continuons (récurrence). Si nous sommes plus chers, nous sautons le nœud. Si tous les nœuds sont ignorés, nous quittons la routine.

Si nous atteignons notre nœud cible, nous quittons également la routine.

De cette façon, toutes les routes viables sont vérifiées, mais surtout celles dont le coût est le plus bas. À la fin du processus, chaque nœud aura le coût le plus bas pour accéder à ce nœud, y compris notre nœud cible.

Pour obtenir la route, nous travaillons à rebours à partir de notre nœud cible. Puisque nous avons stocké le nœud d'où nous venions avec le coût, nous sautons simplement en arrière pour construire l'itinéraire. Pour notre exemple, nous nous retrouverions avec quelque chose comme:

Nœud A - Coût (total) 0 - À partir du nœud Aucun
Nœud B - Coût 1 - À partir du nœud A
Nœud C - Coût 2 - À partir du nœud B
Nœud D - Coût 1 - À partir du nœud A
Nœud E - Coût 2 - À partir du nœud D / Coût 2 - À partir du nœud B (il s'agit d'une exception car le coût est égal)
Nœud F - Coût 2 - À partir du nœud D

Le chemin le plus court est donc l'ADF.

La source
Translate

D'après mon expérience de travail dans ce domaine, A * fait très bien le travail. Il est (comme mentionné ci-dessus) plus rapide que l'algorithme de Dijkstra, mais reste assez simple pour qu'un programmeur normalement compétent puisse l'implémenter et le comprendre.

Construire le réseau de routes est la partie la plus difficile, mais cela peut être décomposé en une série d'étapes simples: obtenir toutes les routes; trier les points dans l'ordre; faire des groupes de points identiques sur différentes routes en intersections (nœuds); ajoutez des arcs dans les deux sens où les nœuds se connectent (ou dans un seul sens pour une route à sens unique).

L'algorithme A * lui-même estbien documenté sur Wikipedia. L'endroit clé à optimiser est la sélection du meilleur nœud dans la liste ouverte, pour lequel vous avez besoin d'une file d'attente prioritaire hautes performances. Si vous utilisez C ++, vous pouvez utiliser l'adaptateur STL priority_queue.

Il est assez facile de personnaliser l'algorithme pour parcourir différentes parties du réseau (par exemple, piétons, voitures, transports en commun, etc.) en favorisant la vitesse, la distance ou d'autres critères. Vous faites cela en écrivant des filtres pour contrôler quels segments d'itinéraire sont disponibles, lors de la construction du réseau et quel poids est attribué à chacun.

La source
Translate

Une autre réflexion me vient à l'esprit concernant le coût de chaque parcours, mais augmenterait le temps et la puissance de traitement nécessaires au calcul.

Exemple:Il y a 3 façons que je peux emprunter (là où je vis) pour aller du point A au point B, selon les GoogleMaps. Les unités Garmin offrent chacun de ces 3 chemins dans leQuickestcalcul d'itinéraire. Après avoir parcouru chacune de ces routes plusieurs fois et avoir fait la moyenne (il y aura évidemment des erreurs en fonction de l'heure de la journée, de la quantité de caféine, etc.), je pense que les algorithmes pourraient prendre en compte le nombre de virages sur la route pour un haut niveau de précision ,par exemple une route droite de 1 mile sera plus rapide qu'une route de 1 mile avec des virages serrés. Ce n'est pas une suggestion pratique, mais certainement une que j'utilise pour améliorer l'ensemble de résultats de mon trajet quotidien.

La source