Dieser Beitrag stellt einen neuartigen Ansatz zur Berechnung barrierefreier intermodaler Türzu-Tür-Verbindungen vor. Die Besonderheit des Ansatzes liegt in seiner multikriteriellen und personalisierten Natur. Ein Hindernis zu umgehen hat häufig den Nachteil, dass hierfür ein längerer Umweg notwendig ist. Hindernisse wie beispielsweise Treppen sind für mobilitätseingeschränkte Menschen mit Nachteilen verbunden (z.B. große Anstrengung und/oder Schmerzen). Dennoch ist die Treppe, abhängig von der Länge des Umwegs, für manche das geringere Übel. Da die genaue Präferenz (Gewichtung zwischen Umweglänge und der Beschwerlichkeit der Barriere) für jeden Menschen unterschiedlich ist, berechnet der vorgestellte Ansatz immer die gesamte Pareto-Menge - also alle „trade-offs“ zwischen Weglänge und Beschwerlichkeit des Weges (durch Hindernisse). Personalisierte Nutzerprofile ermöglichen es, jeden Aspekt der Berechnung zu steuern. Zudem ist es möglich, bestimmte Hindernistypen vollständig auszuschließen. Der vorgestellte Ansatz für das Fußgängerrouting wird vollständig in eine intermodale Verbindungssuche integriert und ermöglicht es auf diese Weise barrierefreie personalisierte multikriteriell optimierte Tür-zu-Tür-Verbindungen zu berechnen. Das Fußgängerrouting wird sowohl für die Wege von/zu und zwischen ÖV-Stationen als auch für die  Berechnung gleisgenauer personalisierter Umstiegszeiten eingesetzt. Zudem wird die Barrierefreiheit von Fahrzeugen berücksichtigt. Die vorgestellte intermodale Auskunft verarbeitet Echtzeitmeldungen (z.B. Verspätungen, (Teil-)Ausfälle, Umleitungen, Zusatzzüge und Gleisänderungen) und aktualisiert das Datenmodell entsprechend. Dies ermöglicht es, im Fall von Problemen, aktuelle  Echtzeitalternativen zu berechnen. Dieses Konzept wird erweitert durch die Berücksichtigung von Fahrstuhlausfällen und der Änderung der Barrierefreiheit der eingesetzten Fahrzeuge. Die Evaluation der prototypischen Implementierung mit OpenStreetMap-Daten und einem vollständigen ÖV-Fahrplan für Deutschland zeigt, dass der beschriebene Ansatz praxistauglich und auch für große, komplexe Netze geeignet ist.

Hinweis: Das vorgestellte barrierefreien Fußgängerroutings, das im Rahmen des mFUNDgeförderten Per Pedes Routing Projekts entwickelt wurde, steht ab sofort als quelloffene Software unter der Adresse https://github.com/algotud/motis zur Verfügung.

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

1 Einleitung

Laut Weltgesundheitsorganisation (WHO) leben weltweit etwa 15% der Menschen mit einer Behinderung [1]. Dies beeinflusst häufig die gesellschaftlichen Teilnahmemöglichkeiten. Ein wichtiger Aspekt hierbei ist die Mobilität: selbst, wenn es (theoretisch) möglich ist, von einem Ort zu einem anderen zu gelangen, kann es schwierig sein, diese Verbindung (praktisch) zu finden. Der hier vorgestellte personalisierte Ansatz zur Berechnung intermodaler Verbindungen versucht, dieses Problem zu lösen. Zunächst wird ein Fußgängerrouting beschrieben, das dann in ein intermodales Auskunftssystem eingebunden wird.

Zuallererst unterscheiden wir zwischen „harten“ Einschränkungen (z.B. sind Rollstühle nicht für Treppen geeignet) und „weichen“ Einschränkungen: jemand mit einem Knieproblem würde gerne Treppen vermeiden – aber nicht zu jedem Preis. Abhängig von der Länge des Umweges (ohne Treppe) ist es möglich, dass die Treppe die bessere Option ist.

Unterschiedliche Präferenzen der Reisenden sind der Grund dafür, dass Forscher multikriterielle Optimierungsalgorithmen zur Berechnung von Verbindungen verwenden. Dies ist insbesondere beim Berechnen von Verbindungen im öffentlichen Verkehr der Fall. Hier wird nicht nur die Reisezeit minimiert, sondern gleichzeitig die Anzahl der Umstiege. Aber auch für die intermodale Verbindungssuche werden multkriteriell optimierte Verbindungen berechnet (weitere Kriterien z.B. Zeit im Taxi oder zu Fuß). Die gesamte Pareto-Menge zu berechnen ist hier der Standard.

Der hier vorgestellte Ansatz erweitert die multikriterielle Suche durch ein weiteres Kriterium, das die Beschwerlichkeit des Weges (in Abhängigkeit des Profils der/des Reisenden) quantifiziert. Basierend auf dem jeweiligen Nutzerprofil wird jedem Teil des Routingnetzwerks ein Beschwerlichkeitswert zugewiesen. Dies beinhaltet Treppen, Straßenüberquerungen, Steigungen und Gefälle und viele weitere potentiell problematische Sektionen. Abhängig von den Eigenschaften des Hindernisses ist der Wert frei konfigurierbar. Beispielsweise ist der Wert für eine Treppe abhängig von der Anzahl der Stufen, der Richtung (hoch oder runter) und ob es ein Geländer gibt oder nicht. Um kompatibel zu den anderen Optimierungskriterien zu sein, repräsentieren kleine Werte geringe Beschwerlichkeit. Dies ermöglicht es, alle Zielkriterien (Reisezeit, Anzahl der Umstiege und Beschwerlichkeit) zu minimieren.

Des Weiteren unterstützt das Fußgängerrouting Straßenüberquerungen. Hierfür ist ein Datenmodell nötig, das zwei Straßenseiten unterstützt. Für jede Straßenüberquerung an einem unmarkierten Übergang wird der kürzeste Umweg über einen markierten Übergang (z.B. über eine Fußgängerampel oder Zebrastreifen) berechnet. Unmarkierte Übergänge werden abhängig von der im Profil eingestellten maximalen Umweglänge als unzulässig markiert, um stattdessen die Benutzungeines nahegelegenen markierten Übergangs zu erzwingen. Die maximale Umweglänge kann abhängig vom Straßentyp eingestellt werden. Alternativ kann die Überquerung von bestimmten Straßentypen vollständig ausgeschlossen werden.

Zur Berechnung von durchgängig barrierefreien Verbindungen wird das Fußgängerrouting vollständig in das intermodale Auskunftssystem MOTIS [12] (Multi Objective Travel Information System) integriert. Es wird für alle Fußwege in der Verbindung eingesetzt. Dies umfasst gleisgenau berechnete Fußwege für den Umstieg zwischen Fahrzeugen im öffentlichen Verkehr. Des Weiteren werden (basierend auf dem jeweiligen Nutzerprofil) nicht barrierefreie Fahrzeuge von der Suche ausgeschlossen, so dass valide barrierefreie Alternativverbindungen berechnet werden.

Das verwendete Datenmodell (ein zeitabhängiger Graph) kann mit Echtzeitinformationen wie beispielsweise Verspätungsmeldungen, Meldungen über Zugausfälle, Zusatzzüge, Gleiswechsel oder  Umleitungen aktualisiert werden. Dies erlaubt es, zur aktuellen Situation Echtzeitalternativen zu berechnen. Wir erweitern diesen Ansatz um auch Fahrstuhlausfälle und Änderungen in der Barrierefreiheit der vom Verkehrsunternehmen eingesetzten Fahrzeuge zu berücksichtigen. Somit ist es möglich, auch in diesen Fällen Echtzeitalternativen für betroffene Reisende mit Mobilitätseinschränkungen zu berechnen.

Die Auswertungsergebnisse einer prototypischen Implementierung des Ansatzes basierend auf dem Deutschen ÖV-Fahrplan (einschließlich aller Züge, Busse, Straßen-, U- und S-Bahnen) und OpenStreetMap-Daten1 zeigen, dass der Ansatz auch auf komplexe Netze angewendet werden kann.

2 Verwandte Arbeiten

Viele Ansätze berücksichtigen die Einschränkungen der Nutzer nicht. In der Übersicht über den Stand der Forschung über das Planen von Routen (auf der Straße und im öffentlichen Verkehr) von Bast et. al. [2] wird das Thema nicht erwähnt. Ein erster multikriterieller Ansatz wurde in [3] vorgestellt. Allerdings wird in dem dort vorgestellten Ansatz nicht wie hier die gesamte Pareto-Front berechnet, sondern alle Kriterien in eine gewichtete Summe verrechnet. Somit besteht nicht mehr die Wahlmöglichkeit zwischen verschiedenen tradeoffs.  In [4] wird ein profilbasiertes Fußgängerrouting vorgestellt, das bestimmte „harte“ Ausschlüsse abbilden kann. Es liegt nach unserem Kenntnisstand bisher kein Ansatz vor, der wie in der Einleitung beschriebenen „weiche“ Ausschlüsse (Vermeidung von  Hindernissen) als zusätzliches Zielkriterium abbildet. Weyrer et. al. stellen in [6] ein intermodales Fußgängerrouting für mobilitätseingeschränkte Menschen basierend auf der OpenTripPlanner-Platform vor. Diese Auswertung von zwei konkreten Routinganfragen wurde auf dem Datensatz von Villach (Österreich) durchgeführt. Im Gegensatz zu unserer Arbeit werden dort keine personalisierten, gleisgenauen Umstiegswege berechnet. Müller-Hannemann und Schnee stellen in [5] eine Echtzeit-Fahrplanauskunft vor, die Verspätungsdaten, Zugausfälle, Zusatzzüge, usw. berücksichtigt.

3 Beitrag dieser Arbeit

 Der in dieser Arbeit vorgestellte Ansatz für ein barrierefreies intermodales Tür-zu-Tür-Routing ist in dieser Form gänzlich neu. Insbesondere die durchgängig integrierte multikriterielle Optimierung mit dem zusätzlichen Zielkriterium „Beschwerlichkeit“, die auch für Fußwege bei Umstiegen verwendet wird, wurde in dieser Form in keinem veröffentlichten Beitrag verwendet. Den Autoren dieses Beitrags ist auch kein intermodales Echtzeit-Routing bekannt, das Fahrstuhlausfälle, Gleisänderungen oder Änderungen in der Barrierefreiheit der vom Verkehrsunternehmen eingesetzten Fahrzeuge in der Auskunft berücksichtigt. Keiner der bisher vorgestellten Ansätze wurde auf einem derart umfangreichen Datensatz wie dem Verkehrsnetz von Deutschland evaluiert.

Bild 1: Beispiel für die Abtastung des Höhenprofils (Grauabstufungen) an gleichabständigen Stützstellen. Vergleiche Start/Ziel-Höhenunterschied (1m) und Gesamthöhenunterschied (-10m, +11m).

4 Fußgängerrouting

Dieses Kapitel stellt die Vorverarbeitung und die Berechnung der kürzesten Wege für das Fußgängerrouting vor. Die hier vorgestellten Verfahren sind quelloffen verfügbar. Das Fußgängerrouting wird in Abschnitt 5 in ein intermodales Echtzeit-Verbindungsauskunftssystem integriert.

4.1 Vorverarbeitung

Das personalisierte Fußgängerrouting für mobilitätseingschränkte Menschen basiert auf OpenStreetMap-Daten. Diese Daten bestehen aus mit Attributen versehenen Knoten, Wegen und Relationen. In einem ersten Schritt werden alle für Fußgänger potentiell zugängliche Wege und Flächen (z.B. öffentliche Plätze) aus dem OpenStreetMap-Datensatz extrahiert und in eine graphbasierte Darstellung überführt.

Vereinfachung des Routing-Graphen und Generierung von Gehwegen: Um die Anzahl der Knoten und Kanten zu reduzieren, werden hier bereits Knoten mit Grad zwei entfernt und die beiden Kanten durch eine einzelne ersetzt. Für Darstellungszwecke wird der genaue Pfad (die Koordinaten der gelöschten Knoten) als Kantenattribut hinterlegt und entsprechend den Angaben in den OpenStreetMap-Daten werden hieraus kein, ein oder zwei Gehweg-Pfade (für die jeweilige Straßenseite) erzeugt.

Höhenprofil: Das Höhenprofil eines Fußweges ist insbesondere für mobilitätseingeschränkte Menschen relevant. Da OpenStreetMap-Daten keine flächendeckenden Höhenangaben enthalten, ist es nötig, weitere Datenquellen hinzuzuziehen. Für Höhenprofile werden häufig Rasterdaten verwendet. Das hier vorgestellte Routing System unterstützt das Einlesen von Rasterdaten um den Routing-Graph entsprechend mit Höheninformationen zu erweitern. Nur Knoten aus OpenStreetMap mit Höhenangaben zu versehen, ist wie in Bild 1 dargestellt nicht sinnvoll (1m Höhenunterschied zwischen beiden Knoten). Das genaue Höhenprofil einer Kante im Routing-Graph wird durch eine Abtastung der Höhendaten entlang des Kantenverlaufs ermittelt (in Bild 1: -10m, +11m).

Zusammenfassung von Fahrbahnen: Unterschiedliche Fahrbahnen der selben Straße werden in OpenStreetMap häufig als getrennte Pfade abgebildet. Diese getrennten Pfade werden zusammengefasst um zu verhindern, dass hier Gehwege auf den Innenseiten der Fahrbahnen erzeugt werden.

Straßenüberquerungen: Durch die Unterscheidung und bedingte Erzeugung der verschieden Gehwegseiten ist es möglich, Straßenüberquerungen im Routing korrekt abzubilden. Es wird grundsätzlich zwischen markierten Übergängen (z.B. Ampeln, Zebrastreifen) und unmarkierten Übergängen unterschieden. Für jeden Straßentyp kann, abhängig vom Nutzerprofil, für unmarkierte Übergänge entweder der maximale Umweg über einen markierten Übergang festgelegt oder die Überquerung an unmarkierten Übergängen gänzlich ausgeschlossen werden. Hierfür wird in der Vorverarbeitung für jeden unmarkierten Übergang mit einem Kürzeste-Wege-Algorithmus die Länge des Umweges (unter Verwendung eines markierten Übergangs) bestimmt und für das Routing im Graph hinterlegt.

Bild 2: Fläche in OpenStreetMap (links), vollständig berechnete Pfade für diese Fläche (mittig) und für das Routing optimierte Pfade (rechts).

Überquerung von Flächen: Um später effizient optimale Pfade über Flächen berechnen zu können, werden in der Vorverarbeitung kürzeste Wege, wie in Bild 2 dargestellt, zwischen allen Randknoten, die an weitere Flächen, Straßen und Fußwege angrenzen, vorberechnet. Die Berechnug von Wegen über nicht-konvexe Plätze oder Plätze mit inneren Polygonen (z.B. Brunnen) basiert auf dem Konzept des Visibility Graph [8]. Alle Knoten, zwischen denen kein Hindernis auf der Sichtverbindung liegt, werden miteinander verbunden. In einem weiteren Vorverarbeitungsschritt werden von allen Ein- und Ausgangsknoten zu allen anderen Ein- und ausgangsknoten mit dem Floyd-Warshall-Algorithmus kürzeste Wege berechnet. Kanten und Knoten, die in nicht auf mindestens einem kürzesten Pfad zwischen Ein- und Ausgangsknoten liegen, werden entfernt, da sie offensichtlich für die Berechnung kürzester Wege nicht relevant sind. Dieser letzte Schritt ist optional. Er beschleunigt die intermodale Verbindungssuche und reduziert den Speicherbedarf.

Darstellung: Zur Optimierung der Darstellungsergebnisse werden die erzeugten Gehwege an Schnittpunkten durch geometrische Schnitte verbunden.

4.2 Berechnung von Routen

In diesem Kapitel wird erläutert, wie basierend auf dem Nutzerprofil, Start- und Zielkoordinaten und dem Routing-Graphen, dessen Generierung aus OpenStreetMap-Daten in Kapitel 4.1 beschrieben wird, eine Pareto-Menge kürzester Wege berechnet wird.

Ableiten von Knoten im Routing-Graph aus Start-, bzw. Zielkoordinaten: Zuerst müssen die vom Nutzer eingegebenen Koordinaten (oder Adressen) in Knoten des Routing-Graphen übersetzt werden. Den Knoten mit dem kleinsten euklidischen Abstand zu wählen, kann zu unsinnigen Routen führen, da der Weg auf diese Weise möglicherweise erstmal (bzw. kurz vor dem Ziel) in die falsche Richtung führt. Um dem entgegenzuwirken, werden die beiden Endpunkte der nächstgelegenen Kante für die Suche mit ihrer euklidischen Distanz zu der vom Nutzer angegebenen Koordinate verknüpft. Liegt der Endpunkt in einer Fläche (z.B. einem Platz), wird der Punkt mit allen „sichtbaren“ (Visibility Graph – siehe [8]) Ecken des Polygons verbunden. Punkte außerhalb von Flächen werden mit dem  nächstgelegenen Punkt auf dem Flächenrand verbunden. Für Spezialfälle (wie z.B. beide Punkte liegen in der selben oder in benachbarten Flächen) gelten gesonderte Regeln. Die ausgewählten Startknoten müssen nicht zwingend mit den Zielknoten verbunden sein. Dies kann passieren, wenn der Graph „Inseln“ hat, die nicht mit dem Rest verbunden sind. Um in diesen Fällen dennoch Verbindungen liefern zu können, werden nach einer erfolglosen ersten Suche weitere Knoten im Umkreis von Start- und Ziel hinzugenommen.

Nutzerprofil: Das Suchprofil unterstützt sowohl Ausschlüsse von beliebigen (in OpenStreetMap enthaltenen) Hindernistypen als auch das Festlegen eines Beschwerlichkeitswertes und Zeitkosten abhängig von den Eigenschaften eines Hindernisses. Hierzu können konstante, lineare und quadratische Abhängigkeiten zwischen den Eigenschaften des Hindernisses und den Kostenfaktoren (Beschwerlichkeit und Zeit) definiert werden. Dies erlaubt es bei Treppen beispielsweise quadratische Kosten für die Treppenlänge und einen konstanten Strafterm für das Nicht-Vorhandensein eines Geländers zu definieren. Kostenfaktoren für Straßenüberquerungen (getrennt für unmarkierte Übergänge, Zebrastreifen und Ampeln) können auf die selbe Art und Weise festgelegt werden. Die Kostenfaktoren können für unterschiedliche Richtungen (z.B. Treppe oder Rampe hoch und runter) separat angegeben werden. Zudem erlaubt das Routing-Profil, die Maximaldauer des Fußweges und den maximalen Umweg für unmarkierte Übergänge (siehe Vorverarbeitung) festzulegen.

In der Praxis kann es sowohl vorgefertigte Profile für typische Mobilitätseinschränkungen geben aber auch die Möglichkeit, dass Experten (z.B. Pfleger/innen oder Ärzte/Ärztinnen – ggf. nach gesonderter Schulung) spezielle Profile passend für die individuellen Einschränkungen einzelner Nutzer definieren.

Für die Auswertung in Abschnitt 6 werden nur vordefinierte Profile verwendet, da dies zur Bestimmung der Rechenzeiten ausreichend ist. Im Allgemeinen ist möglich, für jede Berechnung individuell ein anderes Nutzerprofil zu verwenden.

Multikriterielle kürzeste Wege: Das Nutzerprofil definiert für jede Kante des Routing-Graphen, in Abhängigkeit der Eigenschaften des Wegstücks, das die Kante repräsentiert, einen Vektor von Kantengewichten. Diese können nun mit einem multikriteriellen Dijkstra-Algorithmus (beschrieben z.B. in [9]) dazu verwendet werden, für die jeweilige Person personalisiert kürzeste Wege zu berechnen.

5 Intermodales Tür-zu-Tür-Routing

Das zuvor beschriebene personalisierte Fußgänger-Routing wird nun verwendet, um Vor- und Nachlauf (die Strecke von der Start-Adresse zur ersten ÖV-Haltestelle und von der letzten ÖV-Haltestelle zur Ziel-Adresse) und die Wege zwischen den Haltepositionen der an einem Umstieg beteiligten Fahrzeuge zu berechnen. Ein Umstieg kann einen Laufweg zwischen zwei nahegelegenen Stationen umfassen.

Wie in [7] beschrieben, basiert das Routing auf einem ausgereiften Fahrplan-Routing-Kern. Dieser unterstützt Sonderregeln wie das Verbot ein- oder auszusteigen, Durchbindungen und Vereinigungen (Flügelzüge), Zeitzonen. Vor dem eigentlichen Routing werden wie in [7] beschrieben kürzeste Wege von der Startadresse zu ÖV-Station in Laufweite und von ÖVStationen in Zielnähe zur Zieladresse berechnet. Diese berechneten Wege ergänzen dynamisch den Fahrplan-Routing-Graphen als zusätzliche Kanten von/zu virtuellen Start/Zielknoten.

Für Umstiege werden kürzeste Wege zwischen allen Gleisen bzw. Haltepunkten der Station mit dem Fußgänger-Routing vorberechnet. Das Routing ist grundsätzlich dazu in der Lage, Umstiegsdauer und Beschwerlichkeit zu berechnen, da das OpenStreetMap-Datenformat auch für die Darstellung von Indoor-Gebäudeplänen geeignet ist. Die vorberechneten Wege werden als Kanten zwischen den Routenknoten im zeitabhängigen Graphmodell genutzt. Das heißt, dass für einen Umstieg gegebenenfalls mehrere Möglichkeiten – beispielsweise eine längere, barrierefreie und eine kürzere, nicht barrierefrei Variante – existieren.

Da der gewählte Routing-Algorithmus auf dem zeitabhängigen Graphen keinerlei gesonderte Vorberechnung benötigt, ist es möglich, das Datenmodell mit Echtzeitinformationen (Verspätungen, Zugausfälle, Umleitungen, usw.) zu aktualisieren. Mit der Erweiterung der exakt berechneten Umstiege, kommen Gleisänderungen und Fahrstuhlausfällen eine besondere Bedeutung zu: ändert sich beispielsweise das Gleis von einem mit Fahrstuhl zu einem ohne Fahrstuhl, oder fällt ein Fahrstuhl aus, kann das für mobilitätseingeschränkte Menschen zu Problemen führen. Das hier vorgestellte Routing ist in der Lage, basierend auf derartigen Echtzeit-Meldungen die vorberechneten Fußwege in diesem Fall punktuell zu aktualisieren. Folglich ist es jetzt möglich, in Problemfällen, zum einen den Nutzer vorzeitig auf darauf aufmerksam zu machen (zum Beispiel über eine Push-Benachrichtigung in einer App) und zum anderen aktuelle Echtzeit-Alternativverbindungen zu berechnen.

6 Evaluation

In diesem Kapitel wird eine Auswertung des beschriebenen Ansatzes basierend auf einer prototypischen Umsetzung vorgestellt. Die Software ist vollständig in der Programmiersprache C++ implementiert und wurde unter Ubuntu 18.10 mit dem Clang-Compiler (Version 8.0.0, -O3 und -march=native Parameter zur Optimierung) kompiliert. Das Programm wurde auf einer Intel Core i7 8700K (6x 3.70GHz) CPU mit 64GB Arbeitsspeicher ausgeführt.

Als Datensatz wurde ein von der Deutschen Bahn AG bereitgestellter ÖV-Fahrplan von Deutschland verwendet, der alle Verkehre (Busse, Straßen-, U-, S-Bahnen, Regional- und Fern- und Hochgeschwindigkeitszüge) enthält. Geladen wurden die Tage 02.07. und 03.07.2019. Für das Fußgängerrouting wurde ein OpenStreetMap-Datensatz verwendet, der das selbe Gebiet abdeckt.

Der Fahrplan umfasst 271.329 Stationen, mit 1.509.787 Fahrten auf 184.344 eindeutigen Stationsfolgen (Routen). Insgesamt gibt es 53.792.814 Ankunfts- und Abfahrtsereignisse. Der resultierende Routinggraph hat 4.063.195 Knoten und 11.544.006 Kanten. Der Routinggraph für das Fußgängerrouting hat 28.829.081 Knoten und 56.842.104 Kanten.

Da die in OpenStreetMap enthaltenen Gebäudepläne häufig nicht genau genug abgebildet sind und keine Verknüpfung mit den Gleisinformationen im Fahrplan aufweisen, ist es aktuell nicht ohne Weitere manuelle Arbeit möglich, diese Daten für das Routing zu verwenden. Um den Ansatz dennoch bezüglich der Laufzeit-Charakteristiken evaluieren zu können, wurden für diese Auswertung  Umstiegsgraphen für alle im Fahrplan enthaltenen Stationen generiert. Hierfür wurde für jedes Gleis im Fahrplan die Information zufällig generiert, ob es ebenerdig, nur über eine Treppe oder über Treppe und Fahrstuhl erreichbar ist. Es wurde angenommen, dass alle Gleise aufsteigend sortiert benachbart sind. Hieraus ergeben sich eindeutig Wegezeiten und Beschwerlichkeitswerte zwischen Quell- und Zielgleis.

6.1 Fußgänger-Routing Vorverarbeitung

Tabelle 1 zeigt die Dauer und die zahlenmäßigen Ergebnisse der Vorverarbeitung für verschieden große Datensätze (Frankfurt am Main, Hessen und Deutschland). Ein deutlicher Zuwachs an Rechenzeit in Abhängigkeit der Größe des Datensatzes ist klar erkennbar. Für die meisten Anwendungsfälle ist aber selbst eine Vorberechnungszeit von 13:11 Min. (Deutschland) aber ausreichend.

Tabelle 1: Rechenzeiten der Vorverarbeitung und Kenngrößen der berechneten Routinggraphen

Tabelle 2: Durchschnittliche Rechenzeit, Anzahl erstellter Labels und Anzahl gefundener Verbindungen für verschiedene Suchprofile

Tabelle 2 zeigt exemplarisch die Rechenzeiten für die unterschiedlichen Routingvarianten2: das Standardprofil enthält keine Beschwerlichkeitswerte oder Ausschlüsse. Das Profil „auch leichte Wege“ optimiert zusätzlich zu den Kriterien Reisezeit und Anzahl der Umstiege auch einen Beschwerlichkeitswert. Das Profil „Rollstuhl“ hat harte Ausschlüsse für Wegteile, die nicht für Rollstühle geeignet sind. Die Rechenzeit für das „auch leichte Wege“ Profil steigt von 1,24 Sekunden um fast den Faktor zehn auf 9,13 Sekunden. Dies entspricht in etwa dem gesteigerten Suchaufwand der zusätzlich benötigten Labels (partielle Verbindungen). Bild 3 zeigt die Abhängigkeit der Rechenzeit von der Distanz zwischen Start und Ziel (links) und der maximalen Fußwegdauer (rechts). In beiden Fällen ist ein klarer Zusammenhang zwischen dem gewählten Parameter und der Rechenzeit ersichtlich. Basierend auf den Parametern der Anfrage kann also bereits abgeschätzt werden, wie sich die Antwortzeit (im Durchschnitt) verhalten wird. Der Grund für die steigende Rechenzeit für größere Laufweg-Radien ist, dass es insbesondere am Start mehr Möglichkeiten gibt, die Reisekette zu beginnen. Diese Optionen alle zu bewerten, kostet im Algorithmus mehr Zeit. Ähnlich ist es bei größeren Distanzen zwischen Start und Ziel: die Anzahl der Optionen, die Berechnet und bewertet (bzw. verglichen) werden müssen, steigt stark an.

Bild 3: Gesamtrechenzeit in Abhängigkeit der Distanz zwischen Start und Ziel bzw. der maximalen Fußwegzeit an Start und Ziel

Einen noch genaueren Überblick der Box-Whisker-Plot Grafik 4. Hier ist klar zu erkennen, dass nicht nur die durchschnittliche Laufzeit mit der Distanz zwischen Start und Ziel anwächst, sondern insbesondere auch die oberen Quartile stark wachsen. Ab 200 km Abstand beträgt die Rechenzeit von 25% der Anfragen bereits mehr als 10 Sekunden.

Bild 4: Gesamtrechenzeit (ms) in Abhängigkeit der Distanz zwischen Start und Ziel (km)

7 Fazit und Ausblick

In diesem Beitrag wurde ein Ansatz für ein personalisiertes barrierefreies intermodales Echtzeit-Tür-zu-Tür-Routing vorgestellt und gezeigt, dass dieser Ansatz auch in der Praxis auf große Netze wie das Deutsche Verkehrsnetz anwendbar ist. Der Ansatz zeichnet sich durch seine multikriterielle Behandlung „weicher“ Ausschlüsse (Vermeidung von Hindernissen) aus, unterstützt aber profilbasiert auch vollständige Ausschlüsse bestimmter Hindernistypen. Neben der Berücksichtigung von Verspätungsmeldungen werden zudem auch Fahrstuhlausfälle, Gleisänderungen (z.B. auf nicht barrierefreie Gleise) und Änderungen der Barrierefreiheit der vom Verkehrsunternehmen eingesetzten Fahrzeuge live berücksichtigt. Dies ermöglicht im Problemfall das Finden von Echtzeit-Alternativen.

Aktuelle Arbeiten beschäftigen sich mit weiteren Beschleunigungstechniken und der Portierung des Ansatzes auf modernere Basis-Routing-Algorithmen wie beispielsweise RAPTOR [10] oder CSA [11]. Zudem hat die Evaluation des Ansatzes gezeigt, dass die Zahl der gefundenen Verbindungen sehr hoch ist. Ziel weiterer Arbeiten sollte es also sein, den Nutzer durch eine intelligente Filterung der Ergebnismenge zu unterstützen.

8 Literatur

[1] World Health Organization (2011). World report on disability

[2] Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., ... & Werneck, R. F. (2016). Route planning in transportation networks. In Algorithm engineering (S. 19-80). Springer, Cham.

[3] Völkel, T., & Weber, G. (2008, October). RouteCheckr: personalized multicriteria routing for mobility impaired pedestrians. In Proceedings of the 10th international ACM SIGACCESS conference on Computers and accessibility (S. 185-192). ACM.

[4] Sobek, Adam D., and Harvey J. Miller. "U-Access: a web-based system for routing pedestrians of differing abilities." Journal of geographical systems 8.3 (2006): S. 269-287.

[5] Müller-Hannemann, M., and Schnee, M. "Efficient timetable information in the presence of delays." Robust and Online Large-Scale Optimization. Springer, Berlin, Heidelberg, 2009. S. 249-272.

[6] Weyrer, Timothy N., Hartwig H. Hochmair, and Gernot Paulus. "Intermodal door-to-door routing for people with physical impairments in a web-based, open-source platform." Transportation Research Record 2469.1 (2014): S. 108-119.

[7] Gündling, F., Keyhani, M. H., Schnee, M., & Weihe, K. (2014). Fully Realistic Multi-Criteria Multi-Modal Routing.

[8] Lozano-Pérez, T., & Wesley, M. A. (1979). An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM, 22(10), 560-570.

[9] Schnee, M. (2009). Fully realistic multi-criteria timetable information systems (Doctoral dissertation, Technische Universität).

[10] Delling, D., Pajor, T., & Werneck, R. F. (2014). Round-based public transit routing. Transportation Science, 49(3), 591-604.

[11] Dibbelt, J., Pajor, T., Strasser, B., & Wagner, D. (2013, June). Intriguingly simple and fast transit routing. In International Symposium on Experimental Algorithms (pp. 43-54). Springer, Berlin, Heidelberg.

[12] Gündling, F., Keyhani, M. H., Schnee, M., & Weihe, K. (2014). Fully Realistic Multi-Criteria Multi-Modal Routing.