Der RAPTOR-Algorithmus wird häufig zur Echtzeit-Routenplanung im ÖPNV verwendet. RAPTOR kann jedoch Routen vorschlagen, die früher als nötig beginnen oder ’zyklische’ Routen, bei denen eine Station doppelt angefahren wird. Dies wird oft von Fahrgästen als nicht-intuitiv empfunden. Wir identifizieren zwei Gründe, warum RAPTOR solche Routen berechnet: Erstens betrachtet RAPTOR die Reisezeit nicht als Optimierungskriterium. Zweitens wird bei der Berechnung der Routen nicht zwischen Wartezeit, etwa bei Umstiegen, und Fahrtzeit unterschieden. Wir entwerfen einen Ansatz, der die grundsätzliche Implementierung eines RAPTORs nicht verändert, jedoch die Anzahl der ’nicht-intuitiven’ Vorschläge in einem realen städtischen Nahverkehrsnetz um etwa 90% reduziert. Der Ansatz minimiert die Fahrtzeit implizit, so dass viele zyklische Routen und zu früh abfahrende Fahrten nicht mehr vorgeschlagen werden.

Der Beitrag ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einführung

Viele Verkehrsdienstleister stellen ihren Fahrgästen Routing-Services zur Verfügung. Der Nutzer gibt seinen Ausgangspunkt, sein Ziel und die bevorzugte Ankunfts- oder Abfahrtszeit ein; der Routing-Service berechnet dann mittels Routenplanungsalgorithmen Vorschläge, wie das Ziel mit öffentlichen Verkehrsmitteln erreicht werden kann.

Häufig existieren mehrere Optionen für eine Route von einem Ausgangs- zu einem Zielort. Zudem kann ein Umsteigen erforderlich sein, d. h. ein Wechsel von einem Fahrzeug auf ein anderes an einer Zwischenstation. Im Allgemeinen wollen die Nutzer die Fahrzeit sowie die Kosten minimieren und bevorzugen direkte Fahrten gegenüber Verbindungen, die ein Umsteigen erfordern [7]. Dabei sind “Trade-offs” zwischen den Kriterien möglich, beispielsweise kann der Fahrpreis für eine kürzere Fahrt höher sein als für eine längere Fahrt, sodass die individuellen Präferenzen der Nutzer bedeutsam sind. Konkret ziehen viele Nutzer eine etwas längere Fahrt einer kurzen Fahrt vor, wenn die Anzahl der Umstiege dadurch reduziert wird. Auch spielen die äußeren Rahmenbedingungen mitunter eine Rolle, etwa das Wetter sowie die Auslastung der Verkehrsmittel (zum Beispiel die Wahrscheinlichkeit einen Sitzplatz zu erhalten). Zahlreiche weitere Anforderungen sind zumindest für bestimmte Nutzergruppen bedeutsam, etwa die Barrierefreiheit oder die Möglichkeit zur Mitnahme von Fahrrädern.

Normalerweise verwenden Routenplanungsalgorithmen mehrere Kriterien, um die Routen auszuwählen, die dem Benutzer vorgeschlagen werden. Genutzt werden insbesondere die Fahrzeit und die Anzahl der Umstiege. Route A wird als dominante Route gegenüber Route B definiert, wenn kein Kriterium existiert, bei dem Route B besser ist. Wird eine Route nicht von einer anderen Route dominiert, spricht man von einer Pareto-optimalen Route. Insbesondere wenn zwei oder mehr Kriterien verwendet werden, gibt es mehrere Pareto-optimale Routen. Der Benutzer kann dann aus diesen Routen die für ihn passende Route wählen.

Statische Algorithmen arbeiten mit dem geplanten Fahrplan. Andere Algorithmen, die als Echtzeit-Algorithmen bezeichnet werden, arbeiten mit Live-Fahrplänen, die  Echtzeitinformationen über die Position aller Fahrzeuge im öffentlichen Verkehrssystem nutzen, wobei Verspätungen und frühzeitige Ankünfte berücksichtigt werden. Ein Vorteil des statischen Routings ist, dass z.B. Routen vorberechnet werden können. Dadurch sind statische Algorithmen deutlich schneller [3]. Da der Live-Fahrplan sich im Sekunden-Takt ändern kann, ist das Design von schnellen Echtzeit-Routenplanungsalgorithmen eine Herausforderung. Laut Delling et al. [2] sind Connection Scan [5], Round Based Public Transit Routing (RAPTOR) [4] und Dijkstra-Varianten [11] die bekanntesten Echtzeit-Routenplanungsalgorithmen. In Routing-Services, die RAPTOR für Echtzeit-Routenplanung verwenden, berichten Anwender allerdings häufig, dass das System Routen vorschlägt, die als ’nicht-intuitiv’ empfunden werden. Insbesondere schlägt RAPTOR manchmal eine Route vor, die eine Haltestelle zweimal anfährt. Weiter kommt es zu Vorschlägen, bei denen der Fahrgast früher als erforderlich abfährt.

Dieser Beitrag untersucht eine Implementierung des RAPTOR-Algorithmus mit zwei Optimierungskriterien, welche von der IVU Traffic Technologies AG für den Aachener Nahverkehr verwendet wird. Der Algorithmus liefert Pareto-optimale Fahrten, wobei die Ankunftszeit und die Anzahl der Umstiege als Optimierungskriterien verwendet werden. Vor dem oben beschriebenen Hintergrund konzentriert sich dieser Beitrag auf zwei zusammenhängende Fragenkomplexe. Der erste Fragenkomplex befasst sich mit der Wahrnehmung der Nutzer: Wie entscheiden die Nutzer, wenn sie aus einem Set von Pareto-optimalen Routen wählen können und welche Vorschläge werden als “nicht-intuitiv” betrachtet. Der zweite Fragenkomplex zielt auf die Verbesserung des RAPTOR-Algorithmus ab: Wie können nicht-intuitive Routenvorschläge identifiziert und aus der Vorschlagsliste ausgeschlossen werden.

Der Beitrag ist wie folgt aufgebaut: In Abschnitt 2 werden spezifische Begriffe definiert. Im Abschnitt 3 werden wesentliche Merkmale der Benutzerpräferenzen und die Spezifika intuitiver und nicht-intuitiver Routen beschrieben. Im Abschnitt 4 wird der RAPTOR-Algorithmus beschrieben. Die Gründe, warum nicht-intuitive Routen von RAPTOR vorgeschlagen werden, werden im Unterabschnitt 4.4 dargestellt. Im Abschnitt 5 werden Verbesserungspotenziale und Möglichkeiten der Implementierung diskutiert. Basierend auf dieser Analyse wird im Unterabschnitt 5.2 eine Lösung, die den Anteil der nicht-intuitiven Routen in der getesteten Umgebung um 90% reduziert, näher diskutiert. Die Leistungsfähigkeit dieser Lösung wird in einem Experiment im Abschnitt 6 getestet. Die Ergebnisse werden im Abschnitt 7 diskutiert, wobei der Anteil von zwei Arten von nicht-intuitiven Routen und die Auswirkung auf die Laufzeit des Algorithmus analysiert werden. Komplexere Ansätze, deren vertiefte Diskussion den Rahmen dieses Beitrages sprengen würde, werden im Abschnitt 8 vorgestellt. Abschnitt 9 fasst die Ergebnisse zusammen.

2 Definitionen

Im Folgenden werden die wichtige Begriffe definiert. Der RAPTOR-Algorithmus selbst wird in Unterabschnitt 4.1 genauer dargestellt.

Ein Fahrplan wird durch S = (S; L; T) dargestellt, wobei S eine Menge von Haltestellen bezeichnet, an denen Fahrzeuge anhalten, um Passagiere ein- oder aussteigen zu lassen. L ist eine Menge von Linien, wobei jede Linie eine vorbestimmte Abfolge von Haltestellen abfährt. Für jede Linie l 2 L und jede Haltestelle s dieser Linie ist ein Tupel tl;s zugeordnet, das aus Ankunftszeit und Abfahrtszeit besteht. Alle Tupel tl;s werden in T gespeichert und stellen den Fahrplan dar.

In diesem Beitrag werden die Fahrpläne als gerichtete Graphen visualisiert. Knoten dienen als Haltestellen mit einer eindeutigen Kennung und Kanten stellen Linien dar. Bei mehreren Linien werden die verschiedenen Kanten farbig dargestellt und beschriftet. Abfahrts- und Ankunftszeiten der Fahrzeuge werden auf den Kanten neben der jeweiligen Haltestelle angezeigt. Entlang der Richtung der Kante werden in der ersten Klammer die Abfahrtszeiten und in der zweiten Klammer die Ankunftszeiten an der nächsten Haltestelle angezeigt. Werden mehrere Frequenzen auf einer Linie betrieben, werden die Zeiten durch ein Komma getrennt. Zur Vereinfachung der Darstellung werden die Zeiten mit einer einzigen Zahl dargestellt, was z.B. die Zeit in Minuten messen kann.

Eine Route ist eine Reise eines Fahrgastes von seinem Ausgangspunkt bis zu seinem Ziel mit öffentlichen Verkehrsmitteln. Eine Route besteht aus n Fahrten und (n – 1) Umstiegen, wobei n ∈ N+. Eine Fahrt ist definiert als eine Teilstrecke auf der ein Fahrgast an einer Haltestelle in ein Fahrzeug einsteigt und an einer späteren Haltestelle auf der gleichen Linie aussteigt. Wenn der Fahrgast ein Fahrzeug an einer Haltestelle verlässt und in ein anderes Fahrzeug einsteigt, nennt man das einen Umstieg. Wie in der Einleitung erwähnt, wurden einige Vorschläge des RAPTOR-Algorithmus von mehreren Nutzern als “nicht-intuitiv” kritisiert. Wir werden keine exakte Definition von intuitiv geben. Im Allgemeinen wird der Begriff intuitiv verwendet, wenn etwas bekannt ist oder von einer Person verstanden wird, ohne dass es Beweise oder Belege gibt [8].

3 Routenwahl aus der Nutzerperspektive

3.1 Nutzerpräferenzen

Die Routenwahl im öffentlichen Verkehr ist, wie bereits oben erwähnt, ein Auswahlprozess auf der Basis mehrerer Kriterien. Folglich kann es zu Trade-offs zwischen den Kriterien kommen, und es ist anzunehmen, dass die Bedeutung der einzelnen Faktoren von Benutzer zu Benutzer unterschiedlich ist. Intuitivität ist bis zu einem gewissen Grad individuell und ohne Personalisierung kaum zu erreichen. Generell könnte Personalisierung zu einer insgesamt höheren Kundenzufriedenheit führen. Der Algorithmus könnte sich an den einzelnen Nutzer anpassen und Routen vorschlagen, die der Nutzer normalerweise nimmt, oder Routen nach expliziten Präferenzen des Nutzers filtern. Das Vorschlagen von personalisierten Routen erfordert jedoch eine Benutzerklassifizierung, z. B. durch Standortverfolgung, welche zu Datenschutzproblemen führen könnte. Eine mögliche Alternative wäre es, die Benutzer die Einstellungen anpassen zu lassen, z.B. die Festlegung einer Mindestumsteigezeit, wie sie u. a. von der Routenplanungs-Website der Deutschen Bahn angeboten wird. Darüber hinaus könnte der Algorithmus externe Faktoren, wie das aktuelle Wetter, bei der Routenvorgabe berücksichtigen.

3.2 Arten von nicht-intuitiven Routen

In den Rückmeldungen der Nutzer zum untersuchten RAPTOR-Algorithmus werden hauptsächlich zwei Arten von nicht-intuitiven Vorschlägen kritisiert. Erstens schlägt der Algorithmus manchmal eine Route vor, bei der der Fahrgast früher als nötig abfährt und länger als erforderlich an einer Umstiegshaltestelle warten muss. Der Fahrgast könnte ein späteres Fahrzeug nehmen, das auf der gleichen Linie fährt und hätte trotzdem die Anschlussfahrt erreicht. Ein Beispiel für eine solche Route ist in Abbildung 1 zu sehen. Der Fahrgast möchte von A nach C fahren. Die Strecke besteht aus zwei Fahrten und der Fahrgast muss in B umsteigen. Die Linie L1 bedient die Strecke zweimal, wobei das erste Fahrzeug auf der Minute 5 abfährt und zu der Minute 7 ankommt. Das zweite Fahrzeug fährt auf Minute 10 ab und kommt zur Minute 12 an. Die Linie L2 wird nur einmal bedient, die Abfahrt von B erfolgt auf der Minute 15 und das Ziel C wird zur Minute 25 erreicht. RAPTOR bietet nur einen Vorschlag an, um von A nach C zu gelangen. Unter der Annahme, dass der Passagier die Anfrage vor der Minute 5 stellt, empfiehlt der Algorithmus, zur Minute 5 die Linie L1 von A nach B zu nehmen und an der Haltestelle B zur Linie L2 zu wechseln. Der Fahrgast erreicht C zur Minute 25. Ein Fahrgast könnte aber auch die spätere Fahrt der Linie L1 nehmen, um fünf Minuten später an der Umstiegshaltestelle B anzukommen.

Er wäre dennoch früh genug dort, um die Anschlussfahrt zu erreichen. Die Routen unterscheiden sich in der Abfahrtszeit und der Wartezeit an der Umstiegshaltestelle B. Die zweite Fahrt mit der Linie L1 scheint für den Benutzer intuitiver zu sein und bietet genügend Umsteigezeit bei einer späteren Abreise. Im weiteren Verlauf dieses Beitrags wird diese Art von Route als T-Route bezeichnet. Genauer ist eine T-Route als eine Route definiert, sodass mindestens eine weitere Route mit identischer Linienkombination existiert die zur gleichen Zeit ankommt, jedoch früher abfährt. Beide Routen sind gleichzeitig Pareto-optimal oder sing gleichzeitig nicht Pareto-optimal, wenn die Ankunftszeit und die Anzahl der Umstiege als Kriterien benutzt werden. Die spätere Route dominiert jedoch die frühere in der Reisezeit.

Grundsätzlich ist darauf hinzuweisen, dass nicht jede T-Route für den Fahrgast negativ ist. Wenn ein Fahrgast an einer Haltestelle warten muss, ließe sich annehmen, dass es irrelevant sei, an welcher Haltestelle er dies tut. Unter gewissen Umständen, etwa bei Regen, ist es jedoch eventuell wünschenswert an einer überdachten Haltestelle zu warten. In dem oben genannten Beispiel wäre dies der Fall, wenn der Fahrgast sich zum Zeitpunkt der Abfrage bereits an einer Haltestelle befindet, welche über keine Überdachung verfügt, die Umstiegshaltestelle jedoch mit einer solchen ausgestattet ist. Allerdings müssten diese Informationen dann auch im Datensatz hinterlegt sein, um bei den Routenvorschlägen berücksichtigt werden zu können.

Abbildung 1: Beispiel einer T-Route

Abbildung 2: Beispiel einer Z-Route

Zweitens schlägt der Algorithmus manchmal zyklischen Routen vor, d. h. während der Fahrt kehrt der Fahrgast zu einer Haltestelle zurück, an der er zuvor bereits war. Dies kann ebenfalls als nicht-intuitiv angesehen werden, insbesondere wenn der Fahrgast an der entsprechenden Haltestelle in das Fahrzeug eingestiegen ist. Wenn dies der Fall ist und durch das Entfernen des Zyklus die Zeit zwischen Abfahrt und Ankunft reduziert werden kann, werden zyklische Routen als Z-Routen bezeichnet. Im Beispiel der Abbildung 2 möchte ein Fahrgast von S nach T fahren. Wenn der Fahrgast vor der Minute 12 an S ankommt, wird der Algorithmus ihm vorschlagen, dass er an der Haltestelle S zur Minute 12 abfahren und den Umweg über A und D nehmen soll. Der Fahrgast kann allerdings auch an der Haltestelle S zur Minute 26 einsteigen. Beide Fahrten kommen zur gleichen Zeit an der Haltestelle T an, aber das Einsteigen in das Fahrzeug bei der zweiten Möglichkeit reduziert die Fahrzeit um 14 Minuten. Zusätzlich zur längeren Fahrt kann es sein, dass der Fahrgast für die längere Fahrt mehr bezahlen muss. Auch hier könnte der Fahrgast, beispielsweise je nach Witterung, die längere Fahrt gegenüber der Zeit an der Haltestelle vorziehen. Im folgenden Abschnitt wird analysiert, warum der RAPTOR-Algorithmus T-Routen und Z-Routen vorschlägt. Im weiteren Verlauf dieses Beitrags wird eine nicht-intuitive Route definiert als eine Route die entweder T-Route oder Z-Route ist.

4 Analyse des Algorithmus

4.1 RAPTOR

Für die Analyse des Algorithmus werden zunächst die Eigenschaften des RAPTOR-Algorithmus skizziert. Zweitens wird der Ablauf des Algorithmus beschrieben und ein kurzer Überblick über die Implementierung anhand eines kleinen Beispielnetzes gegeben. Schließlich wird im folgenden Unterabschnitt diskutiert, warum nicht-intuitive Routen vorgeschlagen werden. Die Verwendung von Echtzeit-Fahrzeugpositionen bedeutet, dass sich der Fahrplan häufig ändert. Deshalb ist es wichtig, dass die Routenvorschläge schnell berechnet werden können. Laut Delling et al. [2] ist RAPTOR etwa doppelt so schnell wie andere Routingalgorithmen wie etwa Dijkstra-Varianten [11], die nur auf der Basis eines Kriteriums optimieren, oder A-Star-Algorithmen [9]. RAPTOR berechnet ein Set aus Pareto-optimalen Routen für gegebene Kriterien, standard sind dies die Ankunftszeit und die Anzahl der Umstiege. Die Reisezeit, die ebenfalls ein wichtiges Kriterium ist, wie in Abschnitt 3.1 erläutert, ist schwer zu modellieren, kann aber durch Abfahrts- und Ankunftszeit berechnet werden. Zusätzliche Kriterien, wie von Delling et al. [4] und Brack [1] vorgeschlagen, können hinzugefügt werden, was jedoch zu einer exponentiellen Erhöhung der Laufzeit führt.

Obwohl die Ankunftszeit für die Reisenden wichtig ist, garantiert die Verwendung dieses Kriteriums nicht, dass die Route mit der kürzesten Fahrzeit vorgeschlagen wird. Ohne Berücksichtigung der Reisezeit unterscheidet der Algorithmus nicht zwischen einer frühen und einer späten Abfahrt, die eine identische Ankunftszeit aufweisen. Wie in Abschnitt 3.2 gezeigt, führt dies dazu, dass Routen vorgeschlagen werden, die als nicht-intuitiv von Reisenden gemeldet werden.

4.2 Ablauf des Algorithmus

Der RAPTOR-Algorithmus arbeitet in Runden, welche die Anzahl der Umstiege von der berechneten Routen von einem Ausgangspunkt S zu einem Ziel T darstellen. In Runde 0 wird S mit der Ankunftszeit des Reisenden am Ausgangspunkt initialisiert. In Runde 1 findet der Algorithmus alle Haltestellen, die von S aus ohne Umstiege erreicht werden können. Für jede dieser Haltestellen speichert der Algorithmus die früheste Ankunftszeit an dieser Haltestelle. Wenn eine der erreichten Haltestellen das Ziel T ist, fügt der Algorithmus die Route zum Pareto-optimalen Set hinzu. Für alle folgenden Runden fragt RAPTOR alle abfahrenden Linien an Haltestellen ab, an denen in der vorherigen Runde Zeiten hinzugefügt oder verbessert wurden. Dabei wird darauf geachtet, dass eine konfigurierbare Umstiegszeit eingehalten wird. Der Algorithmus sucht nun nach Fahrten, auf denen eine Haltestelle entweder zum ersten Mal oder schneller als zuvor erreicht werden kann. Für diese Haltestellen addiert er die Ankunftszeiten der jeweiligen Runde. Findet der Algorithmus eine Fahrt zu T, so wird diese nur dann zum Pareto-optimalen Set hinzugefügt, wenn sie früher ankommt als Fahrten mit weniger Umstiegen. Der Algorithmus bricht ab, wenn die Ankunftszeit nicht weiter verbessert werden kann. In der Praxis begrenzt ein Abbruchkriterium oft die maximale Anzahl der Runden, was die Laufzeit des Algorithmus reduziert. So sind etwa in mittelgroßen Städten (z. B. Aachen) Routen mit mehr als fünf Umstiegen aufgrund der Netzstruktur eher selten. Daher kann die Obergrenze der Runden beispielsweise auf fünf festgelegt werden. Da der Algorithmus nicht notwendigerweise mehrere Routen und – genauer gesagt – nur eine Route für jede Anzahl von Umstiegen liefert, wird der Algorithmus wiederholt mit verschobenen Startzeiten ausgeführt. Nehmen wir an, dass eine Abfrage um 11:30 Uhr eine Route ergibt, die um 12:00 Uhr abfährt. Diese Route bleibt Pareto-optimal für jede Abfragezeit von 11:30 bis zu 12:00 Uhr. Um die Anzahl der vorgeschlagenen Routen zu erhöhen, wird der Algorithmus erneut mit der Startzeit 12:01 ausgeführt. Dies führt zu einem anderen Vorschlag, da die bis zu diesem Zeitpunkt Pareto-optimale Route nicht mehr durchführbar ist. Dieser Vorgang wird so lange wiederholt, bis eine vordefinierte Anzahl von Routen gesammelt wurde, die dem Benutzer vorgeschlagen werden können.

4.3 Beispiel für ein RAPTOR-Routing

Abbildung 3 bis Abbildung 6 zeigen ein einfaches Liniennetz mit vier Haltestellen S; A;B; T und drei Linien L1;L2;L3. Zur Vereinfachung wird jede Linie nur einmal befahren. Der Algorithmus speichert für jede Runde Ankunftszeit(en). Diese werden in eckigen Klammern in den Knoten, getrennt durch ein Komma, vermerkt. Es wird angenommen, dass ein Fahrgast zur Minute 0 an der Haltestelle S ankommt und zum Ziel T gelangen möchte. Der Algorithmus trägt die Zeit für Runde 0 am Startpunkt ein, was in Abbildung 3 zu sehen ist. Damit ist die Runde 0 abgeschlossen.

Abbildung 5: RAPTOR - Runde 1 - Line 2

Abbildung 6: RAPTOR - Runde 2

Abbildung 3: RAPTOR - Runde 0

Abbildung 4: RAPTOR - Runde 1 - Line 1

Zu Beginn jeder Runde iteriert RAPTOR über die Haltestellen, die in der vorherigen Runde aktualisiert wurden. Für jede der aktualisierten Haltestellen wählt er die erste Fahrt jeder Linie, die von dieser Haltestelle abfährt. Im hier genutzten Beispiel beginnt der Algorithmus Runde 1 mit Linie L1, die von S abfährt. In Abbildung 4 ist veranschaulicht, wie er die Ankunftszeiten für jede Haltestelle aktualisiert, die von S aus mit L1 erreicht werden kann. Da L1 eine direkte Verbindung zu T ist, wird diese Option zusätzlich zu dem Set der Pareto-optimalen Routen hinzugefügt.

Abbildung 5 zeigt die zweite Linie, die in Runde 1 betrachtet wird. L2 ist ebenfalls eine direkte Fahrt zu T. Der RAPTOR-Algorithmus vergleicht dann die beiden Routen nach den implementierten Kriterien. Beide Routen haben die gleiche Anzahl von Umstiegen, jedoch kommt L2 früher bei T an. Somit dominiert die Fahrt der Linie L2 die Fahrt der Linie L1. Die Route mit der Linie L1 wird aus dem Pareto-optimalen Set entfernt und durch L2 ersetzt. Dies beendet Runde 1, da jede Linie, die bei S abfährt, betrachtet wurde. Abbildung 6 zeigt, wie der Algorithmus in Runde 2 versucht, eine Fahrt mit einem Umstieg zu finden, die früher als die in Runde 1 gefundene Fahrt ankommt. Die Ankunftszeiten an den Haltestellen werden nur dann aktualisiert, wenn die Haltestelle in der/den vorhergehenden Runde(n) nicht erreicht werden konnte oder früher als in der/den vorhergehenden Runde(n) erreichbar ist. In Runde 1 wurden die Haltestellen A, B und T initialisiert. T wird nicht berücksichtigt, da es das Ziel ist. B wird ebenfalls nicht berücksichtigt, da der Algorithmus bereits alle Linien, die von B ausgehen, durchlaufen hat. Bei der Haltestelle A kann der Algorithmus Linie L3 folgen und findet damit einen schnelleren Weg zum Ziel. Die Ankunftszeit bei T wird für Runde 2 hinzugefügt und Runde 2 wird mit dem Hinzufügen der Strecke L1;L3 zu dem Set der Pareto-optimalen Routen abgeschlossen. Würde die Fahrt nach der Minute 20 ankommen, so würde sie verworfen, da sie hinsichtlich beider Kriterien, Ankunftszeit und Anzahl der Umstiege, von den Fahrten aus Runde 1 dominiert würde. Nach dem Beenden von Runde 2 endet der Algorithmus, da die Ankunftszeiten nicht weiter verbessert werden können.

Zusätzlich zur Suche nach Fahrten mit einer gegebenen Abfahrtszeit kann der Algorithmus auch Routen mit einer gewünschten Ankunftszeit finden. Das Finden einer Route mit einer vorgegebenen Ankunftszeit wird als Rückwärtsrouting bezeichnet, da der Algorithmus die Zielhaltestelle T als Starthaltestelle verwendet und die Abfahrtszeiten ähnlich wie die Ankunftszeiten in der ersten Option behandelt; man fährt in der Zeit rückwärts so zu sagen.

4.4 Probleme eines Zwei-Kriterien-RAPTOR

Wie bereits erwähnt, weist RAPTOR-Algorithmus, der die Ankunftszeit und die Anzahl der Umstiege als Kriterien verwendet, hauptsächlich zwei Probleme auf. Da der Algorithmus die Reisezeit nicht berücksichtigt, schlägt er vor, die früheste Reiseoption zu nutzen. Folglich wird dem Fahrgast vorgeschlagen, bei der ersten Möglichkeit einsteigen, auch wenn die Fahrt einen Zyklus enthält. Die Ankunftszeit wird dadurch nicht beeinträchtigt und die Fahrt wird somit als Pareto-optimal eingestuft. T-Routen werden durch denselben Effekt verursacht. Der Algorithmus folgt einem Monotonie-Kriterium, das davon ausgeht, dass bei zwei Fahrten, die die gleiche Linienkombination verwenden, die später abfahrende Fahrt nicht vor der früher abfahrenden Fahrt ankommt. Daher berücksichtigt der Algorithmus keine späteren Fahrten der gleichen Linie, da sie die aktuelle Strecke in der Ankunftszeit nicht dominieren können. Die Prüfung von späteren Fahrten würde die Laufzeit deutlich erhöhen. Hervorzuheben ist, dass die genannten Arten von nicht-intuitiven Routen bei einem Rückwärtsrouting nicht auftreten können. Der Grund dafür ist, dass der Algorithmus bei einer vorgegebenen Ankunftszeit die Fahrten mit der spätesten Abfahrtszeit findet. Dem Fahrgast wird somit nicht vorgeschlagen, eine Fahrt früher als erforderlich anzutreten. In Abschnitt 5.2 wird erläutert, wie diese Eigenschaft zum Entfernen der nicht-intuitiven Routen benutzt werden kann.

5 Verbesserungen des RAPTOR-Algorithmus

5.1 Verbesserungsmöglichkeiten

In diesem Abschnitt werden mögliche Verbesserungen vorgestellt, um nicht-intuitive Routenvorschläge des RAPTOR-Algorithmus auszuschließen. Zunächst wird ein Überblick über Verbesserungsoptionen gegeben, die nicht implementiert und getestet wurden. Der zweite Unterabschnitt illustriert eine Lösung, die für einen Zwei-Kriterien-RAPTOR unter Verwendung der Ankunftszeit und der Anzahl der Umstiege implementiert und getestet wurde. Um nicht-intuitive Routen auszuschließen, liegt es nahe, die Reisezeit als zusätzliches Kriterium hinzuzufügen. Da sowohl T-Routen als auch Z-Routen eine längere Reisezeit verursachen, würden sie wahrscheinlich ausgeschlossen, wenn man die Reisezeit als Kriterium hinzufügt. Die Hinzufügung weiterer Kriterien führt jedoch zu einer exponentiellen Laufzeiterhöhung. Für jede Haltestelle müssten nicht nur die nächsten abfahrenden Linien geprüft werden, sondern jede Fahrt jeder Linie bis zur frühesten bisher gefundenen Ankunftszeit. Mittelgroße Städte wie Aachen haben ca. 1000 Haltestellen mit über 22000 täglichen Fahrten auf etwa 100 Linien. Einige dieser Linien bieten in der Hauptverkehrszeit Abfahrten im Abstand von weniger als zehn Minuten an. Bei einem Netz dieser Größe ist die Umsetzung des Kriteriums Fahrzeit aufgrund der exponentiellen Skalierung nicht möglich. Für jede mögliche Änderung müssten alle Optionen neu bewertet werden und es müsste sichergestellt sein, dass die jeweilige Haltestelle nicht früher von einer anderen Fahrt erreicht werden kann. Zusätzlich müssten größere Anpassungen des aktuellen Algorithmus vorgenommen werden. Die Pareto-optimalen Routensets würden dann auf drei Kriterien beruhen. Dies könnte entweder durch die Änderung der von RAPTOR verwendeten Tupel in Tripel oder durch die Speicherung von Bags aus Tupeln, wie von Delling et al. [2] angewendet, erfolgen. Darüber hinaus würden zusätzliche Kriterien zu einer Vergrößerung des Pareto-optimalen Sets führen, was einen zusätzlichen Filteralgorithmus erfordert, der die Routen auswählt, die dem Benutzer präsentiert werden.

Als Alternative zur Erhöhung der Anzahl der Kriterien wird in der Praxis häufig ein sogenannter Ex post-Algorithmus, wie von Delling et al. [4] vorgeschlagen, zum Ranking oder Filtern der von RAPTOR zurückgegebenen Ergebnisse verwendet. Mit einem solchen Algorithmus können zum Beispiel nicht realisierbare Routen entfernen werden. Zusätzlich könnte er nicht-intuitive Routen herausfiltern. Sobald RAPTOR eine Route gefunden hat, könnten die folgenden Fahrten der gleichen Linien ausgewertet werden, um T-Routen auszuschließen. Wenn auf einer Linie eine Fahrt angeboten wird, die später abfährt, aber noch genügend Umstiegszeit bietet, um die nächste Fahrt oder das Endziel zu erreichen, würde die ursprüngliche Empfehlung ersetzt werden. Zyklen könnten auf ähnliche Weise identifiziert werden. Durch einfaches Durchlaufen der resultierenden Fahrten können Schleifen identifiziert und entfernt werden. Es ist jedoch nicht immer wünschenswert, alle Zyklen zu entfernen. In einigen Fällen, wie in Abschnitt 3.2 diskutiert, kann es von einem Fahrgast unter bestimmten Umständen nicht als negativ empfunden werden, eine zyklische Route zu nehmen.

5.2 Implementierte Verbesserung

Wie in Abschnitt 4 erwähnt, können beim Rückwärtsrouting weder T-Routen noch Z-Routen auftreten. Dies kann dazu genutzt werden, um von RAPTOR vorgeschlagene nicht-intuitive Routen auszuschließen. Beim Vorwärtsrouting gibt der Algorithmus, wie oben beschrieben, für jede Anzahl von Umstiegen die früheste Ankunftszeit zurück. Wendet man auf diesem Ergebnis ein Rückwärtsrouting an, wird die späteste mögliche Abfahrtszeit zurückgegeben und somit die Reisezeit implizit minimiert.

Um Robustheit zu gewährleisten, muss der Algorithmus mehrfach rückwärts routen, einmal für jede im Pareto-optimalen Set des Vorwärtsroutings enthaltene Fahrt. Diese  Anforderung soll mit einem Beispiel verdeutlicht werden. Ein Passagier, der um 12:00 Uhr abreist, hat zwei Möglichkeiten, sein Ziel zu erreichen. Er kann eine Route mit einem Umstieg wählen die 10 Minuten dauert, oder er kann eine direkte Verbindung nehmen die 15 Minuten dauert. Außerdem gibt es noch eine weitere Verbindung mit einem Umstieg die allerdings nicht von RAPTOR vorgeschlagen wird. Diese fährt um 12:05 ab und dauert ebenfalls 10 Minuten. Beim Rückwärtsrouting um 12:10 Uhr gibt der Algorithmus nur die Route mit einem Umstieg zurück, da dies die einzige Lösung ist, die um (oder vor) 12:10 Uhr ankommt (und nicht später als 12:00 anfängt). Wenn der Algorithmus um 12:15 Uhr rückwärts routet, findet er zwei Routen. Eine ist die Route ohne Umstieg, die andere hat einem Umstieg. Da jedoch 12:15 Uhr als Zielankunftszeit festgelegt ist, schlägt der Algorithmus als Route mit einem Umstieg die Route die um 12:05 Uhr beginnt. Dies ist nicht gewünscht, da der Passagier um 12:00 losfahren möchte. Man sieht also, dass es nicht ausreicht zu einer einzigen Zeit rückwärts zu routen. Der negative Effekt, dass durch das Rückwärtsrouting realisierbare und intuitive Routen entfernt werden könnten, kann vermieden werden, indem für jede Pareto-optimale Route rückwärts geroutet wird. Für jede Iteration werden Routen nur dann zum überarbeiteten Pareto-optimalen Set hinzugefügt, wenn sie eine kürzere Reisezeit, aber die gleiche Anzahl an Umstiegen sowie die gleiche Ankunftszeit haben.

Das oben vorgeschlagene Verfahren, das wir als Multi-RAPTOR (MRAPTOR) nennen, hat einen Einfluss auf die Laufzeit des Algorithmus. Für jede Strecke innerhalb des Pareto-optimalen Sets muss der Algorithmus erneut laufen. Die Gesamtzahl der Durchläufe beträgt daher (N + 1), wobei N die Anzahl der zurückgegebenen Fahrten ist. Die Laufzeit T(MRAPTOR) des MRAPTOR-Algorithmus steigt also linear mit der Zahl von zurückgegebenen Fahrten, und ist T(MRAPTOR) = (N + 1) ·

T(RAPTOR).

6 Experimente

Die Experimente wurden in der IVU-Testumgebung mit einer existierenden Implementierung des Zwei-Kriterien-RAPTOR-Algorithmus durchgeführt [1]. Der verwendete Fahrplan ahmt das Aachener Verkehrsnetz mit einer Datenbank nach, die den Tag der Ausführung, den Vortag und die folgenden drei Tage umfasst. Der Fahrplan eines jeden Tages enthält 1.022 Haltestellen und 22.016 Fahrten.

Um nicht-intuitive Fahrtrouten vor und nach der Änderung des Algorithmus zu identifizieren, wurde ein Skript geschrieben, das eine Reihe von Start- und Zielpaaren abfragt. Um sicherzustellen, dass es möglich ist, die beiden Haltestellen zu verbinden, rief das Skript den RAPTORAlgorithmus auf, bis 10.000 zufällige Paare mit mindestens einer möglichen Route gesammelt wurden. Die Anzahl der vorgeschlagenen Routen pro Start-Ziel-Paar reichte von 1 bis 15, wobei der Durchschnitt etwas über 2 lag.

Zyklische Routen wurden durch die Suche nach sich wiederholenden Stopps innerhalb der abgerufenen Route identifiziert, wie in Abbildung 7 zu sehen ist, die ein besonders drastisches Beispiel für eine vom Skript identifizierte zyklische Route zeigt. Die blaue Markierung (oben links) zeigt den Startpunkt und die grüne Markierung (unten links) das Ziel an. Beim Routing zwischen diesen beiden Haltestellen schlägt der Algorithmus einen großen Umweg vor, der den Fahrgast zu einem Punkt zurückbringt, an dem er bereits gewesen ist.

Des weiteren wird im Folgenden eine Route als schwache T-Route definiert, wenn diese keine T-Route ist aber eine T-Route als Teilroute enthält. Um eine schwache T-Route zu identifizieren, wurde überprüft ob es eine andere Route gibt, die exakt der gleichen Reihenfolge von Linien und Haltestellen folgt und die selbe Ankunftszeit hat, jedoch unterschiedliche Ankunftszeiten an mindestens einer Haltestelle hat.

Diese identifizierten Routen enthalten nicht ausschließlich T-Routen und Z-Routen, sondern auch die Varianten die keinen Einfluss auf die Reisezeit haben. Diese Methode wurde gewählt, da diese von manchen Nutzern dennoch als nicht-intuitiv gesehen werden können (obwohl die Routen manchmal bevorzugt werden können).

Abbildung 7: Zyklische Route die von RAPTOR vorgeschlagen wurde. Der Startpunkt ist die blaue Markierung (oben links) und das Ziel ist die grüne Markierung (unten links).

Weiterhin wurde für die Fahrzeit der Z-Score [6] berechnet, der als Anzahl der Standardabweichungen über oder unter dem Mittelwert definiert ist. In der Statistik werden Z-Scores über 1 als unüblich eingestuft. Daher wurden Routen mit einem Z-Score größer als 1 erfasst, um einen möglichen Zusammenhang zwischen der Reisezeit und nicht-intuitiven Routen zu erkennen.

Ein Vorteil der IVU-Testumgebung ist die Nichteinbeziehung größerer Verkehrsstörungen, die bei der Verwendung von Ist-Daten die Ergebnisse beeinflussen könnten. Da das System Zeitpläne für die Tage um das aktuelle Datum herum lädt, wurde bei Experimenten, die an verschiedenen Tagen durchgeführt wurden, keine identische Datenbank verwendet. Dies schränkt die Reproduzierbarkeit der Experimente etwas ein. Der Ausführungstag hatte jedoch keinen nennenswerten Einfluss auf die Ergebnisse, da der modellierte Zeitplan der IVU sich wiederholt. Mit anderen Worten: Eine Abfrage nach Routen an einem Montag liefert im Wesentlichen die gleichen Routen wie die gleiche Abfrage an einem Dienstag.

Es wurden zwei verschiedene Experimente entworfen. Für das erste Experiment wurde der Satz von 10.000 Verbindungen einmal mit RAPTOR und einmal mit MRAPTOR abgefragt.

Das Datum und die Uhrzeit der Abfahrt wurde innerhalb der vom System geladenen Tage zufällig ermittelt. Jede der abgefragten Verbindungen wurde wie oben beschrieben für T-Routen, zyklische Routen und den Z-Score ausgewertet. Im zweiten Experiment wurde die Anzahl der Verbindungen auf 1.000 reduziert, während die Anzahl der Abfragen für jede Verbindung erhöht wurde. Während im ersten Experiment nur eine Anfrage pro Verbindung gestellt wurde (unter Verwendung einer zufälligen Abfahrtszeit), wurde bei diesem Experiment jede Verbindung in einem 5-Minuten-Intervall zwischen 9:00 Uhr und 9:55 Uhr abgefragt, was zu insgesamt 12.000 Anfragen führte. Während die Abfahrtszeit in diesem Experiment fixiert war, blieb der Reisetag variabel. Diese Methode reduziert die Zufälligkeit und die Varianz aufgrund der Wiederholbarkeit des Fahrplans. Darüber hinaus wurde in beiden Experimenten der Einfluss auf die Laufzeit des angepassten Algorithmus analysiert, wobei die Laufzeit von RAPTOR und MRAPTOR für jede Strecke verglichen wurde.

7 Ergebnisse und Diskussion

Die Experimente zeigen, dass MRAPTOR deutlich weniger Routen vorschlägt als RAPTOR (siehe Tabelle 1). Im ersten Experiment erhielt MRAPTOR etwa 9.000 Routen weniger als RAPTOR. Im zweiten Experiment beträgt die Differenz sogar rund 17.000 Routen. Dieses Ergebnis war zu erwarten, da der aktualisierte Algorithmus darauf abzielt, die Anzahl der nicht-intuitiven Routen zu reduzieren.

Die Reduzierung der Anzahl der Routen führt zu einer messbaren Verbesserung der Qualität der Ergebnisse des Algorithmus. Es ist ein deutlicher Rückgang der Anzahl der zyklischen Routen und der schwachen T-Routen zu beobachten. Beide Experimente zeigen eine große Verbesserung, wenn auch in unterschiedlicher Größenordnung. Der anfängliche RAPTOR-Algorithmus enthielt im ersten Experiment etwa 20% T-Routen und 4% zyklische Routen. MRAPTOR reduziert diese Anteile auf 2; 38% T-Routen und 0; 34% zyklische Routen, d. h. eine Reduzierung um den Faktor 10. Zusätzlich hat sich die Anzahl der Routen mit einem Z-Score >1 mehr als halbiert, d. h. es gibt weniger Variation in der Reisezeit und weniger Routen dauern deutlich länger als der Durchschnitt der Routen.

Im zweiten Experiment schnitt MRAPTOR ebenfalls besser ab. Während RAPTOR einen ähnlichen Anteil an T-Routen und zyklischen Routen wie im ersten Experiment produzierte, konnte mit MRAPTOR der Anteil der zyklischen Routen von 3; 39% auf 1; 69% reduziert werden. Der Anteil der schwachen T-Routen verringerte sich sogar von 19; 16% auf 0; 42%. Dagegen konnte nur ein leichter Rückgang des Anteils der deutlich längeren Routen mit einem Z-Score >1 erreicht werden, der bei Verwendung des MRAPTORs von 12; 83% auf 10; 13% sank.

Offensichtlich zeigt MRAPTOR eine gute Gesamtperformance. Sowohl die Zahl der zyklischen Routen als auch die Zahl der schwachen T-Routen konnten stark reduziert werden. Die von MRAPTOR vorgeschlagenen schwachen T-Routen befinden sich im mittleren Bereich einer Fahrt mit mehr als zwei Umstiegen und haben somit, wie in Abschnitt 3.2 erwähnt, keinen Einfluss auf die Reisezeit. Auch die restlichen zyklischen Routen haben ebenfalls keine Auswirkung auf die Reisezeit, da diese implizit minimiert wird. Da die nicht-intuitiven Routen beim Rückwärtsrouting nicht auftreten können wurde der Anteil der T-Routen und Z-Routen auf 0% reduziert. Während einige der in Abschnitt 5 besprochenen Methoden zu einer Eliminierung aller schwachen T-Routen und zyklischen Routen führen könnten, ließe sich argumentieren, dass es im Interesse des Nutzers ist, die verbleibenden Routen zu behalten. Diese nicht-intuitiven Routen haben keinen Einfluss auf die Gesamtreisezeit und bieten dem Fahrgast eine größere Auswahl an. Die zwei angebotenen Alternativen sind fast gleich, lassen den Fahrgast aber entscheiden, wann und wo er umsteigen möchte.

In beiden Experimenten war nur ein sehr geringer Anteil der Routen (unter 2%) durch einen hohen Z-Score in Kombination mit einer schwachen T-Route bzw. einer zyklischen Route gekennzeichnet. Daher wurde der Z-Score als Indikator verworfen. Diese Unabhängigkeit zwischen den Merkmalen der Routen lässt sich durch die relativ große Anzahl kleiner zyklischer Routen erklären. Diese haben kaum einen Einfluss auf die Reisezeit und führen daher nicht zu einem hohen Z-Score. Tatsächlich waren die meisten Routen mit einem hohen Z-Score Routen ohne Umstiege. Nach den Kriterien der Auswahl von Pareto-optimalen Routen werden Routen mit Umstiegen nur dann vorgeschlagen, wenn sie schneller als direkte Fahrten sind. Daher ist es unwahrscheinlich, dass eine Route mit einer großen Anzahl von Umstiegen einen Z-Score grösser als 1 hat.

Bezüglich der Laufzeit des Algorithmus wurden im Durchschnitt zwei Routen pro Aufruf gefunden. Im Durchschnitt dauerte es in der ersten Version des Algorithmus 268 Millisekunden, bis er beendet war. Mit der erwarteten Laufzeiterhöhung auf (N + 1)
· T(RAPTOR) würde die geschätzte durchschnittliche Laufzeit etwa 804 Millisekunden betragen. Die tatsächliche Laufzeit der überarbeiteten Version ergab eine durchschnittliche Laufzeit von 1035 Millisekunden pro Aufruf. Dies wird wahrscheinlich durch die Datenstruktur des Algorithmus verursacht. Wenn der Fahrplan geladen wird, werden die Fahrten nach aufsteigender Abfahrtszeit sortiert. Das Rückwärtsrouting benötigt aufgrund dieser Struktur mehr Iterationen über die Menge. Die geringe Erhöhung der Laufzeit ist jedoch nicht entscheidend, da der Algorithmus zusätzlich auf mehrere Systeme verteilt und parallelisiert werden kann. Somit muss bei einer Anfrage nicht auf die Terminierung einer anderen Anfrage gewartet werden, sondern kann an ein anderes System geleitet werden. Oftmals ist der Engpass die Verbindung zwischen Endbenutzer und System.

Tabelle 1: Ergebnisse beider Experimente

8 Weitere Verbesserungsoptionen

Zur weiteren Verbesserung des Algorithmus kommen verschiedene Anpassungen infrage, die im Rahmen dieses Projekts nicht implementiert wurden. Einige dieser Möglichkeiten wurden bereits in den Abschnitten 3.1 und 5 erwähnt. Die größte Verbesserung könnte durch Nutzerklassifizierung erreicht werden. Ortega-Tong [10] analysiert, wie Smart Cards, z.B. die in den Niederlanden verwendete OV-Chipkaart, benutzt werden können um Fahrgäste zu klassifizieren. Der Autor teilt die Fahrgäste in mehrere Gruppen ein und unterscheidet dabei zwischen regelmäßigen Nutzern (Studenten, Arbeiter etc.), die in der Regel täglich pendeln, und gelegentlichen Nutzern wie Touristen. So lassen sich typische Routen von Mitgliedern der jeweiligen Gruppen identifizieren. Wenn bekannt ist, zu welcher Gruppe ein Nutzer gehört, kann der Algorithmus diese Information mit zusätzlichen Faktoren wie z. B. dem Zeitpunkt der Abfrage verknüpfen und so Routen vorschlagen die auf den Nutzer zugeschnitten sind, indem er nach Routen sucht, die andere Fahrgästen derselben Gruppe üblicherweise nehmen.

Die Nutzerklassifizierung muss nicht unbedingt implizit erfolgen. Auch die Möglichkeit, ein Profil zu erstellen, in dem der Kunde seine Präferenzen festlegt, kann zu besseren Vorschlägen führen. So könnte er zum Beispiel seine Laufgeschwindigkeit festlegen oder einstellen, dass direkte Fahrten gegenüber Fahrten mit Umstiegen bevorzugt werden sollen.

Eine weitere mögliche Verbesserung wäre die Optimierung der Datenstruktur, speziell im Umfeld der IVU. Die Speicherung der Routen mit aufsteigender Abfahrtszeit ist vorteilhaft für das Vorwärtsrouting. Allerdings muss der Algorithmus beim Rückwärtsrouting über mehr Fahrten iterieren. Eine Kopie des Fahrplans mit absteigenden Abfahrtszeiten würde wahrscheinlich die Zeit für das Rückwärtsrouting verringern, was aber mit einem höheren Speicherplatzbedarf verbunden wäre. Mit dieser Anpassung könnte die Laufzeit des Rückwärtsroutings weiter reduziert und die erwartete Laufzeit, wie in Abschnitt 5 beschrieben, potenziell erreicht werden.

9 Fazit

Dieser Beitrag behandelt das Thema der intuitiven Routenfindung im öffentlichen Verkehr. Da die Präferenzen der Benutzer individuell sind, wären personalisierte Routen eine Möglichkeit, die Intuitivität zu gewährleisten. Die Personalisierung erfordert jedoch eine Benutzerklassifizierung, die den Rahmen des zugrundeliegenden Projekts gesprengt hätte. Daher war eine allgemeine Lösung zu implementieren, die die Mehrheit der Fahrgäste zufrieden stellt. Nach der Identifizierung der beiden Hauptprobleme, die von den Nutzern gemeldet wurden, d. h. T-Routen und Z-Routen, wurden verschiedene Methoden zum Ausschluss dieser Art von Routen analysiert. Einige dieser Methoden sind mit unerwünschten Nebenwirkungen verbunden. Die Hinzunahme der Reisezeit als weiteres Kriterium führt nicht nur zu einer deutlichen Erhöhung der Laufzeit des Algorithmus, sondern vergrößert auch das Pareto-optimale Set. Die Schnelligkeit des Algorithmus ist von entscheidender Bedeutung, wenn von einem System Live-Fahrpläne verwendet werden, da sich diese im Laufe des Tages häufig ändern. RAPTOR kann auf einem sich häufig ändernden Zeitplan ohne jegliche Vorverarbeitung arbeiten und behält dabei eine schnelle Laufzeit bei. Das Hinzufügen eines Algorithmus zum Filtern, Einordnen oder Ausschließen von nicht-intuitiven Routen kann zu anderen nicht-intuitiven Fällen führen, insbesondere wenn der Filter-Algorithmus die meisten oder alle zyklischen Routen entfernt.

Das Rückwärtsrouting auf Basis der Ergebnisse des Vorwärtsroutings ist eine zuverlässige und geeignete Lösung. Mit welcher die nicht-intuitiven Routen durch eine implizite Minimierung der Reisezeit ausgeschlossen werden, wodurch die Laufzeit nur linear erhöht wird, sofern die entsprechenden Datenstrukturen vorliegen. Darüber hinaus erfordert eine solche Anpassung des Algorithmus keine größeren Veränderungen, z. B. die Änderung von Tupeln zu Tripeln, und damit die Überarbeitung des gesamten Algorithmus. Basierend auf den Ergebnissen von zwei Experimenten konnte der Anteil der nicht-intuitiven Routen um den Faktor 10 verringert werden, wobei die Routen, die keine höhere als die notwendige Reisezeit haben, im Set bleiben.

Zusammenfassend lässt sich sagen, dass eine einfache Änderung des Algorithmus zu einer signifikanten Verbesserung des Ergebnisses führt. Da keine Nutzerklassifizierung implementiert wird, kann der Fahrgast seine bevorzugten Routen selbst auswählen, wobei ihm eine geeignete Auswahlgrundlage bereitgestellt wird.

In einer kürzlich veröffentlichten Studie verwenden Delling et al. [2] eine ähnliche Kombination aus Vorwärts- und Rückwärtsrouting, um die Anzahl der verwendeten Kriterien innerhalb eines RAPTORs zu erhöhen und gleichzeitig die Laufzeit relativ gering zu halten. Folglich bietet die Ergänzung eines RAPTORs durch ein zusätzliches Rückwärtsrouting noch mehr Möglichkeiten, als in diesem Beitrag gezeigt wird.

Literatur

[1] Brack, A. “Massiv paralleles pareto-optimales Routing für den Echtzeit-Einsatz auf großen dynamischen Datenmengen”. MA thesis. RWTH Aachen, 2014.

[2] Delling, D., Dibbelt, J., and Pajor, T. “Fast and Exact Public Transit Routing with Restricted Pareto Sets”. In: 2019 Proceedings of the Twenty-FirstWorkshop on Algorithm Engineering and Experiments (ALENEX). SIAM. 2019, pp. 54–65.

[3] Delling, D., Goldberg, A. V., Pajor, T., and Werneck, R. F. “Customizable route planning in road networks”. In: Transportation Science 51.2 (2015), pp. 566–591.

[4] Delling, D., Pajor, T., and Werneck, R. F. “Round-based public transit routing”. In: Transportation Science 49.3 (2014), pp. 591–604.

[5] Dibbelt, J., Pajor, T., Strasser, B., and Wagner, D. “Connection Scan Algorithm”. In: CoRR abs/1703.05997 (2017). arXiv: 1703.05997. URL: http://arxiv.org/abs/1703.05997.

[6] Diez, D. M., Barr, C. D., and Cetinkaya-Rundel, M. OpenIntro statistics. Vol. 2. OpenIntro, 2012, pp. 120–127.

[7] Frank, L., Bradley, M., Kavage, S., Chapman, J., and Lawton, T. K. “Urban form, travel time, and cost relationships with tour complexity and mode choice”. In: Transportation 35.1
(Jan. 2008), pp. 37–54. ISSN: 1572-9435. DOI: 10.1007/s11116-007-9136-6.

[8] Intuition. In MerriamWebster. 2019. URL: https://www.merriam-webster.com/dictionary/intuition#etymology (visited on 06/17/2019).

[9] Niu, L. and Zhuo, G. “An improved real 3D A* algorithm for difficult path finding situation”. In: Proceedings of the International Archives of the Photogrammetry, Remote Sensing
and Spatial Information Sciences 37 (2008).

[10] Ortega-Tong, M. A. “Classification of London’s public transport users using smart card data”. PhD thesis. Massachusetts Institute of Technology, 2013.

[11] Zhan, B. “Three fastest shortest path algorithms on real road networks: Data structures and procedures”. In: Journal of geographic information and decision analysis 1.1 (1997),
pp. 69–82.