Entwicklung einer Fahrplanauskunft

[BUG]

Zitat von NamenLozer:

Das, was jfheins gesagt hat, und vielleicht hilft es, wenn du dir bewusst machst, dass Zeit auch eine Dimension ist. Das heißt, eigentlich suchst du eine Route durch eine dreidimensionale (wenn deine Karte zweidimensional ist, wovon ich ausgehe) Punktwolke (die sich als Graph darstellen lässt).

Das Ganze kann man vereinfachen. Die Position der Haltestellen ist eigentlich egal, nur die Zeit (und evtl. der Preis) zwischen den Stationen ist interessant.
Die Zeit würde ich auch als Kopien der Haltestellen modellieren.

Für jeden (diskreten) Zeitpunkt, z.B. in Minutenauflösung, gibt es eine Kopie von jeder Haltestelle. Jede Haltestelle hat eine Kante zu ihrer Kopie im nächsten Zeitschritt (eine Zeiteinheit als Kosten).
Außerdem besitzt sie Kanten zu den nächsten Haltestellen in den Linien zu der jeweils geplanten Ankunftszeit. Die Kanten-Kosten sind die Fahrzeiten.
Um den schnellsten Weg zu finden lassen sich dann klassische Algorithmen anwenden (z.B. Dijstra).

Das sollte eine geeignete Basis für weitere Verbesserungen sein, z.B. Duplizierung aller Haltestellenknoten als Ankunfts- und Abreiseknoten, um Unsteigezeiten zu berücksichtigen.

Auch wenn die oben definierte Graphen theoretisch unendlich sind (angenommen die Zeit endet nicht), kann man praktisch annehmen, das niemand mehr als drei Tage auf einer Strecke fährt und damit die Anzahl der Knoten auf gut handhabbare Größen begrenzen

[Furtbichler]

Nee, das ist ein Minimierungsproblem (shortest Path). Nur das der Graph nicht nur Entfernungen/Preise enthält (und damit Fahrzeiten), sondern auch Wartezeiten.

Ein Weg von A nach B über C mit Umsteigen wird im Graph dann einfach so modelliert.

A=>C1 (Fahrzeit: 5 min)
C1=>C2(Wartezeit: 3 min)
C2=>B (FAhrzeit: 3 min)

vielleicht gibt es auch eine direkte Strecke (A=>B). Die dauert aber, wegen Bauarbeiten, 15min.
A=>B (Fahrzeit: 15min)

Nun kann jeder single-pair shortest-path Algorithmus die optimale Lösung finden. Etwas modifizieren muss man den Algorithmus aber schon, denn die Wartezeit am Punkt 'C' (Übergang C1=>C2) ist nicht notwendigerweise konstant 3 minuten, sondern kann variieren. Vielleicht ist der Anschluss bei Ankunft 15:19 wirklich nur 3 minuten, weil der andere Bus um 15:22 kommt, aber wenn man um 14:19 kommt, dann muss man leider 20min warten, denn der andere Bus kommt leider erst um 14:39.

D.h. die Kostenfunktion 'Zeit(P1,P2)' ist nicht durch eine einfache Matrix dargestellt, sondern berücksichtigt andere Parameter. Mit fällt auf Anhieb ein, das man einfach die Ankunftzeit an C1 als weiteren Parameter nimmt.


Ergo benötigt der Optimierungsalgorithmus ("Finde kürzesten Weg von A->B") neben dem Start- und Endpunkt auch den Zeitpunkt der gewünschten Abfahrt. Sollte sehr einfach umzusetzen sein.

[Namenloser]

Zitat von BUG:

Zitat von NamenLozer:

Das, was jfheins gesagt hat, und vielleicht hilft es, wenn du dir bewusst machst, dass Zeit auch eine Dimension ist. Das heißt, eigentlich suchst du eine Route durch eine dreidimensionale (wenn deine Karte zweidimensional ist, wovon ich ausgehe) Punktwolke (die sich als Graph darstellen lässt).

Das Ganze kann man vereinfachen. Die Position der Haltestellen ist eigentlich egal, nur die Zeit (und evtl. der Preis) zwischen den Stationen ist interessant.

Ja, das ist schon richtig, am Ende hat man natürlich einfach einen Graphen mit Kantengewichten. Ich persönlich finde es bloß anschaulicher, wenn man sich vorstellt, dass man kürzeste Wege auf einer zweidimensionalen Karte berechnet und die Kosten zwischen zwei Knoten der geometrischen Distanz entsprechen. In der Praxis muss natürlich der geometrisch kürzeste Weg nicht der schnellste sein, da man z.B. auf der Autobahn schneller fahren kann als auf irgendeiner Landstraße, aber ich finde, wenn man das Prinzip erst mal verstanden hat, kann man es sehr leicht verallgemeinern...

Edit:

Zitat von BUG:

Auch wenn die oben definierte Graphen theoretisch unendlich sind (angenommen die Zeit endet nicht), kann man praktisch annehmen, das niemand mehr als drei Tage auf einer Strecke fährt und damit die Anzahl der Knoten auf gut handhabbare Größen begrenzen

Das ist eigentlich gar nicht nötig, es reicht ja, wenn die Knoten „virtuell“ vorhanden sind. Dijkstra guckt sich ja immer nur die unmittelbar adjazenten Knoten an. Man kann diese also generieren, während man den Algorithmus ausführt...

Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.

[Furtbichler]

Zitat von NamenLozer:

Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.

Nö. Dann gibt es einfach keine Lösung.

Bei der Graphentraversierung markiert man die besuchten Knoten, dann passiert das nicht.

[Namenloser]

Zitat von Furtbichler:

Zitat von NamenLozer:

Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.

Nö. Dann gibt es einfach keine Lösung.

Man will aber trotzdem nicht, dass das ganze System abschmiert, bloß weil der User eine Route berechnen will, die nicht existiert.

Zitat von Furtbichler:

Bei der Graphentraversierung markiert man die besuchten Knoten, dann passiert das nicht.

Hier ist der Graph aber unendlich und man findet (in zeitlicher Dimension) an jedem Knoten einen weiteren Knoten, der nicht zum Ziel führt.

Jedes Stehen eines Busses an einer Haltestelle ist eigentlich ein Knoten. Man kann sich dann an jedem Knoten jeweils dafür entscheiden, ob man mit dem Bus zur nächsten Haltestelle (1. adjazenter Knoten) fährt, oder ob man auf den nächsten Bus wartet (2. adjazenter Knoten). Nun kann man aber beliebig lange an der Haltestelle stehen und darauf warten, dass ein Bus kommt, der einen in Richtung des Ziels bringt. Wenn ein solcher aber niemals kommt, dann sitzt man bei einer naiven Implementierung in einer Endlosschleife...

[Furtbichler]

Zitat von NamenLozer:

Hier ist der Graph aber unendlich und man findet (in zeitlicher Dimension) an jedem Knoten einen weiteren Knoten, der nicht zum Ziel führt.

Hmmm..... Nein.

Der Graph enthält alle Bus/Bahnlinien. Die Kosten einer Fahrt sind je Kante konstant (wenn man Baustellen, Staus etc. mal ignoriert). Die Wartezeiten an den Knoten beim Umsteigen sind abhängig von der Ankunftszeit, die jedoch beim Traversieren des Knotens bekannt ist, denn man sucht ja immer den kürzesten Weg bei Abfahrt zu einem bestimmten Zeitpunkt.

Wenn mann also z.B. am Zentralbahnhof umsteigen will, dann gibt es immer genau eine nächste Verbindung zu einem Ort X (ICE und Bummelzug sind zwei unterschiedliche Verbindungen!). Die übernächste ist irrelevant, denn dann ist man garantiert länger unterwegs. Deswegen kann man (zumindest bei der Bahn) auch angeben, wie lange man mindestens am Umsteigebahnhof warten will. Denn dann wird ggf. nicht die nächste Verbindung genommen, sondern die Übernächste.

Der Graph also endlich, aber die Kantengewichtung unvollständig und wird erst während des Suchvorganges dynamisch ermittelt. Eine Fahrtzeit kann zum Zeitpunkt X 10 Minuten sein, aber zum Zeitpunkt Y (Berufsverkehr) auch 50 Minuten. Die Wartezeit kann mal 5, mal 10 Minuten sein (gleiches Ziel). Das ist aber kein Showstopper.

Zitat von evilboy:

Fahrpläne mit konkreten Uhrzeiten lassen wir mal außen vor

Würde ich nicht machen, denn deine Lösung ist dann eine ganz andere.

Implementiere einen Optimierungsalgorithmus deiner Wahl (Djikstra wurde bereits genannt) und modelliere dabei Haltestellen und Umsteigeaktionen als einzelne Knoten. Die Verbindungen zwischen den Knoten sind Fahrt- bzw. Umsteigezeiten. Für beides schreibst Du jeweils eine Funktion

Delphi-Quellcode:

Function FahrtZeit (Von, Bis : TKnoten, Ankunftszeit : TDateTime) : Integer;
Function WarteZeit (Von, Bis : TKnoten, Ankunftszeit : TDateTime) : Integer;

[BUG]

Zitat von Furtbichler:

Der Graph also endlich, aber die Kantengewichtung unvollständig und wird erst während des Suchvorganges dynamisch ermittelt. Eine Fahrtzeit kann zum Zeitpunkt X 10 Minuten sein, aber zum Zeitpunkt Y (Berufsverkehr) auch 50 Minuten. Die Wartezeit kann mal 5, mal 10 Minuten sein (gleiches Ziel).

Jetzt habe ich es verstanden, schöne Idee
Man müsste nochmal genau am Algorithmus nachvollziehen, ob es da keine Probleme gibt. Da die Gesamtfahrzeit nie größer werden kann, wenn man früher als über einen anderen Weg zu einem Knoten kommt, könnte es mit Dijkstra klappen. Das passt ja ziemlich gut zu den Invarianten.

[Namenloser]

Zitat von Furtbichler:

Wenn mann also z.B. am Zentralbahnhof umsteigen will, dann gibt es immer genau eine nächste Verbindung zu einem Ort X (ICE und Bummelzug sind zwei unterschiedliche Verbindungen!). Die übernächste ist irrelevant, denn dann ist man garantiert länger unterwegs.

Hmm, aber es könnte doch sein, dass zuerst ein Zug kommt, der zwar in die richtige Richtung fährt, aber zwischendurch an zig Haltestellen hält („Bummelzug“), und 10 Minuten später eine wesentlich schnellere Direktverbindung kommt, mit der man schneller ankommt, obwohl man vorher länger gewartet hat. Hab jetzt nicht ganz verstanden, wie das bei dir berücksichtigt wird...

Vielleicht wolltest du darauf hinaus, dass man nur so lange wartet, bis man alle Linien, die überhaupt über die aktuellen Haltestelle fahren, einmal durch hat? Das wäre dann im Falle von Zug- oder Busverbindungen auch mein Ansatz gewesen, um das Problem zu lösen. Aber da ich nicht wusste, ob es evilboy wirklich um Zug-/Busfahrpläne geht oder ob er das Szenario nur zur Veranschaulichung gewählt hat, wollte ich es erst mal möglichst allgemein lassen. Hätte ja z.B. sei können, dass der „Fahrplan“ nicht konstant ist...

Er wollte ja auch nur einen Denkanstoß; mir fallen zu Zug-/Bahnrouten noch einige andere Details ein... z.B. sollte jede Haltestelle nur einmal in einer Route vorkommen, weil es sonst sein könnte, dass eine Route ausgegeben wird, bei der man irgendwo einmal im Kreis fährt, weil das genau so lange dauert, wie wenn man an der Haltestelle gewartet hätte...

Wie BUG schon schrieb:

Zitat von BUG:

Ich glaube, alles Prinzipielle zu in dieser Modellierung wurde mittlerweile genannt und wir fangen jetzt an, uns im Kreis zu drehen und über Details/Optimierungen zu streiten

[Furtbichler]

Zitat von NamenLozer:

Hmm, aber es könnte doch sein, dass zuerst ein Zug kommt, der zwar in die richtige Richtung fährt, aber zwischendurch an zig Haltestellen hält („Bummelzug“),

Das ist eine Verbindung. Der gleiche Bummelzug später wird ignoriert. Ein anderer Zug in die gleiche Richtung ist eine andere Verbindung => berücksichtigen.

Zitat:

sollte jede Haltestelle nur einmal in einer Route vorkommen, weil es sonst sein könnte, dass eine Route ausgegeben wird, bei der man irgendwo einmal im Kreis fährt, weil das genau so lange dauert, wie wenn man an der Haltestelle gewartet hätte...

Dafür sind die Algorithmen gedacht. Die sorgen schon dafür, dass das nicht passiert. Die besuchten Knoten werden nicht noch einmal besucht.

Ausnahme: Eine Kantengewichtung ist negativ, wenn man z.B. mit einem Warp-Antrieb fährt, vergeht die Zeit rückwärts. Dann würde der Djikstra-Algorithmus passen. Wenn man also Busse hat, die ankommen, bevor sie abgefahren sind, muss man den Bellman-Ford Algorithmus verwenden.

Du hast noch nicht verstanden, wie diese shortest-path Algorithmen funktionieren.

Aber wenn 'Die Bahn' so einen Algorithmus umgesetzt hat, *kann* es nicht schwer sein.

[BUG]

Zitat von NamenLozer:

Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.

Stimmt, das könnte man vorher einfach prüfen (oder evtl. sogar vor berechnet haben).
Wenn man eventuell über den Basis-Dijstra hinaus will, wäre es schon schön, wenn der Graph endlich ist Aber für so kleine Probleme sollte wohl nicht nötig sein.

Ich glaube, alles Prinzipielle zu in dieser Modellierung wurde mittlerweile genannt und wir fangen jetzt an, uns im Kreis zu drehen und über Details/Optimierungen zu streiten
@evilboy: Hast du den Ansatz verstanden oder hast du Fragen?

EDIT:

Zitat von evilboy:

Fahrpläne mit konkreten Uhrzeiten lassen wir mal außen vor

Der Fall ist einfacher zu modellieren, bringt dem Fahrgast aber nicht wirklich viel, wenn der er zwar die kürzeste Fahrzeit hat, aber zwischen-drin einen halben Tag warten muss