TU Darmstadt / ULB / TUprints

Efficient Algorithms for Intermodal Routing and Monitoring in Travel Information Systems

Gündling, Felix (2020)
Efficient Algorithms for Intermodal Routing and Monitoring in Travel Information Systems.
Technische Universität
doi: 10.25534/tuprints-00014212
Ph.D. Thesis, Primary publication, Publisher's Version

[img]
Preview
Text
dissertation_FelixGuendling.pdf
Copyright Information: CC BY 4.0 International - Creative Commons, Attribution.

Download (5MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Efficient Algorithms for Intermodal Routing and Monitoring in Travel Information Systems
Language: English
Referees: Weihe, Prof. Dr. Karsten ; Borndörfer, Prof. Dr. Ralf
Date: 22 October 2020
Place of Publication: Darmstadt
Collation: xiii, 175 Seiten
Date of oral examination: 22 October 2020
DOI: 10.25534/tuprints-00014212
Abstract:

Millions of people use online journey planning systems. However, most of the currently available systems only support finding optimal journeys for one mode of transportation (i.e. only public transportation, driving by car, etc.). This makes it hard to plan intermodal journeys combining different modes of transportation to reach a destination. In this thesis we present a real-time multi-criteria intermodal travel information system supporting various transportation modes as well as different special use cases such as intermodal routing for people with disabilities and tourist tour planning.

Choosing the perfect parking to switch from private transportation (e.g. bicycle or car) to public transport (e.g. buses, trams, trains, etc.) is basically trial and error when using unimodal planning systems. This problem becomes even harder when the user wants to return to the starting point which is a common use case of intermodal travel. The optimal route for the outward trip may yield a suboptimal or even infeasible return trip and vice versa (due to the choice of the parking place). In this work, we present a novel and integrated multi-criteria approach to computing optimal journeys for both trips (outward and return trip) combined.

Previous routing approaches only provide very limited functionality for people with disabilities. Many elderly people as well as persons with heavy luggage or a baby buggy would like to avoid obstacles like stairs -- however not at all costs (depending on the detour length). Our new multi-criteria approach computes all optimal trade-offs between the difficulty of the route and other optimization criteria (like travel time and the number of transfers). Additionally, we support restrictions that forbid the usage of certain obstacle types completely (like a person in a wheelchair cannot use stairs at all). The restrictions as well as the difficulty of each obstacle need to be adaptable to the profile of the person using the routing service. Our approach is customizable and computes optimal intermodal journeys in a fully integrated manner.

Another use case of intermodal mobility is the planning of a tourist trip in a foreign city. Here, several constraints such as opening hours of attractions need to be considered. If planning a tour for multiple days, we want to avoid redundancy. We present a novel combination of the Time Dependent Team Orienteering Problem with Time Windows (TDTOPTW) with the Orienteering Problem with Variable Profits (OPVP). Additionally, our modeling is the first to support several entries and exits per point of interest (PoI) which is relevant in practice because for large area sites like zoos or boardwalks the public transport stop at each entry/exit may be serviced by different lines.

In case of delays, cancellations, reroutings, or track changes, a journey may become infeasible. In this case, information is key to finding a solution to this problem. Informing travelers as soon as possible gives them the most options. We present an efficient approach to monitor millions of journeys in parallel. The selection of change notices to be communicated to a traveler may be flexibly adapted to the travelers individual needs. Additionally, the system is capable of providing intermodal real-time alternatives in case of a broken connection.

To make the functionality described above accessible to the end-user, we have built mobile (Android) as well as web-based user interfaces. We describe the distributed modular software architecture which can resemble micro-services as well as a monolithic setup enables us to provide the approaches in a scalable and efficient way.

Alternative Abstract:
Alternative AbstractLanguage

Millionen Menschen nutzen Online-Reiseplaner. Allerdings unterstützen die meisten aktuell verfügbaren Systeme nur die Routensuche für ein Verkehrsmittel (z.B. nur öffentliche Verkehrsmittel oder nur mit dem Auto fahren). Das erschwert die Suche nach intermodalen Reiseketten in denen verschiedene Verkehrsmittel kombiniert werden, um das Ziel zu erreichen. In dieser Arbeit stellen wir ein echtzeitfähiges, multikriterielles und intermodales Reiseinformationssystem vor, das verschiedenste Verkehrsmittel und Anwendungsfälle wie beispielsweise die intermodale Verbindungssuche für Menschen mit Mobilitätseinschränkung oder das Planen einer Touristen-Tour unterstützt.

Den perfekten Parkplatz zum Wechsel zwischen Individualverkehr (beispielsweise Fahrrad oder PkW) auf den öffentlichen Verkehr (Buasse, Straßenbahnen, Züge, usw.) zu finden, ist bei der Verwendung mehrerer unimodaler Reiseplaner nur durch Ausprobieren möglich. Das Problem wird weiter erschwert, wenn man den Rückweg in die Planung miteinbezieht. Dies ist ein weitverbreiteter Anwendungsfall intermodaler Mobilität. Die optimale Route für den Hinweg kann (durch die Wahl des Parkplatzes) einen suboptimalen oder sogar unfahrbaren Rückweg erzwingen. Selbiges gilt umgekehrt. In dieser Arbeit stellen wir einen neuartigen integrierten multikriteriellen Ansatz vor, mit dem (kombiniert) optimale Reiseketten für Hin- und Rückrichtung berechnet werden können.

Bisherige Routingansätze bieten nur sehr limitierte Funktionalität für Menschen mit Mobilitätseinschränkungen. Viele ältere Menschen sowie Menschen mit schwerem Gepäck oder einem Kinderwagen würden Hindernisse gerne vermeiden -- aber nicht zu jedem Preis (abhängig von der Länge des Umwegs). Unser neuer multikriterieller Ansatz berechnet alle optimalen Kompromisslösungen zwischen der Beschwerlichkeit des Weges und den anderen Optimierungskriterien (wie zum Beispiel Reisezeit und die Anzahl der Umstiege). Zudem unterstützen wir Einschränkungen, die die Nutzung von bestimmten Hindernistypen vollständig verhindert (wie zum Beispiel eine Person im Rollstuhl, die keine Treppen nutzen kann). Die Konfiguration dieser Ausschlüsse sowie der Beschwerlichkeit für jedes Wegstück müssen vollständig durch die Nutzer des Routenplaners anpassbar sein. Unser Ansatz ist frei konfigurierbar und berechnet optimale intermodale Reiseketten auf eine vollständig integrierte Art- und Weise.

Ein weiterer Anwendungsfall intermodaler Mobilität ist die Planung einer Touristen-Tour in einer fremden Stadt. Hierfür müssen einige Bedingungen, wie beispielsweise die Öffnungszeiten von Attraktionen, berücksichtigt werden. Bei der Planung von Touren für mehrere Tage möchte man Redundanz bei den Aktivitäten vermeiden. Wir präsentieren eine neuartige Kombination des Time Dependent Team Orienteering Problem with Time Windows (TDTOPTW) mit dem Orienteering Problem with Variable Profits (OPVP). Zudem ist unsere Modellierung die erste, die Attraktionen mit mehreren Ein- und Ausgängen unterstützt. Diese Möglichkeit ist praktisch relevant, da insbesondere bei großflächigen Attraktionen wie beispielsweise Zoos oder Strandpromenaden die Haltestellen in der Nähe der Ein- und Ausgänge von verschiedenen Linien bedient werden.

Im Fall von Verspätungen, Ausfällen, Umleitungen, oder Gleiswechseln können Verbindungen brechen. In diesem Fall sind Informationen der Schlüssel um eine Lösung für das Problem zu finden. Die Reisenden möglichst frühzeitig über Probleme zu informieren vergrößert den Handlungsspielraum. Wir präsentieren einen effizienten Ansatz um Millionen von Verbindungen zeitgleich zu überwachen. Die Auswahl der Änderungsmeldungen, die den Reisenden übermittelt werden sollen, kann flexibel den Wünschen der Reisenden angepasst werden. Zudem ist das System in der Lage im Fall einer gebrochenen Reisekette Echtzeitalternativen zu berechnen.

Um die beschriebenen Funktionalitäten dem Endanwender zur Verfügung zu stellen, wurde eine mobile sowie eine web-basierte Nutzeroberflächen entwickelt. Die vorgestellte verteilte modulare Software-Architektur, die sowohl als Microservices als auch in einem monolithischen Setup verwendet werden kann, ermöglicht die skalierbare und effiziente Bereitstellung der Ansätze.

German
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-142127
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Algorithmics
Date Deposited: 11 Dec 2020 14:14
Last Modified: 24 May 2023 15:39
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/14212
PPN: 473884771
Export:
Actions (login required)
View Item View Item