Entwicklung einer Fahrplanauskunft

[evilboy]

Zitat:

Zitat von BUG (Beitrag 1223450)

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 :wink:
@evilboy: Hast du den Ansatz verstanden oder hast du Fragen?

Ja, erst mal vielen Dank an alle für die hilfreichen Infos!
Ich mach mich jetzt mal dran, das Liniennetz umzusetzen :) Und ja, es gibt keine isolierten Linien, so dass man von jeder Haltestelle zu jeder Haltestelle kommt und das Problem schon mal nicht auftritt…

Zitat:

Zitat von BUG (Beitrag 1223450)

EDIT:

Zitat:

Zitat von evilboy (Beitrag 1223400)

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 :mrgreen:

Klar, das Ganze sollte erst mal nur ein Anschauungsmodell werden :)
Es gibt Apps wie Tube 2 für Windows Mobile (ja, das alte Windows Mobile), die genau so funktioniert haben und mangels echtem Fahrplan immer einen Pauschalwert für Umstiege (5-10 Minuten) veranschlagt haben…

[Furtbichler]

Zitat:

Zitat von NamenLozer (Beitrag 1223445)

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:

Zitat von evilboy (Beitrag 1223451)

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:

Zitat von Furtbichler (Beitrag 1223463)

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 :thumb:
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:

Zitat von Furtbichler (Beitrag 1223463)

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:

Zitat von BUG (Beitrag 1223450)

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 :wink:

[Furtbichler]

Zitat:

Zitat von NamenLozer (Beitrag 1223577)

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.

[Namenloser]

Zitat:

Zitat von Furtbichler (Beitrag 1223589)

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.

Ich weiß schon wie der Dijkstra-Algorithmus funktioniert, ich habe vor einer Woche noch eine Klausur unter anderem darüber (und über Bellman-Ford auch) geschrieben. ;)

Nur ist Haltestelle hier ja nicht das gleiche wie Knoten. Zu jeder Haltestelle gibt es mehrere Knoten wegen der Zeit-Dimension...

[Furtbichler]

Zitat:

Zitat von NamenLozer (Beitrag 1223594)

Ich weiß schon wie der Dijkstra-Algorithmus funktioniert, ich habe vor einer Woche noch eine Klausur unter anderem darüber (und über Bellman-Ford auch) geschrieben. ;)

Dann weißt Du ja mehr als ich :oops:

Zitat:

Nur ist Haltestelle hier ja nicht das gleiche wie Knoten. Zu jeder Haltestelle gibt es mehrere Knoten wegen der Zeit-Dimension...

Nein. Lies meinen Ansatz genau. Eine Fahrt von A->B dauert 5 Minuten, Umsteigen bei B dauert 10 Minuten. Ergo ist fahren und umsteigen ein und dasselbe: Ein Übergang von A nach B, der X Minuten dauert.

Also:
Fahrplan:
Bus 1 fährt von A-10->B-20->C
Bus 2 fährt von B-10->C

Wenn A an B ankommt, fährt #2 3 minuten später ab.
Ich führe einen neuen Knoten ein (B1)
Bus 2 fährt dann nicht von B ab, sondern von B1 -> C (10 Minuten)
Eine neue Kante: Umsteigen von B->B1 (3 minuten).

Also hast Du wieder einen simplen gerichteten Graphen. Nix mit Dimension. Nur eben die Funktion, die die Fahrt/Wartezeit von A nach B ausrechnet, benötigt die Ankunftszeit bei 'A'.

Bei uns wäre das also:
Abfahrt bei A um 15:10 nach B.
Ankunft bei B um 15:20

Bus #2 fährt um 15:23 ab
also bekommt die Kante B->B1 den Wert 3 (Minuten)

Wenn wir bei A um 15:00 losfahren würden, kämen wir bei B um 15:10 an.
Dann bekommt die Kante B->B1 den Wert 13 (Minuten)

verstanden?

[Namenloser]

Dein Algorithmus ist im Prinzip derselbe wie meiner, nur du hast es etwas anders dargestellt als ich. Was du machst, ist halt kein reiner Dijkstra-Algorithmus, weil bei Dijkstra die Kantengewichte fest sind. Was du also eigentlich machst, wenn du das Gewicht einer Kante „dynamisch berechnest“, ist, dass du einen neuen Knoten im Graphen erzeugst (der vorher nie berührt wurde, deshalb hätte er auch genau so gut schon immer da sein können. Man könnte auch sagen, du „entdeckst“ den Knoten), der über eine Kante mit genau diesem Gewicht mit dem aktuellen Knoten verbunden ist. Wenn du also bei dir „einen“ Knoten markierst, markierst du in Wirklichkeit eine ganze Knotenmenge... Das ist dann das gleiche, wie wenn ich sage „Man muss sicherstellen, dass eine bestimmte Haltestelle nur einmal angefahren wird“.

[Furtbichler]

Also ich kann den Djikstra-Algorithmus nehmen (glaube ich zumindest). Ausgehend vom Startknoten weiß ich genau, wie lange ich zur nächsten Station oder zum nächsten Umsteigen brauche. Diese Kanten sind also fest und werden nicht mehr verändert.

Interessantes Problem, jedenfalls.

[Namenloser]

Zitat:

Zitat von Furtbichler (Beitrag 1223601)

Diese Kanten sind also fest und werden nicht mehr verändert.

Aber deine Wartezeiten hängen ja von der Uhrzeit ab und damit von deinem zurückgelegten Pfad. Die Kantengewichte in einem Graphen sind aber unabhängig vom Pfad.

Der Graph, den du dir mit deinem Dijkstra anschaust, ist eigentlich ein Teilgraph. Das funktioniert mit Dijkstra, aber z.B. mit Bellman-Ford würde es nicht funktionieren, weil dort alle Knoten/Kanten bekannt sein müssen. Zugegeben, bei mir wäre es ohne einen Quantencomputer allerdings auch ein bisschen schwierig, weil es ja unendlich Knoten gibt, aber man könnte den Graphen ja zumindest zeitlich beschränken, wie von BUG zuerst vorgeschlagen. Dann kann man sogar mit zeitreisenden Bussen umgehen ;)

Edit: Jetzt krieg ich fast schon Lust, das zu implementieren, die Idee von einem Zeitreisen-Busunternehmen hat irgendwie was :)