License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2019.10
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11422/
Go to the corresponding OASIcs Volume Portal

Hespe, Demian ; Sanders, Peter

More Hierarchy in Route Planning Using Edge Hierarchies

pdf-format:
OASIcs-ATMOS-2019-10.pdf (0.6 MB)

Abstract

A highly successful approach to route planning in networks (particularly road networks) is to identify a hierarchy in the network that allows faster queries after some preprocessing that basically inserts additional "shortcut"-edges into a graph. In the past there has been a succession of techniques that infer a more and more fine grained hierarchy enabling increasingly more efficient queries. This appeared to culminate in contraction hierarchies that assign one hierarchy level to each vertex.
In this paper we show how to identify an even more fine grained hierarchy that assigns one level to each edge of the network. Our findings indicate that this can lead to considerably smaller search spaces in terms of visited edges. Currently, this rarely implies improved query times so that it remains an open question whether edge hierarchies can lead to consistently improved performance. However, we believe that the technique as such is a noteworthy enrichment of the portfolio of available techniques that might prove useful in the future.

BibTeX - Entry

@InProceedings{hespe_et_al:OASIcs:2019:11422,
  author =	{Demian Hespe and Peter Sanders},
  title =	{{More Hierarchy in Route Planning Using Edge Hierarchies}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{10:1--10:14},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Valentina Cacchiani and Alberto Marchetti-Spaccamela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11422},
  doi =		{10.4230/OASIcs.ATMOS.2019.10},
  annote =	{Keywords: shortest path, hierarchy, road networks, preprocessing}
}

Keywords: shortest path, hierarchy, road networks, preprocessing
Collection: 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
Issue Date: 2019
Date of publication: 15.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI