KIT | KIT-Bibliothek | Impressum | Datenschutz

Alternative Route Graphs in Road Networks

Bader, Roland; Dees, Jonathan; Geisberger, Robert; Sanders, Peter

Abstract:
Every human likes choices. But today’s fast route planning algorithms usually compute just a single route between source and target. There are beginnings to compute alternative routes, but there is a gap between the intuition of humans what makes a good alternative and mathematical definitions needed for grasping these concepts algorithmically. In this paper we make several steps towards closing this gap: Based on the concept of an alternative graph that can compactly encode many alternatives, we define and motivate several attributes quantifying the quality of the alternative graph. We show that it is already NP-hard to optimize a simple objective function combining two of these attributes and therefore turn to heuristics. The combination of the refined penalty based iterative shortest path routine and the previously proposed Plateau heuristics yields best results. A user study confirms these results.



Originalveröffentlichung
DOI: 10.1007/978-3-642-19754-3_5
Scopus
Zitationen: 31
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2011
Sprache Englisch
Identifikator ISBN: 978-3-642-19754-3
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097648
Erschienen in Theory and Practice of Algorithms in (Computer) Systems – 1st International ICST Conference (TAPAS 2011), Rome, I, April 18-20, 2011. Proceedings. Ed.: A. Marchetti-Spaccamela
Verlag Springer, Berlin
Seiten 21-32
Serie Lecture Notes in Computer Science ; 6595
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page