Sensible edge weight rounding for realistic path planning

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

STORANDT, Sabine, 2018. Sensible edge weight rounding for realistic path planning. The 26th ACM SIGSPATIAL International Conference. Seattle, Washington, Nov 6, 2018 - Nov 9, 2018. In: Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems : SIGSPATIAL '18. New York, NY, USA:ACM Press, pp. 89-98. ISBN 978-1-4503-5889-7. Available under: doi: 10.1145/3274895.3274954

@inproceedings{Storandt2018Sensi-44484, title={Sensible edge weight rounding for realistic path planning}, year={2018}, doi={10.1145/3274895.3274954}, isbn={978-1-4503-5889-7}, address={New York, NY, USA}, publisher={ACM Press}, booktitle={Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems : SIGSPATIAL '18}, pages={89--98}, author={Storandt, Sabine} }

<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/44484"> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:title>Sensible edge weight rounding for realistic path planning</dcterms:title> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-09T12:57:53Z</dc:date> <dc:creator>Storandt, Sabine</dc:creator> <dcterms:abstract xml:lang="eng">Real-world route planning problems are conventionally modeled as weighted graphs - either as grid graphs for open spaces or as path/road networks. The edge weights (e.g. Euclidean distances, travel times or energy consumption) are then derived from measurements or estimations. But the resulting weights are often overly precise and demand a lot of space to be stored. In addition, operations on these weights are computationally expensive. The common approach to avoid those problems is to round edge weights to reasonable precisions (e.g. whole meters, seconds or watt). Unfortunately, naive rounding schemes can easily distort the structure of optimal paths in the graph. In this paper, we present a novel rounding framework based on the construction of an overlay graph. We show that a carefully designed overlay graph based on so called contraction hierarchies can accelerate shortest path computations and minimize rounding errors at the same time, while demanding little space on its own.</dcterms:abstract> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44484"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-09T12:57:53Z</dcterms:available> <dcterms:issued>2018</dcterms:issued> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Storandt, Sabine</dc:contributor> <dc:language>eng</dc:language> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account