Scalability of Route Planning Techniques

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BLUM, Johannes, Sabine STORANDT, 2018. Scalability of Route Planning Techniques. Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018). Delft, Jun 24, 2018 - Jun 29, 2018. In: DE WEERDT, Mathijs, ed., Sven KOENIG, ed., Gabriele RÖGER, ed., Matthijs T. J. SPAAN, ed.. Twenty-Eighth International Conference on Automated Planning and Scheduling. Palo Alto, Ca.:AAAI Press, pp. 20-28. ISBN 978-1-57735-797-1

@inproceedings{Blum2018Scala-44807, title={Scalability of Route Planning Techniques}, url={}, year={2018}, isbn={978-1-57735-797-1}, address={Palo Alto, Ca.}, publisher={AAAI Press}, booktitle={Twenty-Eighth International Conference on Automated Planning and Scheduling}, pages={20--28}, editor={de Weerdt, Mathijs and Koenig, Sven and Röger, Gabriele and Spaan, Matthijs T. J.}, author={Blum, Johannes and Storandt, Sabine} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dcterms:abstract xml:lang="eng">In this paper, we thoroughly analyze the scaling behavior of several state-of-the-art route planning techniques for road networks, all of which rely on preprocessing. One goal is to determine which technique is most suitable to be used on huge networks. To be able to conduct scalability studies in a clean way, we first describe a new kind of road network generator that allows to produce road networks even larger than that of our planet with similar properties as real networks. We then carefully implement several preprocessing-based route planning techniques, as contraction hierarchies, hub labels and transit nodes, to study their space consumption as well as their search spaces in different sized networks. This allows to derive functions that describe their empirical scaling behavior for the first time. We also compare our functions to existing theoretical bounds. We show that several of our results can not be sufficiently explained by the theoretical investigations conducted so far. Hence our results encourage a further look for road network models that allow for better predictions.</dcterms:abstract> <dc:creator>Blum, Johannes</dc:creator> <dc:contributor>Blum, Johannes</dc:contributor> <dcterms:isPartOf rdf:resource=""/> <dc:contributor>Storandt, Sabine</dc:contributor> <dcterms:title>Scalability of Route Planning Techniques</dcterms:title> <dspace:isPartOfCollection rdf:resource=""/> <dc:creator>Storandt, Sabine</dc:creator> <dc:date rdf:datatype="">2019-02-01T13:32:32Z</dc:date> <dcterms:available rdf:datatype="">2019-02-01T13:32:32Z</dcterms:available> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:language>eng</dc:language> <bibo:uri rdf:resource=""/> <dcterms:issued>2018</dcterms:issued> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account