Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives

Funke, Stefan; Storandt, Sabine

Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2013

Autor:innen

Funke, Stefan

Storandt, Sabine

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen in

HELMERT, Malte, ed.. Proceedings of the Sixth International Symposium on Combinatorial Search (SoCS-2013), 11 - 13 July 2013, Leavenworth, Washington, USA. Palo Alto, Calif.: AAAI Press, 2013, pp. 214-215. ISBN 978-1-57735-632-5

Zusammenfassung

In this paper we consider a variant of the multi-criteria shortest path problem where the different criteria are combined in an arbitrary conic combination at query time. We show that contraction hierarchies (CH) - a very powerful speedup technique originally developed for standard shortest path queries (Geisberger et al. 2008) - can be adapted to this scenario and lead - after moderate preprocessing effort - to query times that are orders of magnitudes faster than standard shortest path approaches. On the theory side we prove via some polyhedral considerations that the crucial node contraction operation during the CH construction can be performed in polynomial-time, while on the more practical side we complement our theoretical results with experiments on real-world data. Our approach extends previous results (Geisberger, Kobitzsch, and Sanders 2010) which only considered the bicriteria case.

Fachgebiet (DDC)

004 Informatik

Schlagwörter

route planning; Pareto-optimality; contraction hierarchies

Konferenz

The Sixth International Symposium on Combinatorial Search, 11. Juli 2013 - 13. Juli 2013, Leavenworth, WA, USA

Zitieren

ISO 690

FUNKE, Stefan, Sabine STORANDT, 2013. Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives. The Sixth International Symposium on Combinatorial Search. Leavenworth, WA, USA, 11. Juli 2013 - 13. Juli 2013. In: HELMERT, Malte, ed.. Proceedings of the Sixth International Symposium on Combinatorial Search (SoCS-2013), 11 - 13 July 2013, Leavenworth, Washington, USA. Palo Alto, Calif.: AAAI Press, 2013, pp. 214-215. ISBN 978-1-57735-632-5

BibTex

@inproceedings{Funke2013Polyn-46628,
  year={2013},
  title={Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives},
  isbn={978-1-57735-632-5},
  publisher={AAAI Press},
  address={Palo Alto, Calif.},
  booktitle={Proceedings of the Sixth International Symposium on Combinatorial Search (SoCS-2013), 11 - 13 July 2013, Leavenworth, Washington, USA},
  pages={214--215},
  editor={Helmert, Malte},
  author={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/46628">
    <dc:creator>Funke, Stefan</dc:creator>
    <dc:language>eng</dc:language>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-08-07T08:17:23Z</dc:date>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Funke, Stefan</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/46628"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-08-07T08:17:23Z</dcterms:available>
    <dcterms:issued>2013</dcterms:issued>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dcterms:title>Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives</dcterms:title>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract xml:lang="eng">In this paper we consider a variant of the multi-criteria shortest path problem where the different criteria are combined in an arbitrary conic combination at query time. We show that contraction hierarchies (CH) - a very powerful speedup technique originally developed for standard shortest path queries (Geisberger et al. 2008) - can be adapted to this scenario and lead - after moderate preprocessing effort - to query times that are orders of magnitudes faster than standard shortest path approaches. On the theory side we prove via some polyhedral considerations that the crucial node contraction operation during the CH construction can be performed in polynomial-time, while on the more practical side we complement our theoretical results with experiments on real-world data. Our approach extends previous results (Geisberger, Kobitzsch, and Sanders 2010) which only considered the bicriteria case.</dcterms:abstract>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Nein