Öffentliche Verkehrsmittel mit Bussen in der Stadt

Question

Ich entwickle eine Journey Planner Website. Es gibt nur wenige Dinge, die in diesem Fall derzeit einfach sind. Im Moment wird die Webseite nur in der Lage sein, Busrouten zu planen, die Zeiten von Bussen sind derzeit nicht verfügbar. Das bedeutet, dass wir nur Busrouten in der DB gespeichert haben und da Bus-Timings nicht verfügbar sind, sind Wartezeiten für Reisende nicht relevant. Was verfügbar ist, ist die Zeit und die Entfernung zwischen zwei Haltestellen für einen einzelnen Bus.

Ich denke, dass die Verwendung eines ungerichteten gewichteten Graphen, der die Zeit- und Entfernungskosten jeder Bushaltestelle für jeden einzelnen Bus speichert, der Weg zu gehen wäre. Dann könnte ich den Dijkstra-Algorithmus verwenden, um den kürzesten Pfad zwischen zwei Orten zu berechnen, die vom Benutzer auf der Grundlage der Zeit oder der Entfernung je nach Benutzerpräferenz eingegeben wurden. Ich würde herausfinden, ob zwei oder drei Busse durch einfache C# -Funktionen erforderlich sind, wenn sich die Buslinien an den Haltestellen kreuzen und dann diese Kreuzungshaltestellen verwenden, damit der Reisende den Bus wechseln kann. Aber es würde für jeden Bus eine individuelle Grafik geben. Eine Alternative (nicht sicher, ob dies korrekt ist) wäre, ein Diagramm zu verwenden, das jede Bushaltestelle der Stadt als Knoten enthält, und dann diese Technik zu verwenden, um den Weg zwischen zwei Haltestellen zu finden. Welcher ist der richtige Ansatz? Soll ich anstelle von Dijkstra algo den A * -Algorithmus verwenden?

Ein paar allgemeine Punkte für das Design: Ich möchte die App erweiterbar sein, so dass ich andere Transportmittel später hinzufügen kann, wenn die Notwendigkeit entsteht. Darüber hinaus könnten die Buszeiten auch später hinzugefügt werden, wenn dies ohne größere Änderungen auf der Website möglich ist. Ich habe hier einige Experten gesehen, die an sehr komplexen Transportprojekten gearbeitet haben. Also bitte helfen Sie mir mit der besten Möglichkeit, diese Funktionalität auf die skalierbarste, modulare und erweiterbare Art und Weise zu implementieren.

Answer 1

Ein Graph muss ein gerader Graph sein - Bushaltestellen auf gegenüberliegenden Straßenseiten (sogar in einem Land wie Großbritannien, das selten Mediane hat) sind NICHT der selbe Stopp!

Answer 2

Ich denke, die wichtigste Optimierung ist das Trennen von Stationen, wo Sie Routen und Stationen ändern können, wo Sie nicht können. Dann müssen Sie nur Stationen berücksichtigen, bei denen Sie die Route als Zwischenstationen in Ihrem Diagramm ändern können. Dies sollte die Grafik so klein machen, dass Dijkstra in Ordnung ist.

Ich unterscheide Knoten mit nur zwei Kanten, indem ich sie einfach aus dem Diagramm herausschneide und stattdessen ihre beiden Nachbarn mit einer Kante der hinzugefügten Länge verbinde. Dann gehe ich auf diesem reduzierten Graphen, der viel schneller sein sollte. d. h. nur Stationen in Betracht ziehen, bei denen Routen gewechselt werden könnten.

Answer 3

Ich habe im letzten Sommer eine ähnliche Anwendung gestartet und nie beendet, aber ich habe ein paar Tipps zu diesem Diagramm und zur Strukturierung Ihrer Daten.

Mein Plan war es, jeden Stopp als Knoten zu haben, und einen Pfad zwischen jedem dieser Knoten für jedes Mal, wenn ein Bus durchging. Zum Beispiel, wenn ein Bus jede halbe Stunde über einen Zeitraum von 6 Stunden angehalten hat, dann würde es 12 Wege zwischen den zwei Knoten geben. Die Zeit war der Haupttreiber hinter den "Kosten" des Pfades, so dass normalerweise der kürzeste Pfad gewählt wurde.

Vor dem Start der Anwendung würde die Datenbank für alle Pfade in den nächsten 5 Stunden abfragen (entsprechend anpassen). Es würde dann mit Dijkstra-Algorithmus knirschen.

Andere Dinge in den Kosten sind die tatsächlichen Geld Kosten der Route, Transfers (und ihre Kosten) Faktor, ohne Dächer stoppt (wenn Sie neigen dazu, schlechte Wetter haben) usw.

Dieser Plan funktionierte gut für mich. Ich lebe in einem Gebiet mit 3 Bussystemen.

Schließlich kann es Ihnen gut tun, Ihre Daten auf ähnliche Weise wie die Google Transit Feed Specification zu strukturieren, da viele Agenturen diese Art von Daten erzeugen, die Sie importieren könnten.

Answer 4

Vielleicht können Sie einige Paddydubs arbeiten für TransportDublin gefunden on github.

Answer 5

Ich habe einen solchen Algorithmus für eine Testanwendung codiert. Ich hatte für jeden Stopp ein Wörterbuch als Quelle und als Ziel. Der Algorithmus war rekursiv. Jeder Schritt der Rekursion war wie folgt: Bei gegebener Quelle und Ziel würde es eine Liste von Routen erzeugen, die ins Ziel gehen, eine Liste von Routen, die die Quelle verlassen. Wenn es gemeinsame Stopps gab, waren wir fertig, wir melden die Route. Wenn nicht, erzeuge ich benachbarte Stopps für die Quelle und rekursiere. Die nächste Rekursion erzeugt eine Liste von benachbarten Stopps für Sink, Recurse. Vor der Rekursion habe ich natürlich den vorherigen Pfad aufgezeichnet, und am Ende hätte ich eine Liste.

Ich erinnere mich, dass ich einige Cutoff-Bedingungen setzen musste, weil die Rekursion manchmal in bestimmten "schlechten" Regionen stecken bleiben würde.

Ich sah auch in diesem Papier:

www.citeulike.org/user/rchauhan/article/819528

Ich bin interessiert, wenn Sie dieses Problem auf eine andere Weise zu lösen geführt.