Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks

Lade...
Vorschaubild
Dateien
Blum_2-azmjbiivodmm5.pdf
Blum_2-azmjbiivodmm5.pdfGröße: 788.15 KBDownloads: 181
Datum
2021
Autor:innen
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Hybrid
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
Journal of Combinatorial Optimization. Springer. 2021, 42(2), pp. 231-257. ISSN 1382-6905. eISSN 1573-2886. Available under: doi: 10.1007/s10878-021-00777-3
Zusammenfassung

Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. However, for many of these techniques it is not fully understood why they perform so remarkably well, and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. Still, these parameters may be large in case the network contains grid-like substructures—which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. Furthermore, our preprocessing methods are close to the ones used in practice and only require expected polynomial time.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Shortest path planning, Bounded growth model, Road network dimensions
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BLUM, Johannes, Stefan FUNKE, Sabine STORANDT, 2021. Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks. In: Journal of Combinatorial Optimization. Springer. 2021, 42(2), pp. 231-257. ISSN 1382-6905. eISSN 1573-2886. Available under: doi: 10.1007/s10878-021-00777-3
BibTex
@article{Blum2021-08Subli-44520.2,
  year={2021},
  doi={10.1007/s10878-021-00777-3},
  title={Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks},
  number={2},
  volume={42},
  issn={1382-6905},
  journal={Journal of Combinatorial Optimization},
  pages={231--257},
  author={Blum, Johannes and Funke, Stefan and Storandt, Sabine}
}
RDF
<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/server/rdf/resource/123456789/44520.2">
    <dc:creator>Storandt, Sabine</dc:creator>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44520.2"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-08-05T11:13:09Z</dcterms:available>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:creator>Blum, Johannes</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44520.2/1/Blum_2-azmjbiivodmm5.pdf"/>
    <dc:language>eng</dc:language>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44520.2/1/Blum_2-azmjbiivodmm5.pdf"/>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dcterms:issued>2021-08</dcterms:issued>
    <dcterms:abstract xml:lang="eng">Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. However, for many of these techniques it is not fully understood why they perform so remarkably well, and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. Still, these parameters may be large in case the network contains grid-like substructures—which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. Furthermore, our preprocessing methods are close to the ones used in practice and only require expected polynomial time.</dcterms:abstract>
    <dc:rights>terms-of-use</dc:rights>
    <dc:contributor>Blum, Johannes</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-08-05T11:13:09Z</dc:date>
    <dc:creator>Funke, Stefan</dc:creator>
    <dc:contributor>Funke, Stefan</dc:contributor>
    <dcterms:title>Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks</dcterms:title>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Unbekannt
Diese Publikation teilen

Versionsgeschichte

Gerade angezeigt 1 - 2 von 2
VersionDatumZusammenfassung
2*
2021-08-05 11:10:19
2019-01-10 15:14:54
* Ausgewählte Version