Early Pruning for Public Transport Routing

Die vorgestellte Arbeit stellt „Early Pruning" vor, eine effiziente Technik zur Beschleunigung von ÖPNV-Routing-Algorithmen wie RAPTOR, die durch das frühzeitige Verwerfen unnötiger Umsteigeverbindungen die Abfragezeiten um bis zu 57 % reduziert und gleichzeitig die Optimalität der Routen sowie die Integration multimodaler Optionen ohne zusätzliche Infrastruktur ermöglicht.

Das Wesentliche

Das Problem: Der überfüllte Bahnhof

Stell dir vor, du planst eine Reise mit dem öffentlichen Nahverkehr. Du möchtest nicht nur die Busse und Bahnen nutzen, sondern auch zu Fuß gehen, ein E-Scooter mieten oder ein Fahrrad nehmen, um von A nach B zu kommen. Das ist toll, aber für den Computer, der die Route berechnet, wird das schnell zum Albtraum.

Stell dir den Computer als einen sehr gewissenhaften, aber etwas langsamen Kellner vor.

• Die Aufgabe: Der Kellner muss dir den schnellsten Weg zum Ziel (dem Restaurant) zeigen.
• Das Problem: In einer großen Stadt gibt es tausende von Wegen. Der Kellner muss jeden einzelnen Weg prüfen: „Kann ich hier zu Fuß gehen? Ja. Kann ich hier mit dem Scooter fahren? Ja. Kann ich hier den Bus nehmen? Ja."
• Der Flaschenhals: Wenn der Kellner alle diese Möglichkeiten durchgeht, verbringt er so viel Zeit mit dem Prüfen von Wegen, die viel zu lange dauern, dass er dir deine Antwort erst nach Minuten gibt. Das ist wie wenn du im Supermarkt jeden einzelnen Gang durchsuchst, nur um eine Milch zu finden, obwohl du wüsstest, dass die Milch schon im ersten Gang liegt.

Bisher haben die Entwickler dieses „Kellner-Problem" gelöst, indem sie ihm verboten haben, zu weit zu schauen. Sie sagten: „Prüfe nur Wege, die maximal 5 Minuten Fußweg sind." Das war schnell, aber unfair: Vielleicht gab es einen tollen Weg mit einem 8-minütigen Fußweg, den der Kellner einfach ignoriert hat.

Die Lösung: „Frühes Abschneiden" (Early Pruning)

Die Autoren dieses Papiers haben eine geniale, aber einfache Idee entwickelt, die sie „Early Pruning" (Frühes Abschneiden) nennen.

Stell dir vor, der Kellner hat eine Liste aller möglichen Wege vom Bahnhof zum Ziel. Früher hat er diese Liste durcheinander durchgelesen.
Mit der neuen Methode sortiert er die Liste vorher nach der Dauer:

1. Erst der Weg, der 2 Minuten dauert.
2. Dann der Weg, der 5 Minuten dauert.
3. Dann der Weg, der 10 Minuten dauert.
   ... und so weiter.

Der Trick:
Der Kellner fängt bei den schnellen Wegen an (die 2 Minuten). Er prüft sie.
Dann kommt der Weg mit 5 Minuten. Wenn der Kellner merkt: „Moment, selbst wenn ich diesen Weg nehme, komme ich nicht früher an als mein bisheriger bester Fund", dann stoppt er sofort.

Warum? Weil die Liste sortiert ist! Wenn der nächste Weg schon 10 Minuten dauert, wird er noch langsamer sein. Es ist also völlig sinnlos, die restliche Liste zu lesen. Der Kellner schneidet den Rest der Liste einfach ab (pruned) und sagt: „Fertig, hier ist dein Ergebnis."

Warum ist das so großartig?

1. Es ist wie ein Lichtschalter: Sobald der Kellner merkt, dass es keinen Sinn mehr hat, weiterzumachen, schaltet er das Licht aus. Er spart sich riesige Mengen an Arbeit.
2. Es ist fair: Da der Kellner nicht mehr blind ist, kann er jetzt auch Wege prüfen, die etwas weiter entfernt sind (z. B. 10 Minuten Fußweg), ohne dass die Antwortzeit langsamer wird. Du bekommst also mehr Optionen, ohne auf das Handy zu warten.
3. Es funktioniert überall: Die Forscher haben das an echten Netzen (Schweiz und London) getestet. Bei komplexen Routen (wo man viele Optionen wie Laufen, Radfahren und Scooter mischt) wurde die Berechnung bis zu 57 % schneller. Das ist, als würde ein Stau auf der Autobahn plötzlich verschwinden.

Was bedeutet das für uns?

• Für dich als Reisenden: Deine App antwortet blitzschnell, auch wenn du „Ich will auch mal ein E-Scooter nutzen" anklickst. Du siehst mehr kreative Wege, wie du ans Ziel kommst, ohne dein Auto zu nehmen.
• Für die Stadt und die Umwelt: Da die Computer weniger Arbeit haben, brauchen sie weniger Strom und weniger teure Server. Das macht öffentliche Verkehrsmittel attraktiver.
• Für abgelegene Orte: In kleinen Dörfern oder Vororten, wo es keine direkte Busverbindung gibt, können jetzt endlich Wege gefunden werden, die eine Kombination aus Radfahren zum nächsten Bahnhof und dann dem Zug beinhalten. Früher waren diese Wege für die Computer zu kompliziert zu berechnen.

Zusammengefasst:
Die Forscher haben dem Computer beigebracht, nicht alles bis zum Ende durchzuplanen, sondern zu erkennen, wann es sinnlos wird, weiterzumachen. Das ist wie ein kluger Schachspieler, der weiß, dass ein Zug verloren ist, und sofort aufhört, ihn zu analysieren, um sich auf die nächsten Züge zu konzentrieren. Das Ergebnis: Schnellere Apps, mehr Mobilität und weniger Stau in den Köpfen der Computer.

Technische Zusammenfassung

1. Problemstellung

Öffentliche Verkehrs-Routing-Algorithmen, insbesondere die weit verbreitete RAPTOR-Familie (Round-based Public Transit Routing) und ihre Varianten, stoßen bei der Unterstützung von unbegrenzten Umsteigemöglichkeiten (z. B. zu Fuß, Fahrrad, E-Scooter) an Leistungsengpässe an.

• Hauptbottleneck: Die Phase der Transfer-Relaxation. In dieser Phase muss der Algorithmus über viele potenzielle Verbindungen zwischen Haltestellen iterieren.
• Dichte Graphen: Durch die Einbeziehung multimodaler Optionen (Walking, Cycling, Shared Mobility) werden die Transfer-Graphen extrem dicht. Das Iterieren über alle ausgehenden Kanten an jeder Haltestelle führt zu langen Abfragezeiten.
• Praktische Konsequenz: Um akzeptable Antwortzeiten zu gewährleisten, beschränken Praktiker oft die Umsteigeentfernungen oder schließen bestimmte Modi aus. Dies führt zu suboptimalen Routen und schränkt die multimodalen Optionen für Reisende ein, was die Attraktivität des öffentlichen Verkehrs mindern kann.

2. Methodik: Early Pruning

Die Autoren stellen Early Pruning (Frühes Beschneiden) vor, eine Technik, die die Abfragezeit beschleunigt, ohne die Optimalität der gefundenen Pfade zu beeinträchtigen.

• Kernidee: Vor dem Start der Suche werden alle ausgehenden Transfer-Kanten an jeder Haltestelle nach ihrer Dauer (Transferzeit) sortiert (nicht aufsteigend).
• Der Pruning-Mechanismus:
  • Während der Transfer-Relaxation in einer Runde wird die Iteration über die Kanten eines aktualisierten Haltepunkts $s$ fortgesetzt, solange die berechnete Ankunftszeit am Ziel $t$ besser ist als die aktuell bekannte beste Ankunftszeit $\tau^*(t)$.
  • Da die Kanten sortiert sind, gilt: Wenn für eine Kante $e_i$ die Bedingung $\tau_k(s) + \tau(e_i) \ge \tau^*(t)$ erfüllt ist (d.h. die Ankunft ist nicht früher als das beste bekannte Ergebnis), dann gilt dies auch für alle folgenden Kanten $e_j$ ($j > i$), da diese eine gleiche oder längere Dauer haben.
  • Konsequenz: Die Iteration kann sofort abgebrochen werden, da alle verbleibenden Kanten keine Verbesserung liefern können.
• Erweiterung auf Mehrkriterien-Optimierung: Für Algorithmen wie McRAPTOR (die z. B. Ankunftszeit, Gehzeit und Anzahl der Umstiege optimieren), wird das Prinzip der Dominanz angewendet. Wenn eine neue Teilstrecke bereits in allen Kriterien von einer bestehenden Lösung dominiert wird und die Gehzeit weiter zunimmt, können alle weiteren, längeren Kanten sicher übersprungen werden.
• Vorteile:
  • Benötigt nur einen einmaligen Preprocessing-Schritt (Sortieren der Kanten).
  • Dieser Schritt ist robust gegenüber Fahrplanänderungen (da er nur die Graph-Struktur betrifft, nicht die Fahrzeiten selbst) und dauert weniger als 600 ms.
  • Kann mit minimalen Änderungen in bestehende Codebasen integriert werden.

3. Wichtige Beiträge

1. Algorithmische Optimierung: Einführung einer effizienten Pruning-Strategie, die speziell für die Transfer-Relaxation in RAPTOR-basierten Algorithmen entwickelt wurde.
2. Formale Korrektheit: Beweis der Korrektheit der Methode für sowohl eindimensionale (nur Ankunftszeit) als auch mehrdimensionale (Pareto-optimierte) Suchräume.
3. Umfassende Evaluation: Testung auf sechs verschiedenen RAPTOR-Varianten (RAPTOR, ULTRA-RAPTOR, McRAPTOR, BM-RAPTOR, ULTRA-McRAPTOR, UBM-RAPTOR) in zwei realen Netzwerken (Schweiz und London).
4. Analyse des Zusammenhangs: Untersuchung der Korrelation zwischen der Dichte des Transfer-Graphen und dem erzielten Geschwindigkeitsgewinn.

4. Ergebnisse

Die Experimente wurden auf einem MacBook Pro (Apple M3 Max) durchgeführt. Die Ergebnisse zeigen konsistente Verbesserungen:

• Geschwindigkeitssteigerung: Die Abfragezeiten wurden um 2 % bis 57 % reduziert.
  • Höchste Gewinne: Bei Algorithmen, die auf dichten, transitiven Graphen arbeiten (z. B. McRAPTOR auf dem Londoner Netz: 56,9 % schneller; RAPTOR auf dem Schweizer Netz: 21,7 % schneller).
  • Geringere Gewinne: Bei ULTRA-basierten Varianten (z. B. ULTRA-McRAPTOR), da diese bereits vorkalkulierte Shortcuts verwenden, die deutlich weniger Kanten enthalten und somit weniger Potenzial für das Pruning bieten.
• Korrelation: Es besteht eine signifikante positive Korrelation (Pearson-Korrelation 0,62) zwischen der Graphendichte und dem Geschwindigkeitsgewinn. Je dichter der Graph, desto effektiver ist Early Pruning.
• Preprocessing: Das Sortieren der Kanten ist extrem schnell (z. B. 417 ms für den transitive Graphen der Schweiz) und muss nicht bei jeder Fahrplanänderung neu berechnet werden.

5. Bedeutung und Implikationen

Die Arbeit hat weitreichende praktische und politische Konsequenzen:

• Multimodale Integration: Durch die Reduktion der Rechenzeit können Verkehrsbehörden größere Umsteigeradien zulassen und mehr Mobilitätsmodi (E-Scooter, Fahrrad, Sharing) in die Planer integrieren, ohne die Serverkapazität erhöhen zu müssen.
• Verbesserte Nutzererfahrung: Schnellere Antwortzeiten ermöglichen interaktive Anwendungen, die komplexe, multimodale Routen in Echtzeit berechnen. Dies ist besonders wichtig für Pendler in Vororten oder kleineren Städten mit schlechter direkter Anbindung, da hier multimodale Alternativen zum Auto oft die einzige Option sind.
• Kosteneffizienz: Eine Reduktion der Abfragezeiten um 10–30 % bedeutet bei Millionen von täglichen Abfragen signifikante Einsparungen bei Server- und Energiekosten.
• Robustheit: Da die Methode nicht von den Fahrplandaten abhängt, sondern nur von der Graph-Struktur, ist sie gegenüber Verspätungen und Störungen im Fahrplan resilient.
• Politische Relevanz: Die Technik unterstützt Ziele der „Mobility-as-a-Service" (MaaS)-Strategie, indem sie die technische Hürde für die Bereitstellung reichhaltiger, multimodaler Reiseinformationen senkt und so die Verkehrswende fördert.

Fazit: Early Pruning ist eine einfache, aber hochwirksame Methode, um die Effizienz von öffentlichen Verkehrs-Routern signifikant zu steigern. Sie ermöglicht es, die Komplexität moderner multimodaler Netzwerke zu bewältigen, ohne auf Optimalität verzichten zu müssen.