Data model and algorithms for multimodal route planning with transportation networks
Lu Liu · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2011
Determining a best route in highly developed complex transportation networks is not a trivial task, especially for those who are unfamiliar with the local transportation system.To assist the mobility of people by taking advantage of the multimodal transportation infrastructure is the main goal of intelligent multimodal navigation services.Multimodal route planning that aims to find an optimal route between the source and the target of a trip while utilizing several transportation modes including car driving, public transportation, cycling, walking, etc. is essential to intelligent multimodal navigation services.Although the task originates from the field of transportation, it can be abstracted as a general form independent of the domain-specific details on the underlying data model and algorithms.This research work is therefore dedicated to a general approach of modeling the multimodal network data and performing optimal path queries on it.The approach is approved in the application field of urban transportation.The bottleneck in the development of a multimodal route planning service is reflected in two aspects: one is the lack of a high-quality dataset; the other is the lack of effective modeling and path-finding approach.With an integrated navigation dataset produced from an automated data-matching process as the desirable test bed, this research is focused on the second aspect.The weighted digraph structure can well represent the fundamental static networks.For each mode, there is one corresponding mode graph.These graphs constitute the Multimodal Graph Set as a key component of the overall multimodal network data model.In comparison with the traditional mono-modal problem, another key component necessary in the modeling of multimodal route-planning problem is mode-switching actions.In this work, such actions are described by Switch Points which are somewhat analog to plugs and sockets between different mode graphs.Consequently, it is possible to plug-and-play a Multimodal Graph Set by means of Switch Points.On the basis of the multimodal network data model, the multimodal route-planning problem is categorized into two types and formalized as the multimodal shortest path problem on the Plug-and-Play Multimodal Graph Set.The first type where the mode sequence is given in the input is described as to find a shortest path from a given source to a destination across the modes in the sequence one after another.This type of problem can be solved within a general algorithmic framework.For the second type where the mode sequence cannot be determined beforehand, the multimodal path-finding algorithm can make good use of the traditional mono-modal shortest path algorithms together with the SCM-PLUG operation.It turns out that the solutions for these two types of problem are equivalent if the input mode list for the first type is transformed into its matrix expression.When applying the general multimodal route-planning approach to a specific application domain, a rule-based inferring process is necessary to determine whether a mode sequence is reasonable or not.Performance evaluations on the integrated navigation dataset have verified the efficiency I of the proposed approach.A web-based prototype system demonstrates the whole workflow of the multimodal route-planning function which is missing in any other existing systems.Case studies based on the prototype system show that all feasible routing plans and the corresponding optimal paths can be automatically created for users who just need to tell the system about their preferences on the usage of transportation modes. II ZusammenfassungDie beste Route in einem hochentwickelten komplexen Verkehrsnetzen zu bestimmen ist keine triviale Aufgabe vor allem für diejenigen, die mit der lokalen Verkehrsinfrastruktur noch nicht vertraut sind.Das Ziel einer intelligenten multimodalen Navigation ist es den Menschen die bestmögliche Mobilität in einer multimodalen Verkehrsinfrastruktur anzubieten.Multimodale Routenplanung ist unentbehrlich beim Aufbau von intelligent multimodalen Navigationsdiensten. Deren Zweck ist es einen Benutzer den optimalen Weg zwischen Start und Ziel einer Reise anzubieten, wenn dabei die Strecke mehrere Verkehrsträger, einschließlich PKW, öffentliche Verkehrsmittel, Fahrrad, etc. oder auch Strecken zu Fuß, beinhaltet.Obwohl dieses Problem ursprünglich aus dem Transportwesen stammt, kann es in allgemeiner Form durch die Entkopplung der Domain-spezifischen Details aus dem zugrunde liegenden Datenmodell und Algorithmen abstrahiert werden.Diese Forschungsarbeit widmet sich dem allgemeinen Ansatz der Modellierung eines multimodalen Datenmodells, den Abfragen von optimalen Routen in diesem Modell, sowie deren Anwendung in einer urbanen Verkehrsinfrastruktur.Der Engpass bei der Entwicklung eines multimodalen Routenplanungsdienstes lässt sich in zwei Aspekte aufteilen: Zum einen das Fehlen eines hochwertigen Datenbestandes, zum anderen, dass keine effektive Modellierung und kein Wegfindungsansatz existiert.Unter Verwendung eines integrierten Navigationsdatensatzes, erzeugt aus einem automatisierten Daten-Matching-Verfahren, das als Testumgebung zur Verfügung steht, konzentriert sich diese Forschung auf den zweiten Aspekt.Die gewichtete Digraphstruktur ist zur Repräsentation der fundamentalen statischen Verkehrsnetze geeignet.Für jeden Modus gibt es einen entsprechenden Modusgraph.Diese Graphen konstituieren das Multimodale Graphenset, dass eine Komponente des gesamten multimodalen Datenmodells darstellt.Im Vergleich mit dem traditionellen mono-modalen Problem ist die primäre Herausforderung bei der Modellierung einer multimodalen Routenplanung, dass Modus-Umschaltungs-Aktionen zusätzlich zu den Basisnetzen berücksichtigt werden müssen.Solche Maßnahmen werden mit der Einführung des Konzepts Switch-Point, dass unter bestimmten Bedingungen mit Stecker und Buchsen zwischen verschiedenen Modusgraphen verglichen werden können, modelliert.Folglich kann der Multimodale Graphenset nach "Plug-and-Play-Art", mit der Unterstützung der anderen Komponente des Datenmodells, nämlich den Switch-Points, verwendet werden.Auf Basis des multimodalen Datenmodells ist die multimodale Routenplanungsaufgabe in zwei Typen kategorisiert und wird als multimodales kürzester Pfad Problem auf dem Plug-and-Play Multimodalen Graphenset formalisiert.Das Typ-I-Problem, bei dem die Modus-Sequenz dem Input hinzugefügt wird, kann durch die Suche des kürzesten Weges von einem gegeben Ursprung zu einem Zielpunkt, über die verschiedenen Modi der Sequenz laufend, beschrieben werden.Dieser Problemtyp kann durch ein allgemeines algorithmisches System gelöst werden.Für das Typ-II-Problem, bei dem die Modus-Sequenz nicht im Voraus bestimmt werden kann, lassen sich konventionelle mono-modale Algorithmen, mit der III XIV SSSP single-source shortest-paths problem STM