[PHP] Djikstra & öffentlicher Nahverkehr

[loads]

Hallo Leute,

ich steh im moment noch etwas auf dem Schlauch bezüglich dieses Problems:

Ich bin im moment dabei eine elektronische Fahrplanabfrage zu programmieren. Diese soll nach Start-/Zieleingabe des Users die zeitmäßig schnellste Verbindung ausgeben. (so wie man es halt kennt von DB und co..)

Für die Berechnung kürzester Wege eignet sich ja der Dijkstra-Algorithmus gut (das Netz in dem abgefragt werden soll ist relativ klein..also keine Performance-Probleme).
Ich war bisher auch erfolgreich im Test mit einer PHP-Klasse des Algorithmus.

Den Sprung ins Liniensystem habe ich aber bisher noch nicht geschafft:

Bei Kanten und Knoten ist das ganze ja kein Problem, man kann an jeder ecke beliebig "abbiegen"
bei einer Linie ist das nicht der Fall, es gibt vorgeschriebene Wege. Man müsste also mindestens Umsteigen. Hierbei sind aber meistens Wartezeiten einzuplanen. Die effektive Fahrzeit könnte ich also locker berechnen. Die Gesamt-"Reise"-Zeit aber nicht so leicht, da es auch andere, schnellere Verbindung mit weniger Wartezeit geben könnte.

Nun: Ist es effektiver die Verbindungen nach Fahrzeit zu berechnen und danach an den Umsteigepunkten die Wartezeiten zu ermitteln und ggf (irgendwie) andere Verbindungen zu ermitteln?
Oder hat jemand eine Idee wie von vorneherein parallel fahren kann...?

Bin dankbar über jede Antwort mit irgendwelchen Ideen (hat ja eher mit logischem Denken als Programmieren direkt zutun..)

 

[theHacker]

Du müsstet die Wartezeit quasi an den Knoten notieren. Dürfte kein Problem sein, Dijkstra ein wenig zu modifizieren, dass du zusätzlich zu den Kanten-Kosten noch die Kosten des Zielknotens addierst.


Mit dem Umsteigen hätte ich spontan die Idee, dass du von anfang an versuchst, den Graphen drastisch zu optimieren.

Ich nehm jetzt mal ein aktuelles Beispiel bei mir in der Nähe (Streckennetz, interessanter Part in etwa WSW):
Ich will vom Hohenecker Weg an die Rothenburger Straße.

Mögliche Wege:

• 67: Hohenecker Weg => Röthenbach
• U2: Röthenbach => Rothenburger Stra0e

• 67: Hohenecker Weg => Fürth Süd
• 70/71/72/113: Fürth Süd => Gustav-Adolf-Straße
• U3: Gustav-Adolf-Straße => Rothenburger Stra0e

Interessant hierbei:
Wichtig sind nur die Knoten "Fürth Süd", "Röthenbach" und "Gustav-Adolf-Straße".

An einer Haltestelle ohne Anschluss würd ich gar keinen Knoten einrichten (außer, es ist der Startknoten oder der Zielknoten), sondern bis zu einem möglichen Umsteigepunkt alles zusammenfassen.

 

[TriloByte]

Der Hauptknackpunkt ist wahrscheinlich, dass Fahrzeiten also Wegkosten bereits vorher bekannt sind und sich wahrscheinlich auch nicht ändern (sofern keine erhöhten Verkehrsaufkommen zu bestimmten Tasgeszeiten, Staus etc. berücksichtigt werden sollen - aber selbst dann müßte der Graph eigentlich nur mit den aktuellen Werten neu initialisiert werden). Mit diesen Werten kann der Graph also initialisiert werden.

Umsteigezeiten sind hingegen von konkreten Zeiten/Fahrplänen abhängig und je nach Konstellation sehr verschieden. Diese Information muss entweder zur Laufzeit oder zuvor bestimmt werden, indem an jedem Knoten zu jedem Zeitpunkt alle möglichen Kombinationen von Umsteigemöglichkeiten zwischen je zwei Linen berechnet und als Zusatzinfos an den jeweiligen Knoten gehängt werden. Die korrekten WartezeitKosten müssen dann auf die entsprechenden Kosten der ausgehenden Strecke aufaddiert werden.

Sind jetzt nur meine spontanen Gedanken zu dem Thema, hab sowas noch nicht gemacht.

 

[burnred]

Beim Verkehrsverbund hier ist das ganze von der durchschnittlichen Gehgeschwindigkeit und dem Abstand der Haltestellen abhängig zwischen denen man umsteigt. Abhängig davon wird dann errechnet welche der möglichen Umsteigemöglichkeiten die günstigste ist. Es wird da immer die Gesamtzeit bestimmt und das kann man sich dann entweder nach den Kriterien am wenigsten Umsteigen, kürzeste Zeit oder kürzeste Strecke anzeigen lassen.

 

[loads]

ich hab heute mal noch ein bisschen nachgedacht und mir folgendes überlegt:
Man könnte doch einfach an einem Knoten zweier Linien eine Haltestelle durch zwei Knoten repräsentieren.
Also Knoten 1 durch den Linie 1 führt
Knoten 2 durch den Linie 2 führt

die Kante, die die Knoten verbindet hat das Gewicht der Umsteigezeit, die man zur Laufzeit ausliest (da ja bestimmt werden muss, wie viel Uhr es an diesem Zeitpunkt wäre)
Nun gliedert sich der 2. Knoten in die Priority Queue ein und wird natürlich entsprechend früh oder spät mit berücksichtigt.

Jetzt nur noch die Frage ob das ganze nicht zu kompliziert ist