KIT | KIT-Bibliothek | Impressum | Datenschutz

Fast Computation of Shortest Smooth Paths and Uniformly Bounded Stretch with Lazy RPHAST

Zeitz, Tim 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

We study the shortest smooth path problem (SSPP), which is motivated by traffic-aware routing in road networks. The goal is to compute the fastest route according to the current traffic situation while avoiding undesired detours, such as briefly using a parking area to bypass a jammed highway. Detours are prevented by limiting the uniformly bounded stretch (UBS) with respect to a second weight function which disregards the traffic situation. The UBS is a path quality metric which measures the maximum relative length of detours on a path. In this paper, we settle the complexity of the SSPP and show that it is strongly NP-complete. We then present practical algorithms to solve the problem on continental-sized road networks both heuristically and exactly. A crucial building block of these algorithms is the UBS evaluation. We propose a novel algorithm to compute the UBS with only a few shortest path computations on typical paths. All our algorithms utilize Lazy RPHAST, a recently proposed technique to incrementally compute distances from many vertices towards a common target. An extensive evaluation shows that our algorithms outperform competing SSPP algorithms by up to two orders of magnitude and that our new UBS algorithm is the first to consistently compute exact UBS values in a matter of milliseconds.


Verlagsausgabe §
DOI: 10.5445/IR/1000149126
Veröffentlicht am 28.07.2022
Originalveröffentlichung
DOI: 10.4230/LIPIcs.SEA.2022.3
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2022
Sprache Englisch
Identifikator ISBN: 978-3-9597725-1-8
ISSN: 1868-8969
KITopen-ID: 1000149126
Erschienen in 20th International Symposium on Experimental Algorithms (SEA 2022). Ed.: C. Schulz
Veranstaltung 20th International Symposium on Experimental Algorithms (SEA 2022), Heidelberg, Deutschland, 25.07.2022 – 27.07.2022
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 3
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 233
Schlagwörter realistic road networks, route planning, shortest paths, traffic-aware routing, live traffic, uniformly bounded stretch
Nachgewiesen in Scopus
Globale Ziele für nachhaltige Entwicklung Ziel 11 – Nachhaltige Städte und Gemeinden
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page