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

Funke, Stefan; Storandt, Sabine

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

Files

There are no files associated with this item.

Date

2013

Authors

Funke, Stefan

Storandt, Sabine

Collections

Informatik und Informationswissenschaft

Publication type

Contribution to a conference collection

Publication status

Published

Published in

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

Abstract

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.

Subject (DDC)

004 Computer Science

Keywords

route planning; Pareto-optimality; contraction hierarchies

Conference

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

Cite This

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, Jul 11, 2013 - Jul 13, 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, 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>

Bibliography of Konstanz

No