KIT | KIT-Bibliothek | Impressum | Datenschutz

Time-Dependent Route Planning with Generalized Objective Functions

Batz, Gernot Veit; Sanders, Peter

Abstract:
We consider the problem of finding routes in road networks that optimize a combination of travel time and additional time-invariant costs. These could be an approximation of energy consumption, distance, tolls, or other penalties. The resulting problem is NP-hard, but if the additional cost is proportional to driving distance we can solve it optimally on the German road network within 2.3 s using a multi-label A* search. A generalization of time-dependent contraction hierarchies to the problem yields approximations with negligible errors using running times below 5 ms which makes the model feasible for high-throughput web services. By introducing tolls we get considerably harder instances, but still we have running times below 41 ms and very small errors.



Originalveröffentlichung
DOI: 10.1007/978-3-642-33090-2_16
Scopus
Zitationen: 7
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2012
Sprache Englisch
Identifikator ISBN: 978-3-642-33090-2
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097637
Erschienen in Algorithms - ESA 2012. Ed.: L. Epstein
Verlag Springer, Berlin
Seiten 169–180
Serie Lecture Notes in Computer Science ; 7501
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page