Pfadfindungsalgorithmen (Routenplanung, Reiseplanung, ...) auf Graphen mit Zeitbeschränkungen

Question

Ich habe eine Datenbank mit Haltestellen von Bussen/Zügen/... und den Ankunfts-/Abfahrtszeiten an jedem Datum usw. Ich suche nach einer Möglichkeit, die schnellste (kürzeste/günstigste/geringste Übergänge) Fahrt zwischen zwei Orten zu suchen. Ich möchte in Zukunft beliebige Orte haben und OpenStreetMap-Daten verwenden, um zwischen den Haltestellen und von den Haltestellen zum Start/Ende zu laufen, aber im Moment möchte ich nur den Weg zwischen zwei Haltestellen in der Datenbank finden.

Das Problem ist, dass ich nicht viele Informationen zu diesem Thema finden kann, zum Beispiel diese Wikipedia-Seite enthält eine Menge Text, der absolut keine nützlichen Informationen enthält.

Was ich herausgefunden habe, ist die GTFS Format, verwendet in Google Transit . Meine Stadt bietet zwar keinen öffentlichen Datenfeed an (nicht einmal einen privaten), aber ich verfüge bereits über alle wichtigen Informationen, die das GTFS enthält, und eine Umwandlung wäre trivial.

Es gibt einige GTFS-basierte Software, wie z.B. OpenTripPlanner die auch Fußgänger-, Auto- und Fahrradrouten erstellen können, indem sie OpenStreetMap .

Allerdings Der Routing-Code ist nicht gut dokumentiert (zumindest nach dem, was ich gefunden habe), und ich brauche nicht das ganze Ding.

Alles, was ich suche, ist ein guter Überblick über die Algorithmen, die ich verwenden könnte, ihre Leistung, vielleicht einige Pseudocode.

Also, die Frage ist Wie kann ich mit einer Liste von Haltestellen, Routen und Ankunfts-/Abfahrts-/Fahrtzeiten den schnellsten Weg von Haltestelle A zu Haltestelle B finden?

Answer 1

1. Modellieren Sie Ihr Problem als Grafik . Jede Station wird ein Vertex sein, und jeder Bus/Zug wird eine Kante sein.
2. eine Funktion erstellen w:Edges->R der die Zeit/Geld/... für jede Kante angibt.
3. Sie haben nun ein typisches Minimalwegproblem, das wie folgt gelöst werden kann Dijkstra-Algorithmus die von einer gegebenen Quelle aus den kürzesten Weg zu allen Knotenpunkten findet.

(*) Bei den "geringsten Übergängen" beträgt die Gewichtung für jede Kante 1, so dass Sie diese sogar optimieren können, indem Sie eine BFS oder sogar bi-direktional BFS anstelle von Dijkstra, wie ich in diesem Artikel erklärt habe Beitrag [Es wird für die soziale Distanz erklärt, aber es ist eigentlich derselbe Algorithmus].

---

EDIT
als Bearbeitung der nicht statischen Natur des Graphen [für das Timing], die Sie in den Kommentaren erwähnt haben [für den Preis und die Anzahl der Übergänge gilt immer noch, was ich oben erwähnt habe, da diese Graphen statisch sind], können Sie eine Distanz-Vektor-Routing-Algorithmus die eigentlich für dynamische Graphen gedacht ist und eine verteilte Variante von Bellman-Ford-Algorithmus .
Die Idee des Algorithmus:

• In regelmäßigen Abständen sendet jeder Knoten seinen "Entfernungsvektor" an seine Nachbarn [der Vektor gibt an, wie viel es "kostet", vom sendenden Knotenpunkt zu jedem anderen Knotenpunkt zu reisen.
• Seine Nachbarn versuchen, ihre Routing-Tabellen zu aktualisieren [über welche Kante ist es am besten, sich zum jeweiligen Ziel zu bewegen].
• In Ihrem Fall weiß jeder Knoten, was der schnellste Weg zu seinen Nachbarn ist [Reisezeit + Wartezeit], und er [der Knoten/Bahnhof] addiert diese Zahl zu jedem Eintrag im Entfernungsvektor, um zu wissen, wie und wie viel Zeit er braucht, um zum Ziel zu gelangen. Wenn ein Bus abfährt, sollte die Reisezeit für alle Knoten [von dieser Quelle] neu berechnet werden, und der neue Vektor sollte an seine Nachbarn gesendet werden