Thumbnail
Access Restriction
Subscribed

Author Geisberger, Robert ♦ Rice, Michael N ♦ Sanders, Peter ♦ Tsotras, Vassilis J
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2012
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Contraction Hierarchies ♦ Edge restrictions ♦ Flexible scenario ♦ Route planning ♦ Shortest paths
Abstract In this work, we explore a new type of flexible shortest-path query, in which the query can be dynamically parameterized to constrain the type of edges that may be included in the resulting shortest path (e.g., find the shortest path in a road network that avoids toll roads and low overpasses, respective of the specified vehicle height). We extend the hierarchical preprocessing technique known as Contraction Hierarchies to efficiently support such flexible queries. We also present several effective algorithmic optimizations for further improving the overall scalability and query times of this approach, including the addition of goal-directed search techniques, search space pruning techniques, and generalizing the constraints of the local search. Experiments are presented for both the North American and the European road networks, showcasing the general effectiveness and scalability of our proposed methodology to large-scale, real-world graphs.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2012-03-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 17
Page Count 20
Starting Page 1.1
Ending Page 1.20


Open content in new tab

   Open content in new tab
Source: ACM Digital Library