Kartenrouting, a la Google Maps?

Question

Ich war schon immer von Map Routing fasziniert, habe aber noch nie gute Tutorials für Einsteiger (oder sogar für Fortgeschrittene!) dazu gefunden.Hat jemand Hinweise, Hinweise usw.?

Aktualisieren: Ich suche hauptsächlich nach Hinweisen, wie ein Kartensystem implementiert ist (Datenstrukturen, Algorithmen usw.).

Answer 1

Werfen Sie einen Blick auf die Offenes Straßenkartenprojekt um zu sehen, wie so etwas in einem wirklich freien Softwareprojekt angegangen wird, bei dem nur vom Benutzer bereitgestellte und lizenzierte Daten verwendet werden, und eine Wiki, das Dinge enthält, die Sie vielleicht interessant finden.

Vor ein paar Jahren waren die beteiligten Jungs ziemlich locker und haben mir viele meiner Fragen beantwortet, sodass ich keinen Grund sehe, warum sie immer noch kein netter Haufen sind.

Answer 2

Barry Brumitt, einer der Ingenieure der Routenfindungsfunktion von Google Maps, hat einen Beitrag zu diesem Thema geschrieben, der von Interesse sein könnte:

Der Weg zu einer besseren Wegfindung06.11.2007 15:47:00 Uhr

Answer 3

A* kommt den Produktions-Mapping-Algorithmen tatsächlich viel näher.Im Vergleich zum ursprünglichen Algorithmus von Dijikstra ist deutlich weniger Aufwand erforderlich.

Answer 4

Mit Kartenrouting meinen Sie die Suche nach dem kürzesten Weg entlang eines Straßennetzes?

Der Dijkstra-Kürzeste-Weg-Algorithmus ist der bekannteste.Wikipedia hat kein schlechtes Intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Hier gibt es ein Java-Applet, in dem Sie es in Aktion sehen können: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html und Google führen Sie zu Quellcode in nahezu jeder Sprache.

Jede reale Implementierung zur Generierung von Fahrrouten wird eine ganze Menge Daten über das Straßennetz umfassen, die die Kosten beschreiben, die mit dem Überqueren von Verbindungen und Knoten verbunden sind – Straßennetzhierarchie, Durchschnittsgeschwindigkeit, Kreuzungspriorität, Ampelverknüpfung, Abbiegeverbote usw.

Answer 5

Anstatt APIs für jeden Kartendienstanbieter zu lernen (wie Gmaps, Ymaps API), ist es gut zu lernen Kartentraktion

„Mapstraction ist eine Bibliothek, die eine gemeinsame API für verschiedene Javascript-Mapping-APIs bereitstellt.“

Ich würde vorschlagen, dass Sie zur URL gehen und sich mit einer allgemeinen API vertraut machen.Es gibt auch eine Menge Anleitungen.

Answer 6

Ich habe noch kein gutes Tutorial zum Thema Routing gefunden, aber es gibt jede Menge Code zu lesen:

Es gibt GPL-Routing-Anwendungen, die Openstreetmap-Daten verwenden, z.B. Gosmore was unter Windows (+ Mobilgeräten) und Linux funktioniert.Es gibt eine Reihe interessanter Anwendungen, die dieselben Daten verwenden, aber Gosmore bietet einige coole Einsatzmöglichkeiten z.B.Schnittstelle zu Websites.

Das größte Problem beim Routing sind schlechte Daten, und man erhält nie ausreichend gute Daten.Wenn Sie es also ausprobieren möchten, halten Sie Ihren Test sehr lokal, damit Sie die Daten besser kontrollieren können.

Answer 7

Aus konzeptioneller Sicht stellen Sie sich vor, Sie werfen einen Stein in einen Teich und beobachten die Wellen.Die Routen würden den Teich und den Stein als Ihre Ausgangsposition darstellen.

Natürlich müsste der Algorithmus mit zunehmender Entfernung n einen gewissen Anteil von n^2 Pfaden durchsuchen.Sie würden Ihre Ausgangsposition einnehmen und von diesem Punkt aus alle verfügbaren Pfade überprüfen.Rufen Sie dann rekursiv die Punkte am Ende dieser Pfade usw. auf.

Sie können die Leistung steigern, indem Sie auf einem Pfad nicht doppelt zurückfahren, indem Sie die Routen nicht erneut an einem Punkt überprüfen, wenn dieser bereits zurückgelegt wurde, und indem Sie Pfade aufgeben, die zu lange dauern.

Eine alternative Möglichkeit besteht darin, den Ameisenpheromon-Ansatz zu verwenden, bei dem Ameisen willkürlich von einem Startpunkt aus kriechen und eine Duftspur hinterlassen, die sich umso mehr aufbaut, je mehr Ameisen einen bestimmten Weg überqueren.Wenn Sie (genügend) Ameisen sowohl vom Startpunkt als auch vom Endpunkt aus schicken, ist der Weg mit dem stärksten Geruch letztendlich der kürzeste.Dies liegt daran, dass der kürzeste Weg in einem bestimmten Zeitraum häufiger besucht wurde, vorausgesetzt, die Ameisen gehen in einem gleichmäßigen Tempo.

BEARBEITEN @ Spikie

Als weitere Erläuterung zur Implementierung des Teichalgorithmus werden potenziell benötigte Datenstrukturen hervorgehoben:

Sie müssen die Karte als Netzwerk speichern.Dies ist einfach eine Reihe von nodes Und edges zwischen ihnen.Eine Menge von nodes bilden ein route.Eine Kante verbindet zwei Knoten (möglicherweise beide denselben Knoten) und hat einen zugehörigen Knoten cost wie zum Beispiel distance oder time den Rand überqueren.Eine Kante kann entweder bidirektional oder unidirektional sein.Wahrscheinlich ist es am einfachsten, nur unidirektionale zu haben und diese für eine bidirektionale Fahrt zwischen Knoten zu verdoppeln (d. h.eine Kante von A nach B und eine andere für B nach A).

Stellen Sie sich zum Beispiel drei Bahnhöfe vor, die in einem gleichseitigen, nach oben gerichteten Dreieck angeordnet sind.Darüber hinaus gibt es jeweils auf halber Strecke drei weitere Stationen.Kanten verbinden alle benachbarten Stationen miteinander. Das endgültige Diagramm weist ein umgekehrtes Dreieck auf, das innerhalb des größeren Dreiecks sitzt.

Beschriften Sie Knoten von links unten über links nach rechts und oben mit A, B, C, D, E, F (oben F).

Gehen Sie davon aus, dass die Kanten in beide Richtungen durchlaufen werden können.Jede Kante kostet 1 km.

Ok, wir möchten also von unten links A zur Bergstation F führen.Es gibt viele mögliche Routen, auch solche, die auf sich selbst zurückgreifen, z.B.ABCEBDEF.

Wir haben eine Routine zu sagen: NextNode, das akzeptiert a node und ein cost und ruft sich selbst für jeden Knoten auf, zu dem es reisen kann.

Wenn wir diese Routine laufen lassen, wird sie natürlich irgendwann alle Routen entdecken, auch solche, die potenziell unendlich lang sind (z. B. ABABABAB usw.).Wir verhindern, dass dies geschieht, indem wir mit dem vergleichen cost.Immer wenn wir einen Knoten besuchen, der noch nie zuvor besucht wurde, vergleichen wir sowohl die Kosten als auch den Knoten, von dem wir kamen, mit diesem Knoten.Wenn ein Knoten zuvor besucht wurde, vergleichen wir ihn mit den bestehenden Kosten und wenn wir günstiger sind, aktualisieren wir den Knoten und fahren fort (rekursiv).Wenn wir teurer sind, überspringen wir den Knoten.Wenn alle Knoten übersprungen werden, verlassen wir die Routine.

Wenn wir unseren Zielknoten erreichen, verlassen wir auch die Routine.

Auf diese Weise werden alle realisierbaren Routen überprüft, aber entscheidend sind nur die mit den geringsten Kosten.Am Ende des Prozesses wird jeder Knoten die niedrigsten Kosten haben, um zu diesem Knoten zu gelangen, einschließlich unseres Zielknotens.

Um die Route zu erhalten, arbeiten wir von unserem Zielknoten aus rückwärts.Da wir den Knoten, von dem wir kamen, zusammen mit den Kosten gespeichert haben, können wir beim Aufbau der Route einfach rückwärts springen.Für unser Beispiel würden wir am Ende so etwas erhalten:

Knoten A – (Gesamt-)Kosten 0 – Von Knoten Keine
Knoten B – Kosten 1 – Von Knoten A
Knoten C – Kosten 2 – Von Knoten B
Knoten D – Kosten 1 – Von Knoten A
Knoten E – Kosten 2 – Von Knoten D / Kosten 2 – Von Knoten B (dies ist eine Ausnahme, da die Kosten gleich sind)
Knoten F – Kosten 2 – Von Knoten D

Der kürzeste Weg ist also ADF.

Answer 8

Aus meiner Erfahrung in diesem Bereich geht hervor, dass A* seine Arbeit sehr gut erledigt.Er ist (wie oben erwähnt) schneller als der Dijkstra-Algorithmus, aber dennoch einfach genug, dass ein normal kompetenter Programmierer ihn implementieren und verstehen kann.

Der Aufbau des Streckennetzes ist der schwierigste Teil, der jedoch in eine Reihe einfacher Schritte unterteilt werden kann:Holen Sie sich alle Straßen;Ordnen Sie die Punkte in der richtigen Reihenfolge.Machen Sie Gruppen identischer Punkte auf verschiedenen Straßen zu Kreuzungen (Knoten);Fügen Sie Bögen in beide Richtungen hinzu, an denen sich Knoten verbinden (oder nur in eine Richtung für eine Einbahnstraße).

Der A*-Algorithmus selbst ist gut dokumentiert auf Wikipedia.Der entscheidende Punkt für die Optimierung ist die Auswahl des besten Knotens aus der offenen Liste, für den Sie eine Hochleistungs-Prioritätswarteschlange benötigen.Wenn Sie C++ verwenden, können Sie den STL-Priority_queue-Adapter verwenden.

Es ist recht einfach, den Algorithmus so anzupassen, dass die Route über verschiedene Teile des Netzwerks (z. B. Fußgänger, Auto, öffentliche Verkehrsmittel usw.) geleitet wird, um Geschwindigkeit, Entfernung oder andere Kriterien zu bevorzugen.Dies erreichen Sie, indem Sie beim Aufbau des Netzwerks Filter schreiben, um zu steuern, welche Routensegmente verfügbar sind und welche Gewichtung jedem einzelnen zugewiesen wird.

Answer 9

Ein anderer Gedanke kommt mir in Bezug auf die Kosten jeder Durchquerung in den Sinn, würde aber die für die Berechnung erforderliche Zeit und Rechenleistung erhöhen.

Beispiel: Laut GoogleMaps gibt es drei Möglichkeiten, wie ich (wo ich wohne) von Punkt A nach B gelangen kann.Garmin-Geräte bieten jeden dieser 3 Pfade im an Quickest Routenberechnung.Nachdem ich jede dieser Routen viele Male zurückgelegt habe und den Durchschnitt ermittelt habe (natürlich gibt es je nach Tageszeit, Koffeinmenge usw. Fehler), bin ich der Meinung, dass die Algorithmen die Anzahl der Kurven auf der Straße berücksichtigen könnten, um ein hohes Maß an Genauigkeit zu erzielen , z.B. Eine gerade Straße von 1 Meile Länge ist schneller als eine 1 Meile lange Straße mit scharfen Kurven.Kein praktischer Vorschlag, aber sicherlich einer, den ich verwende, um die Ergebnisse meines täglichen Pendelverkehrs zu verbessern.