KIT | KIT-Bibliothek | Impressum | Datenschutz

Robust Mobile Route Planning with Limited Connectivity

Delling, Daniel; Kobitzsch, Moritz; Luxen, Dennis; Werneck, Renato F.

Abstract:
We study the problem of route planning on mobile devices. There are two current approaches to this problem. One option is to have all the routing data on the device, which can then compute routes by itself. This makes it hard to incorporate traffic updates, leading to suboptimal routes. An alternative approach outsources the route computation to a server, which then sends only the route to the device. The downside is that a user is lost when deviating from the proposed route in an area with limited connectivity. In this work, we present an approach that combines the best of both worlds. The server performs the route computation but, instead of sending only the route to the user, it sends a corridor that is robust against deviations. We define these corridors properly and show that their size can be theoretically bounded in road networks. We evaluate their quality experimentally in terms of size and robustness on a continental road network. Finally, we introduce several algorithms to compute corridors efficiently. Our experimental analysis shows that our corridors are small but very robust against deviations, and can be computed quickly on a standard server.



Originalveröffentlichung
DOI: 10.1137/1.9781611972924.15
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2012
Sprache Englisch
Identifikator ISBN: 978-1-61197-212-2
KITopen-ID: 1000097643
Erschienen in 2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Ed.: D. Bader
Verlag Society for Industrial and Applied Mathematics, Philadelphia, PA
Seiten 150-159
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page