KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficient Route Compression for Hybrid Route Planning

Batz, Gernot Veit; Geisberger, Robert; Luxen, Dennis; Sanders, Peter; Zubkov, Roman

Abstract (englisch):
We describe an algorithmic framework for lossless compression of route descriptions. This is useful for hybrid route planning where routes are computed by a server and then transmitted to a client device in a car using some mobile radio communication where bandwidth may be low. Compressed routes are represented by only a few via nodes which are the connection points when the route is decomposed into unique optimal segments. To reconstruct the route efficiently a client device needs basic but fast route planning capability. Contraction hierarchies make this approach fast enough for practice: Compressing takes only a few milliseconds. And previous experiments suggest that a client can decompress each route segment virtually instantaneously. So, as the segments can be decompressed successively while driving, it is not likely that the driver experiences any delay except for the time needed by the mobile communication.

DOI: 10.1007/978-3-642-34862-4_7
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2012
Sprache Englisch
Identifikator ISBN: 978-3-642-34862-4
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097636
Erschienen in Design and analysis of algorithms: 1st Mediterranean Conference on Algorithms. Ed.: G. Even
Verlag Springer Verlag
Seiten 93–107
Serie Lecture Notes in Computer Science ; 7659
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page