Entwicklung einer Fahrplanauskunft

[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.