RAPTOR-Algorithmus

Der RAPTOR-Algorithmus ist ein Algorithmus von Daniel Delling, Thomas Pajor und Renator F. Werneck. Deren Forschung wurde 2012 bei Microsoft Research veröffentlicht. Es hat bei der Wegfindung (engl. pathfinding) den Dijkstra-Algorithmus ersetzt, um einen effizienteren Weg zu finden, den schnellsten Weg im ÖPNV zu zeigen. Dabei kann es mehrere Priorisierungen haben, unter anderem maximale Umsteige oder schnellster Weg zum Ziel.

Verwendung

Der Algorithmus wird von vielen Diensten benutzt unter anderem von Apple Karten oder Google Maps. Der Code hat viele verschiedene Varianten, z. B. "frequency-based RAPTOR", welches die Routen in Takten beschreibt, anstatt jede einzelne Fahrt einer Route zu berücksichtigen.

Pseudocode vom Algorithmus

1. Initialisierung:

  Für jede Haltestelle v:
      earliestArrival[v] = ∞
  earliestArrival[S] = Startzeit
  markedStops = {S}

"markedStops" stellt die Haltestellen dar die sich in der letzten Runde verbessert haben.
2. Ausführung des Codes -> Für Runde k = 1 bis maxRunden:

      newMarkedStops = ∅
      Für jede Route r in Routen:
          Wenn r mindestens eine Haltestelle aus markedStops enthält:
              earliestTrip = frühester Trip auf r nach Ankunftszeiten der markierten Haltestellen
              Für jede Haltestelle u auf r nach earliestTrip:
                  arrivalTime = Ankunftszeit von earliestTrip an u
                  Wenn arrivalTime < earliestArrival[u]:
                      earliestArrival[u] = arrivalTime
                      newMarkedStops.add(u)

      markedStops = newMarkedStops
      Wenn markedStops leer ist:
          Stoppen (keine Verbesserungen mehr möglich)

Am Anfang betrachtet er jede Route, die eine markierte Haltestelle enthält. Danach propagiert er Fahrten entlang der Routen. Zum Schluss stoppt er den Algorithmus wenn er keine Verbesserung mehr sieht.
3. Rückgabe der frühsten Ankunftszeit:

  earliestArrival[T]