Methoden des „Algorithm Engineering“ haben in den vergangenen Jahren zu erheblichen Verbesserungen von Fahrplanauskunftssystemen und Navigationssystemen für den Straßenverkehr geführt, die sich insbesondere in Beschleunigungsfaktoren im Millionenbereich bei der Routenberechnung niederschlagen. Nach dieser rasanten Entwicklung zählt heute die Routenplanung in einem multimodalen Verkehrsnetz zu den größten Herausforderungen der algorithmischen Forschung in diesem Bereich. Dieser Beitrag gibt einen Überblick über die wichtigsten Routenplanungsalgorithmen und schildert die Modellierungsaufgaben und algorithmischen Probleme, die sich bei der multimodalen Routenplanung stellen.

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

1 Einführung

Fahrplanauskunftssysteme (wie der DB Navigator) und Routenplanungssysteme für den Straßenverkehr (wie die Routenplaner in Google-Maps- und Bing-Maps-Routenplaner oder TomTomNavigationssysteme) gehören heute zu den meistbenutzten Informationssystemen überhaupt. Die Nutzer erwarten inzwischen weit umfangreichere Informationen als „nur“ die Berechnung der schnellsten Reiseroute vor Antritt der Reise. Die Berechnung einer neuen Route oder Alternativroute auf Basis der aktuellen Verkehrsbzw. Verspätungslage zu jedem Zeitpunkt während der Reise ist inzwischen eine ebenso naheliegende Anforderung an ein Fahrplanauskunftssystem wie die Einbeziehung anderer Verkehrsmittel als Ergänzung oder Erweiterung des öffentlichen Verkehrs (ÖV). Angesichts neuer alternativer Mobilitätskonzepte werden in Zukunft zunehmend auch Informationen über „echte“ Alternativen irgendwo zwischen fahrplangebundenem öffentlichem Verkehr und Individualverkehr erwartet, man denke an die jüngst angebotenen Fernbuslinien privater Unternehmen, Konzepte gemeinsam genutzter Fahrzeuge wie „Stadtmobil“, moderne Mitfahrdienste wie beispielsweise flinc1 oder die von der Bahn angebotenen Leihfahrradsysteme und Leihautosysteme. Auch wünschen sich die heutigen Nutzer nicht einfach nur eine Berechnung der schnellsten Route, sondern „beste“ Routen, die ihren individuellen Präferenzen und Optimalitätskriterien genügen.

Vorhandene Routenplanungssysteme, wie die vorab genannten, bieten solche Dienste ansatzweise bereits an. Allerdings werden bei der Fahrplanauskunft im ÖV andere Verkehrsmittel nicht gleichberechtigt in die Routenplanung einbezogen, sondern nur für den Anund Abgang zum ÖV berücksichtigt; es findet also keine „echte“ multimodale Routenberechnung2 statt. Ebenso werden während der Reise zwar Verspätungsinformationen gegeben, aber keine echte Alternativroute auf Basis der aktuellen Verspätungslage im ÖV und unter Einbeziehung anderer Mobilitätsanbieter angeboten.

Im Folgenden wird ein Überblick über die neuesten Ergebnisse zur Routenplanung gegeben, die unter Verwendung von Methoden des Algorithm Engineering erzielt wurden. Da die multimodale Routenplanung Fahrplanauskunft und Routenplanung im Straßenverkehr als Teilaspekte beinhaltet, gehen wir zunächt auf die entsprechenden Methoden ein, wobei unser Schwerpunkt auf Arbeiten liegt, an denen die Autorin beteiligt ist. Abschnitt 4 geht dann auf den Stand der Forschung bei der multimodalen Routenplanung genauer ein. Einen umfassenden und weitaus gründlicheren Überblick bieten die Übersichtsartikel [1, 2, 3], wobei [3] auch einen genaueren Vergleich der Effektivität nachfolgend diskutierter Techniken präsentiert.

2 Algorithm Engineering für  Routenplanung

Die algorithmische Grundlagenforschung der letzten 15 Jahre im Bereich der Routenplanung hat zu großen Fortschritten geführt, die sich insbesondere in einem enormen Effizienzgewinn der Routenplanung im Straßenverkehr ausdrücken. Neueste algorithmische Forschungsergebnisse beziehen sich auf deutlich anspruchsvollere und realistischere Szenarien als noch vor fünf Jahren. Sie basieren auf der Methodik des Algorithm Engineering, bei der der gesamte Kreislauf aus Entwurf, Analyse, Implementierung und experimenteller Bewertung von Algorithmen durchlaufen wird und insbesondere die Ergebnisse der Experimente wieder in den Entwurf und die Analyse der Verfahren einbezogen werden. Die theoretische Fundierung besteht darin, dass ein mathematischer Beweis für die Optimalität der berechneten Routen geführt wird. Andererseits wird die Effizienz und Praktikabilität mittels ausgiebiger Evaluationen anhand großer Realweltdatensätze nachgewiesen. Diese Entwicklung wird heute als Erfolgsgeschichte des Algorithm Engineering angesehen, siehe auch [4].

Einerseits haben Methoden aus der algorithmischen Forschung inzwischen Eingang in kommezielle Routenplanungssysteme4 gefunden, andererseits wurden in den letzten Jahren tiefliegende theoretische Einsichten gewonnen, die wiederum zu neuen und schnelleren Routenplanungsalgorithmen geführt haben. Grundidee der hocheffizienten Routenplanungsalgorithmen ist die Ausnutzung vorberechneter Information zur Beschleunigung des klassischen Algorithmus von Dijkstra [5] für die Berechnung kürzester Wege in Graphen.

2.1 Beschleunigungstechniken

Der algorithmische Kern des Routenplanungsproblems besteht in der Berechnung eines kürzesten Weges zwischen zwei ausgezeichneten Knoten in einem Graphen. Dabei sei ein (möglicherweise gerichteter) Graph G = (V, E) mit Knotenmenge V und Kantenmenge E mit |V | = n und |E| = m, sowie ausgezeichnete Knoten s, t ∈ V gegeben. Jede Kante (x, y) habe eine nicht negative Kantenlänge dist(x, y), und die Länge eines Weges sei die Summe seiner Kantenlängen. Zu berechnen ist dann der kürzeste Weg zwischen dem Startknoten s und dem Zielknoten t. Bei der Routenplanung wird in der Regel als Kantenlänge die (mittlere) Fahrzeit gewählt, aber es sind je nach Anwendungsszenario auch andere Metriken wie die geographische Distanz, Kosten, Energieverbrauch oder Anzahl der Umstiege relevant. Dieses klassische Problem kann mittels des Algorithmus von Dijkstra [5] gelöst werden, wobei die Laufzeit von den benutzten Datenstrukturen abhängt. Mit binären Heaps wird eine Laufzeit von O(n + m log n) erreicht [6] beziehungsweise O(m + n log n) mit Fibonacci-Heaps [7]. In der Praxis eignen sich offenbar verallgemeinerte Versionen von binären Heaps am besten [8].

Für große Verkehrsnetze und die Beantwortung vieler Anfragen innerhalb kurzer Zeit ist diese Laufzeitkomplexität allerdings nicht praktikabel. Aus diesem Grund gewinnen sogenannte Beschleunigungstechniken für den Algorithmus von Dijkstra an Bedeutung. Eine Beschleunigungstechnik besteht meistens aus einer zweiphasigen Berechnung. In der ersten, oft aufwändigen, Vorberechnungsphase werden zusätzliche Informationen berechnet. Diese werden in der Anfragephase, welche mit dem (gegebenenfalls modifizierten) Algorithmus von Dijkstra durchgeführt wird, zur Beschleunigung der Berechnung genutzt. Für die Effektivität solcher Techniken sind neben der erzielten Beschleunigung auch der Aufwand für die Vorberechnungsphase und der für die vorberechneten Informationen benötigte Speicherplatz relevant. Dabei ist zu beachten, dass die Speicherung vorberechneter kürzester Wege zwischen allen Knotenpaaren keine Option ist, da der dafür benötigte Speicherplatz für realistische Verkehrsnetze bei weitem zu groß wäre.

Klassische Beschleunigungstechniken, die noch ohne Vorberechnung auskommen, sind die bigerichtete Suche [9] und die zielgerichtete Suche A∗ [10]. Bei der bigerichteten Suche werden simultan eine Vorwärtssuche von s und eine Rückwärtssuche von t aus durchgeführt. Der Algorithmus kann abgebrochen werden, sobald sich Vorwärtsund Rückwärtssuche an einem gemeinsamen Knoten treffen. Die zielgerichtete Suche A∗ benutzt eine Potentialfunktion π, welche für jeden Knoten x  ∈ V  eine untere Schranke für die Distanz dist(x, t) zum Zielknoten t  angibt. Eine modifizierte Version des Algorithmus von Dijkstra priorisiert dann einen Knoten x entsprechend seines Wertes dist(s, x) + π(x), wodurch Knoten, die näher am Zielknoten t liegen, durch die Suche früher berücksichtigt werden. Die Suche wird also in Richtung Zielknoten geleitet. In der Praxis eignet sich als Potentialfunktion die euklidische Distanz.

Eine bessere untere Schranke wird mit der Technik ALT [11] erzielt, die in einer Vorberechnungsphase eine kleine Anzahl von Landmarken aus der Knotenmenge auswählt und für alle Knoten die Distanzen zu diesen Landmarken berechnet. Wie bei A∗ wird dann in der Anfragephase unter Ausnutzung dieser Distanzen und der Dreiecksungleichung für jeden Knoten x eine untere Schranke für dist(x, t) benutzt. Die Effektivität dieser Technik hängt von der Wahl der Landmarken ab. Für Straßengraphen eignen sich am besten Landmarken, die gleichmäßig verteilt am Rand des Graphen liegen [12, 13].

Es existiert eine Fülle weiterer raffinierter und sehr effektiver Beschleunigungstechniken, auf die wir hier nicht näher eingehen möchten. Zu nennen sind als weitere zielgerichtete Techniken geometrische Container [14, 15] und Arc Flags [16, 17] oder die Technik Reach [18, 19], darüber hinaus sogenannte Bounded-Hop-Techniken (BHT) wie Hub Labeling (HL) [20, 21, 22], Transit Node Routing (TNR) [23, 24] und Pruned Highway Labeling [25]. Schießlich sind Kombinationen solcher Techniken intensiv untersucht worden [26, 27]. Einige dieser Techniken wurden speziell für die Routenplanung im Straßenverkehr optimiert, wo sie zu millionenfachen Beschleunigungen geführt haben. In den letzten fünf Jahren wurden Beschleunigungstechniken auch für erweiterte Szenarien weiterentwickelt, etwa für zeitabhängige Fahrzeiten oder die gleichzeitige Berücksichtigung von mehreren Optimierungskriterien. Wir wollen nachfolgend nur zwei weitere Techniken hervorheben, die sich in jüngster Zeit als besonders effektiv für die Routenplanung im Straßenverkehr erwiesen haben.

Ein Paradebeispiel für eine grundlegende Beschleunigungstechnik ist die in [14] für Fahrplangraphen (und unabhängig in [28] für Straßengraphen) vorgeschlagene und später [29, 30] weiter verbesserte Multi-Level-Methode, die unlängst wieder aufgegriffen wurde und zu der aus heutiger Sicht vermutlich praktikabelsten Vorgehensweise bei der Routenplanung im Straßenverkehr geführt hat [31, 32]. Diese Technik beruht auf einer zweistufigen Vorberechnung, in der zunächst der Graph partitioniert wird und auf Basis der Partition ein (möglicherweise aus mehreren Leveln bestehender) Overlay-Graph konstruiert wird, in dem Wege zwischen Randknoten der Zerlegung durch Abkürzungskanten ersetzt werden. Mit dem Algorithmus von Dijkstra wird die Anfragebearbeitung dann in diesem Overlay-Graph durchgeführt. Diese Technik zeichnet sich dadurch aus, dass ein Teil der Vorberechnung unabhängig von der Metrik (etwa fahrzeugabhängigen Reisezeiten) ist, was eine individuelle Anpassung der vorberechneten Information sehr effizient macht.

Eine weitere wichtige Beschleunigungstechnik ist die sehr elegante Vorgehensweise Contraction Hierarchy (CH) [33, 34]. Kernidee dieser Beschleunigungstechnik ist eine Vorberechnung, in der eine systematische Knotenersetzung durchgeführt wird, bei der sukzessiv für zwei aufeinanderfolgende Kanten eine Abkürzungskante eingefügt wird. Die Reihenfolge der Knoten wird heuristisch etwa entsprechend der Wichtigkeit der Knoten gewählt und hat Einfluss auf die Effektivität. Für die Anfragebearbeitung wird in dem um die Abkürzungskanten angereicherten Graphen eine modifizierte, bigerichtete Version des Algorithmus von Dijkstra ausgeführt, wobei jeweils nur Kanten zu Knoten höherer Ordnung (entsprechend der gewählten Reihenfolge) besucht werden. Inzwischen wurde diese Technik für verschiedene Szenarien angewendet, die größten Fortschritte sind allerdings im Bereich der Routenplanung im Straßenverkehr zu verzeichnen.

2.2 Theoretische Fundierung

Theoretische Ergebnisse zur Komplexität von Beschleunigungstechniken und zu dem durch einzelne Beschleunigungstechniken erreichbaren Effizienzgewinn wurden erst in jüngster Vergangenheit erzielt. Zu den ersten theoretischen Einsichten in diesem Gebiet gehören Komplexitätsaussagen zu allen gängigen Beschleunigungstechniken über das jeweilige Problem eine Vorberechnungen mit optimalem Beschleunigungseffekt durchzuführen [35, 36, 37]. Demgegenüber liefern die Arbeiten [38, 39, 40] erste Garantien und entsprechende theoretische Erklärungen für den durch Beschleunigungstechniken erzielten Effizienzgewinn. Die bewiesenen Garantien beruhen auf dem dort eingeführten Parameter Highway Dimension, der eine Beziehung zwischen dem Effizienzgewinn von Beschleunigungstechniken und der hierarchischen Struktur der betrachteten Graphen herstellt. Besonders hervorzuheben ist in diesem Zusammenhang, dass diese Einsichten wiederum zur Entwicklung der bereits erwähnten Technik HL geführt haben, die unter den heute bekannten Beschleunigungstechniken die höchste Beschleunigung auf Straßengraphen erzielt, wenn auch unter Verwendung von sehr viel Speicherplatz für die vorberechnete Information. Während bei den auf der Highway Dimension basierenden Garantien die Metrik der Kantengewichte in die Analyse eingeht, ist es in [41] erstmals gelungen, metrikunabhängige Garantien für die Effizienz der Beschleunigungstechnik CH zu beweisen.

3 Fahrplanauskunft

Gegenüber der Routenplanung im Straßenverkehr zeigen die wichtigsten Arbeiten zur Anwendung von Beschleunigungstechniken auf Fahrplangraphen [14, 42, 43, 44], dass die erzielte Beschleunigung im Bereich der Fahrplanauskunft nicht annährend so groß ist. Dies liegt nicht allein an der deutlich komplexeren Modellierungsaufgabe, die sich, insbesondere wegen der durch die Fahrplanbindung öffentlicher Verkehrssysteme induzierten Zeitabhängigkeit, hinter der Formulierung von Fahrplanauskunft als Berechnung von kürzesten Wegen in Graphen verbirgt [45, 46]. Es hat sich auch gezeigt, dass die Struktur der resultierenden Fahrplangraphen deutlich anders geartet ist als bei Straßengraphen. Straßengraphen sind dünner als Fahrplangraphen und in gewisser Weise fast planar. Zudem gelten gewisse Lokalitätseigenschaften, die die Routenberechnung in Straßengraphen einfacher machen, in der Fahrplanauskunft nicht mehr [47]. Eine Suche im Fahrplangraph muss typischerweise von einem Bahnhof aus sowohl Kanten zu geographisch nahe gelegenen Bahnhöfen als auch (induziert durch Fernverbindungen) zu weiter entfernten Bahnhöfen durchsuchen, während in einem Straßengraph die meisten, wenn nicht sogar alle Kanten von einer Kreuzung aus nur zu geographisch nahe gelegenen Kreuzungen führen.

Meistens wird in der Fahrplanauskunft die Reisezeit als wichtigstes Optimierungskriterium betrachtet und als weiteres Kriterium die Anzahl der Umstiege. Die gleichzeitige Optimierung von mehreren Kriterien führt zu einer meistens sehr aufwendigen Pareto-Optimierung [48]. Schließlich ist in Hinblick auf eine Fahrplanauskunft zur Reisezeit auf Basis der aktuellen Verkehrslage auch die schnelle Aktualisierung der vorberechneten Informationen, beziehungsweise die Robustheit der Vorberechnung, relevant. Insofern können auch die neuesten Arbeiten zur Routenplanung im ÖV noch nicht als das Ende der Entwicklung angesehen werden, da sie nicht alle diese Aspekte berücksichtigen.

Die bei der Firma Google entwickelte Technik Transfer  Patterns (TP)  [49] basiert auf der  Idee, dass viele Fahrverbindungen die selbe Abfolge von Umstiegen beinhalten. Diese Abfolgen können für alle Startund Zielknoten vorberechnet und dann bei der Anfragebearbeitung ausgenutzt werden. TP arbeiten in der Praxis offensichtlich sehr effektiv, auch wenn die Vorberechnungszeit im Bereich von mehreren Tagen oder sogar Wochen liegt. Das Verfahren kann neben der Reisezeit auch die Anzahl von Umstiegen berücksichtigen und auf die Beantwortung von „Profilanfragen“, bei denen für ein Intervall möglicher Abfahrtszeiten alle fahrzeitminimalen Routen zu berechnen sind, angewendet werden. Allerdings kann bei TP nicht für alle Anfragen Optimalität der Auskunft garantiert werden.

Demgegenüber beantwortet das in [50] vorgestellte Verfahren Round-bAsed Public Transit Optimized Router (RAPTOR) Profilanfragen nachweislich optimal. RAPTOR arbeitet in Runden, wobei (wie bei der dynamischen Programmierung) in der i-ten Runde die Verbindung mit frühester Ankunftszeit und genau i Umstiegen berechnet wird. Das Verfahren kann gut parallelisiert und auch auf weitere Optimierungskriterien erweitert werden.

Wie im vorherigen Kapitel beschrieben, beruhen bisherige Beschleunigungstechniken typischerweise auf dem Algorithmus von Dijkstra. Erst kürzlich wurde gezeigt, dass alternative Verfahren auf Fahrplandaten effizienter arbeiten. Der in [51] vorgeschlagene Connection Scan Algorithmus (CSA) berechnet Routen mit kürzester Reisezeit mittels einer einfachen Abfragetechnik auf Basis geeigneter Datenstrukturen und den darin abgelegten atomaren Verbindungsdaten. Aufgrund seiner Einfachheit und Effizienz bietet dieser Algorithmus eine sehr gute Grundlage für die Betrachtung anspruchsvollerer Szenarien in der Fahrplanauskunft und darüber hinaus. Es gibt bereits erste Ansätze, wie CSA auf die Berechnung verspätungsrobuster Routen erweitert werden kann. Diese basieren auf der Berechnung von „Reiseplänen“, welche dem Reisenden für eine Abreisezeit Alternativen aufzeigen, die im Laufe der Reise, etwa bei Verspätungen, relevant werden könnten. Ein solcher Reiseplan ist also ein Entscheidungsgraph, der dem Reisenden Routenalternativen aufzeigt. Eine jüngst in [52] beschriebene Weiterentwicklung von CSA zeigt zudem, dass CSA auch für die gleichzeitige Betrachtung mehrerer Kriterien gut geeignet ist.

4 Multimodale Routenplanung

Die Erforschung und Entwicklung von Verfahren für die multimodale Routenberechnung steht trotz erster Erfolge noch am Anfang. Zunächst ist festzuhalten, dass die Fahrplanauskunft im ÖV bereits eine multimodale Komponente beinhaltet, da ÖV-Verbindungen typischerweise auch Fußwege enthalten. Allerdings werden diese bei bisherigen Verfahren durch Transferkanten zwischen nahe beieinander liegenden Stationen im Fahrplangraphen fest kodiert. Die erste große Herausforderung bei der multimodalen Routenplanung liegt in der geeigneten Modellierung aller Verkehrsmodi in einem Graph. Es zeigt sich allerdings auch, dass im Gegensatz zur Routenplanung im Straßenverkehr die Festlegung was die „beste“ Route im multimodalen Verkehrsnetz ist weniger eindeutig und deren Berechnung ungleich schwieriger ist. Einerseits bekommen individuelle Präferenzen der Reisenden, etwa die Einschränkung auf bestimmte Verkehrsmittel (beispielsweise nur ÖV-Verkehrsmittel, Fußwege und Fahrrad) oder die Einschränkung auf bestimmte Abfolgen von Verkehrsmitteln (beispielsweise PKW, Taxi, Fahrrad und Fußwege nur zu Beginn und Ende der Reise), eine größere Bedeutung. Andererseits ergibt sich eine noch größere Anzahl relevanter Optimierungskriterien, neben der Reisezeit beispielsweise die Anzahl der Wechsel zwischen Verkehrsmodi, die Länge der Fußwege, die Wartezeiten an Stationen oder die Kosten einer Verbindung, was eine aufwendige Pareto-Optimierung erfordert.

4.1 Graphenmodelle für multimodale Routenplanung

Um ein multimodales Verkehrsnetz als einen Graphen zu modellieren, kann man zunächst die verschiedenen Verkehrsnetze als einzelne Graphen repräsentieren und diese dann durch Kanten (oder Knoten) verbinden, die die Wechsel zwischen den Verkehrmodi abbilden. Naheliegenderweise kann man den Straßenverkehr als Graph mit zeitabhängigen Fahrzeiten und den öffentlichen Verkehr als zeitabhängigen Fahrplangraph darstellen [53, 54, 55, 56]. Einschränkungen auf bestimmte Verkehrsmittel beziehungsweise die Bevorzugung bestimmter Verkehrsmittel können dabei durch Strafkosten, die in die Zielfunktion integriert werden, implementiert werden [57, 58, 59]. Deutlich eleganter ist allerdings die im nachfolgenden Abschnitt beschriebene Idee, Einschränkungen an die Reiseverläufe mittels regulärer Sprachen bzw. endlicher Automaten auszudrücken.

4.2 Kürzeste Wege mit Einschränkungen

In [60] wird ein mathematisch sauberer Ansatz vorgestellt um Einschränkungen auf bestimmte Abfolgen von Verkehrsmodi zu begegnen, der zur Berechnung kürzester Wege mit LabelConstraints führt. Dazu wird die Menge der Verkehrsmodi durch ein Alphabet repräsentiert und die Kanten des Graphen mit entsprechenden Labeln aus dem Alphabet versehen. Einschränkungen auf bestimmte Abfolgen von Verkehrsmodi können dann als Sprache über dem Alphabet angesehen werden. Entsprechend muss bei der Anfragebearbeitung sichergestellt werden, dass die berechnete Route einem Wort aus der vorgegebenen Sprache entspricht. Für reguläre Sprachen kann die Berechnung eines kürzesten Weges mit Einschränkungen wiederum durch eine Variante des Algorithmus von Dijkstra gelöst werden [60] und zwar indem als zugrunde liegender Graph der Produktgraph aus dem endlichen Automat zur regulären Sprache und dem Graph zum Verkehrsnetz betrachtet wird. Erfreulicherweise reichen die Ausdrucksmöglichkeiten regulärer Sprachen für sinnvolle Einschränkungen in der multimodalen Routenplanung aus [61].

4.3 Multimodale Routenplanung in eingeschränkten Szenarien

In [62] werden die ersten systematischen Untersuchungen zur Anwendung der klassischen Beschleunigungstechniken auf die Berechnung kürzester Wege mit Einschränkungen in multimodalen Szenarien vorgestellt. Die Arbeit [53] stellt mit Access-Node Routing (ANR) eine erste fortgeschrittene und maßgeschneiderte Beschleunigungstechnik für die Berechnung einer Route mit frühester Ankunftszeit vor, die allerdings nur ein eingeschränktes, vorab fixiertes multimodales Verkehrsnetz betrachtet. Dabei wird eine formale Sprache benutzt, die die Nutzung von PKW nur zu Beginn und am Ende der Reise erlaubt. ANR benutzt vorberechnete Zugangsknoten in das öffentliche Verkehrsnetz und arbeitet ähnlich wie die in Abschnitt 2.1 erwähnten Techniken TNR und BHT. Alternativ baut die in [55] vorgeschlagene Methode State-Dependent ALT (SALT) auf der Beschleunigungstechnik ALT auf. ANR und ALT wurden beide auf größeren (aber unterschiedlichen) Realweltdatensätzen evaluiert und liefern bereits deutliche Beschleunigungen, die jedoch noch weit entfernt sind von den bei der Routenplanung im Straßenverkehr oder der Fahrplanauskunft erreichbaren Faktoren. Zudem sind beide Ansätze nur für Szenarien anwendbar, bei denen die Einschränkungen an die Abfolge der Verkehrsmodi vorab fixiert ist.

4.4 Nutzerabhängige multimodale Routenplanung

Deutlich weniger restriktiv arbeitet das auf CH basierende Verfahren User-Constrained Contraction Hierarchies (UCCH) [63], das die Festlegung von Einschränkungen dem Reisenden überlässt. Erst zur Anfragezeit müssen bei UCCH die gewünschten Einschränkungen an die Abfolge von Verkehrsmodi festgelegt werden. Neben dem Vorteil der allgemeineren Anwendbarkeit erreicht UCCH bei ähnlich guter Beschleunigung wie ANR (getestet auf den gleichen Realweltdatensätzen) eine deutlich niedrigere Vorberechnungszeit und einen geringeren Speicherplatz als ANR. Wie bei ANR und SALT wird aber nur die Berechnung einer Route mit frühester Ankunftszeit unterstützt.

4.5 Multikriterielle multimodale Routenplanung

Soll nicht allein die Reisezeit berücksichtigt werden, so ist nicht klar ob angesichts der Vielzahl relevanter Kriterien die Wahl der Einschränkungen an die Abfolge von Verkehrsmodi wirklich dem Nutzer eines Auskunftssystems überlassen werden kann. Was als „beste“ Route angesehen wird, spielt bei der multimodalen Routenplanung eine noch wichtigere Rolle als bei der Routenplanung im Straßenverkehr oder der Fahrplanauskunft. Neben den dort relevanten Kriterien treten Aspekte, die von den individuellen Präferenzen der Reisenden abhängen, noch deutlicher in den Vordergrund. Es ist schwierig gegeneinander abzuwägen, einen wie langen Fußweg der Reisende zugunsten weniger Umstiege in Kauf nimmt oder einen wie großen Umweg (und entsprechend verlängerte Reisezeit) ein Reisender akzeptiert, um einen Fußweg zu vermeiden. Neben allen Schwierigkeiten und Herausforderungen, die sich gegenüber der Routenplanung im Straßenverkehr bereits bei der Fahrplanauskunft stellen, beinhaltet die multimodale Routenplanung also nicht nur eine komplexere Modellierungsaufgabe, sondern muss auch als inhärent multikriterielles Optimierungsproblem angegangen werden.

Erste Ansatzpunkte zur Betrachtung mehrerer Kriterien in der multimodalen Routenberechnung wurden erst in neuesten Arbeiten präsentiert. In [64] wird zur Beschleunigung der Routenberechnung das für die Fahrplanauskunft entwickelte Verfahren RAPTOR erweitert. Experimente zeigen, dass die Anzahl an Pareto-optimalen Routen in Realweltszenarien bereits bei der Betrachtung von drei oder vier Kriterien wie Reisezeit, Anzahl Transfers, Länge von Fußwegen und Taxikosten bei weitem zu groß ist, was sich in einer nicht akzeptablen Berechnungszeit niederschlägt. Zudem möchte ein Nutzer nicht 30 oder 40 Pareto-optimale Routen zur Auswahl gestellt bekommen. Deshalb wird eine Methode vorgeschlagen, die mittels Fuzzy-Logik [65] zur Berechnungszeit die Menge Pareto-optimaler Routen auf eine überschaubare Anzahl von Routen einschränkt. Die experimentelle Evaluation rechtfertigt diese Einschränkung, da offenbar alle relevanten Pareto-optimalen Routen dabei ausgewählt werden. Eine ähnliche Sichtweise wird in der Arbeit [66] vertreten, in der nachgewiesen wird, dass sich viele der Pareto-optimalen Routen entweder nur unwesentlich voneinander unterscheiden oder bei genauer Betrachtung nicht sinnvoll sind.

5 Ausblick

Im letzten Abschnitt wurden die wesentlichen algorithmischen Herausforderungen bei der multimodalen Routenplanung angesprochen und es ist festzuhalten, dass bisher nur erste Ansätze zu deren Bewältigung vorliegen. Orientiert man sich an den Erfolgen, die dank der algorithmischen Grundlagenforschung vor allem im Bereich der Routenplanung im Straßenverkehr erzielt wurden, so darf man in den nächsten Jahren auch für die multimodale Routenplanung große Fortschritte erwarten. Mit den in Abschnitt 2 beschriebenen Techniken steht uns heute ein mächtiger algorithmischer Methodenapparat zur Verfügung, der insbesondere auf profunden theoretischen Einsichten basiert. Für die Umsetzung dieser Methoden in praktikable Routenplanungsverfahren für multimodale Szenarien wird neben weiterer Grundlagenforschung aber auch die Verfügbarkeit von Realweltdatensätzen und der Austausch mit Verkehrsanbietern und Anwendern wichtig sein.

Literatur

[1]    Delling, D.; Sanders, P.;  Schultes, D.;  Wagner, D.:  Engineering  Route  Planning Algorithms.  In: Lerner, J. (Hrsg.) ; Wagner, D. (Hrsg.) ; Zweig, K. A. (Hrsg.): Algorithmics of Large and Complex Networks LNCS 5515. Springer, 2009, S. 117–139

[2]    Sommer, C.: Shortest-Path Queries in Static Networks. http://www.sommer.jp/ spq-survey.htm. Version: 2012

[3]    Bast, H. ; Delling, D. ; Goldberg, A. V. ; Müller–Hannemann, M. ; Pajor, T.; Sanders, P. ; Wagner, D. ; Werneck, R. F.: Route Planning in Transportation Networks. Technical Report MSR-TR-2014-4. http://research.microsoft.com/apps/ pubs/default.aspx?id=207102. Version: 2014

[4]    Delling, D. ; Goldberg, A. V. ; Werneck, R. F.: Shortest Paths in Road Networks: From Practice to Theory and Back. In: Sanders, P. (Hrsg.) ; Wagner, D. (Hrsg.); Algorithm Engineering. it—Information Technology 53 (2011), S. 294–301

[5]    Dijkstra, E. W.: A Note on Two Problems in Connexion with Graphs. In: Numerische Mathematik 1 (1959), S. 269–271

[6]    Williams, J.W.J.: Algorithm 232: Heapsort. In: Journal of the ACM 7 (1964), June, Nr. 6, S. 347–348

[7]    Fredman, M. L. ; Tarjan, R. E.: Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. In: Journal of the ACM 34 (1987), Nr. 3, S. 596–615

[8]    Cherkassky, B. V. ; Goldberg, A. V. ; Radzik, T.: Shortest paths algorithms. In: Mathematical Programming, Series A 73 (1996), S. 129–174

[9]    Dantzig, G. B.: Linear Programming and Extensions. Princeton University Press, 1962

[10]    Hart, P.  E. ; Nilsson, N. ; Raphael, B.:  A Formal  Basis for the Heuristic Determination  of Minimum Cost Paths. In: IEEE Transactions on Systems Science and Cybernetics  4 (1968), S. 100–107

[11]    Goldberg, A. V. ; Harrelson, C.: Computing the Shortest Path: A* Search Meets Graph Theory. In: Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA’05), SIAM, 2005, S. 156–165

[12]    Goldberg, A. V. ; Werneck, R. F.: Computing Point-to-Point Shortest Paths from External Memory. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX’05), SIAM, 2005, S. 26–40

[13]    Efentakis, A. ; Pfoser, D.: Optimizing Landmark-Based Routing and Preprocessing. In: Proceedings of the 6th ACM SIGSPATIAL International Workshop on Computational Transportation Science, ACM Press, 2013, 25:25–25:30

[14]    Schulz, F. ; Wagner, D. ; Weihe, K.: Dijkstra’s Algorithm On-Line: An Empirical Case Study from Public Railroad Transport. In: ACM Journal of Experimental Algorithmics 5 (2000), Nr. 12, S. 1–23

[15]    Wagner, D.; Willhalm, T.; Zaroliagis, C.: Geometric Containers for Efficient Shortest-Path Computation. In: ACM Journal of Experimental Algorithmics 10 (2005), Nr. 1.3, S. 1–30

[16]    Lauther, U.: An Experimental Evaluation of Point-To-Point Shortest Path Calculation on Roadnetworks with Precalculated Edge-Flags. In: Demetrescu, C. (Hrsg.) ; Goldberg, A. V. (Hrsg.) ; Johnson, D. S. (Hrsg.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge Bd. 74. American Mathematical Society, 2009, S. 19–40

[17]    Hilger, M. ; Köhler, E. ; Möhring, R. H. ; Schilling, H.:  Fast  Point-to-Point  Shor    test Path Computations with Arc-Flags. In: Demetrescu, C. (Hrsg.) ; Goldberg, A. V. (Hrsg.) ; Johnson, D. S. (Hrsg.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge Bd. 74. American Mathematical Society, 2009, S. 41–72

[18]    Gutman, R. J.: Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX’04), SIAM, 2004, S. 100–111

[19]    Goldberg, A. V. ; Kaplan, H. ; Werneck, R. F.: Reach for A*: Shortest Path Algorithms with Preprocessing. In: Demetrescu, C. (Hrsg.) ; Goldberg, A. V. (Hrsg.); Johnson, D. S. (Hrsg.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge Bd. 74. American Mathematical Society, 2009, S. 93–139

[20]    Abraham, I. ; Delling, D. ; Goldberg, A. V. ; Werneck, R. F.: A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks. In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA’11) LNCS 6630, Springer, 2011, S. 230–241

[21]    Abraham, I. ; Delling, D. ; Goldberg, A. V. ; Werneck, R. F.: Hierarchical Hub Labelings for Shortest Paths. In: Proceedings of the 20th Annual European Symposium on Algorithms (ESA’12) LNCS 7501, Springer, 2012, S. 24–35

[22]    Delling, D. ; Goldberg, A. V. ; Werneck, R. F.: Hub Label Compression. In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13) LNCS 7933, Springer, 2013, S. 18–29

[23]    Bast, H. ; Funke, S. ; Sanders, P. ;  Schultes,  D.:  Fast  Routing in Road Networks  with Transit Nodes. In: Science 316 (2007), Nr. 5824, S. 566

[24]    Bast, H. ; Funke, S. ; Matijevic, D.: Ultrafast Shortest-Path  Queries  via  Transit Nodes. In: Demetrescu, C. (Hrsg.) ; Goldberg, A. V. (Hrsg.) ; Johnson, D. S. (Hrsg.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge Bd. 74. American Mathematical Society, 2009, S. 175–192

[25]    Akiba, T. ; Iwata, Y. ; Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: SIGMOD, 2013, S. 349–360

[26]    Holzer, M. ; Schulz, F. ; Wagner, D. ; Willhalm, T.: Combining Speed-up Techniques for Shortest-Path Computations. In: ACM Journal of Experimental Algorithmics 10 (2006), Nr. 2.5, S. 1–18

[27]    Bauer, R. ;  Delling,  D.  ;  Sanders,  P.  ;  Schieferdecker,  D.  ;  Schultes, D.  ;  Wag ner, D.: Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm. In: ACM Journal of Experimental Algorithmics 15 (2010), Nr. 2.3, S. 1–31

[28]    Jung, S. ; Pramanik, S.: An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps. In: IEEE Transactions on Knowledge and Data Engineering 14 (2002), Nr. 5, S. 1029–1046

[29]    Schulz, F. ; Wagner, D. ; Zaroliagis, C.: Using Multi-Level Graphs for Timetable Information in Railway Systems. In: Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX’02) LNCS 2409, Springer, 2002, S. 43–59

[30]    Holzer, M. ; Schulz, F. ; Wagner, D.: Engineering Multilevel Overlay Graphs for Shortest-Path Queries. In: ACM Journal of Experimental Algorithmics 13 (2008), Nr. 2.5, S. 1–26

[31]    Delling, D. ; Goldberg, A. V. ; Pajor, T. ; Werneck, R. F.: Customizable Route Planning. In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA’11) LNCS 6630, Springer, 2011, S. 376–387

[32]    Delling, D. ; Werneck, R. F.: Faster Customization of Road Networks. In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13) LNCS 7933, Springer, 2013, S. 30–42

[33]    Geisberger, R. ; Sanders, P. ; Schultes, D. ; Delling, D.: Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA’08) LNCS 5038, Springer, June 2008, S. 319–333

[34]    Geisberger, R. ; Sanders, P. ; Schultes, D. ; Vetter, C.:  Exact  Routing  in  Large Road Networks Using Contraction Hierarchies. In: Transportation Science 46 (2012), Nr. 3, S. 388–404

[35]    Bauer, R. ; Columbus, T. ; Katz, B. ; Krug, M. ; Wagner, D.: Preprocessing Speed-Up Techniques is Hard. In: Proceedings of the 7th Conference on Algorithms and Complexity (CIAC’10) LNCS 6078, Springer, 2010, S. 359–370

[36]    Bauer, R. ; D’Angelo, G. ; Delling, D. ; Schumm, A. ; Wagner, D.: The Shortcut Problem – Complexity and Algorithms. In: Journal of Graph Algorithms and Applications 16 (2012), Nr. 2, 447–481

[37]    Bauer, R. ; Baum, M. ; Rutter, I. ; Wagner, D.: On the Complexity of Partitioning Graphs for Arc-Flags. In: Journal of Graph Algorithms and Applications 17 (2013), Nr. 3, 265–299

[38]    Abraham, I. ; Fiat, A. ; Goldberg, A. V. ; Werneck, R. F.: Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. In: Proceedings of the 21st Annual ACM–SIAM Symposium on Discrete Algorithms (SODA’10), SIAM, 2010, S. 782–793

[39]    Abraham, I. ; Delling, D. ; Fiat, A. ; Goldberg, A. V. ; Werneck,  R.  F.:  VC Dimension and Shortest Path Algorithms. In: Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP’11) LNCS 6755, Springer, 2011, S. 690–699

[40]    Babenko, M. ; Goldberg, A. V. ; Gupta,  A. ; Nagarajan, V.:  Algorithms for Hub   Label Optimization. In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP’13) LNCS 7965, Springer, 2013, S. 69–80

[41]    Bauer, R. ; Columbus, T. ; Rutter, I. ; Wagner, D.: Search-Space Size in Contraction Hierarchies. In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP’13) LNCS 7965, Springer, 2013, S. 93–104

[42]    Berger, A. ; Delling,  D.  ;  Gebhardt,  A.  ;  Müller–Hannemann,  M.:  Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected. In: Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’09) Bd. 12, OASIcs, 2009

[43]    Geisberger, R.: Contraction of Timetable Networks with Realistic Transfers. In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA’10) LNCS 6049, Springer, 2010, S. 71–82

[44]    Bauer, R, ; Delling, D. ; Wagner,  D.:  Experimental Study on Speed-Up Techniques    for Timetable Information Systems. In: Networks 57 (2011), Nr. 1, S. 38–52

[45]    Müller–Hannemann, M. ; Schulz, F. ; Wagner, D. ; Zaroliagis, C.: Timetable Information: Models and Algorithms. In: Algorithmic Methods for Railway Optimization LNCS 4359. Springer, 2007, S. 67–90

[46]    Pyrga, E. ; Schulz, F. ;  Wagner,  D.  ;  Zaroliagis,  C.:  Efficient  Models  for  Timetable Information in Public Transportation Systems. In: ACM Journal of Experimental Algorithmics 12 (2008), Nr. 2.4, S. 1–39

[47]    Bast, H.: Car or Public Transport – Two Worlds. In: Efficient Algorithms LNCS 5760. Springer, 2009, S. 355–367

[48]    Disser, Y. ; Müller–Hannemann, M. ; Schnee, M.: Multi-Criteria Shortest Paths in Time-Dependent Train Networks. In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA’08) LNCS 5038, Springer, S. 347–361

[49]    Bast, H. ; Carlsson, E. ; Eigenwillig,  A.  ;  Geisberger,  R.  ;  Harrelson,  C.  ;  Raychev, V. ; Viger, F.: Fast Routing in Very Large Public Transportation Networks using Transfer Patterns. In: Proceedings of the 18th Annual European Symposium on Algorithms (ESA’10) LNCS 6346, Springer, 2010, S. 290–301

[50]    Delling, D. ; Pajor, T. ; Werneck, R. F.: Round-Based Public Transit Routing. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX’12), SIAM, 2012, 130–140

[51]    Dibbelt, J. ; Pajor, T. ; Strasser, B. ; Wagner, D.: Intriguingly  Simple  and  Fast Transit Routing. In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13) LNCS 7933, Springer, 2013, S. 43–54

[52]    Strasser, B. ; Wagner, D.: Connection Scan Accelerated. In: Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX’14), SIAM, 2014, S. 125– 137

[53]    Delling, D. ; Pajor, T. ; Wagner, D.: Accelerating Multi-Modal Route Planning by Access-Nodes. In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA’09) LNCS 5757, Springer, 2009, S. 587–598

[54]    Delling, D. ; Pajor,  T. ; Wagner,  D. ; Zaroliagis, C.:   Efficient Route Planning in Flight Networks. In: Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’09), Bd. 12, OASIcs, 2009

[55]    Kirchler, D. ; Liberti, L. ; Pajor, T. ; Calvo, R. W.: UniALT for Regular Language Constraint Shortest Paths on a Multi-Modal Transportation Network. In: Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’11) Bd. 20, OASIcs, 2011

[56]    Kirchler, D. ; Liberti, L. ; Calvo, R. W.: A Label Correcting Algorithm for the Shortest Path Problem on a Multi-Modal Route Network. In: Proceedings of the 11th International Symposium on Experimental Algorithms (SEA’12) LNCS 7276, Springer, 2012, S. 236–247

[57]    Aifadopoulou, G. ; Ziliaskopoulos, A. ; Chrisohoou, E.:  Multiobjective  Optimum Path Algorithm for Passenger Pretrip Planning in Multimodal Transportation Networks. In: Journal of the Transportation Research Board 2032 (2007), Nr. 1, S. 26–34

[58]    Antsfeld, L. ; Walsh, T.: Finding Multi-criteria Optimal Paths in Multi-modal Public Transportation Networks using the Transit Algorithm. In: Proceedings of the 19th ITS World Congress, 2012

[59]    Modesti, P. ; Sciomachen, A.: A utility measure for  finding  multiobjective  shortest paths in urban multimodal transportation networks. In: European Journal of Operational Research 111 (1998), Nr. 3, S. 495–508

[60]    Barrett, C. ; Jacob, R. ; Marathe, M. V.: Formal-Language-Constrained Path Problems. In: SIAM Journal on Computing 30 (2000), Nr. 3, S. 809–837

[61]    Barrett, C. ; Bisset, K.  ;  Jacob,  R.  ;  Konjevod,  G.  ;  Marathe,  M.  V.:  Classical and Contemporary Shortest Path Problems in Road Networks: Implementation and Experimental Analysis of the TRANSIMS Router. In: Proceedings of the 10th Annual European Symposium on Algorithms (ESA’02) LNCS 2461, Springer, 2002, S. 126–138

[62]    Barrett, C.  ;  Bisset,  K.  ;  Holzer,  M.  ;  Konjevod,  G.  ;  Marathe,  M.  V.  ;  Wagner, D.: Engineering Label-Constrained Shortest-Path Algorithms. In: Demetrescu, C. (Hrsg.) ; Goldberg, A. V. (Hrsg.) ; Johnson, D. S. (Hrsg.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge Bd. 74. American Mathematical Society, 2009,
S. 309–319

[63]    Dibbelt, J. ; Pajor, T. ; Wagner, D.:  User-Constrained  Multi-Modal  Route  Planning. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX’12), SIAM, 2012, S. 118–129

[64]    Delling, D. ; Dibbelt, J. ; Pajor, T. ; Wagner, D. ; Werneck, R. F.: Computing Multimodal Journeys in Practice. In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13) LNCS 7933, Springer, 2013, S. 260–271

[65]    Zadeh, L. A.: Fuzzy Logic. In: IEEE Computer 21 (1988), Nr. 4, S. 83–93

[66]    Bast, H. ; Brodesser, M. ; Storandt, S.: Result Diversity for Multi-Modal Route Planning. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’13) Bd. 33, OASIcs, 2013