Thumbnail
Access Restriction
Subscribed

Author Luxen, Dennis ♦ Schieferdecker, Dennis
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Algorithm engineering ♦ Alternative routes ♦ Routing ♦ Shortest paths
Abstract We study the computation of good alternatives to the shortest path in road networks. Our approach is based on single via-node routing on top of contraction hierarchies and achieves superior quality and efficiency compared to previous methods. We present a fast preprocessing method for computing multiple good alternatives and apply this result in an online setting. This setting makes our result applicable in legacy systems with negligible memory overhead. An extensive experimental analysis on a continental-sized real- world road network proves the performance of our algorithm and supports the general systematic algorithm engineering approach. We also show how to combine our results with the competing concept of alternative graphs that encode many alternative paths at once.
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 2015-01-07
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 19
Page Count 28
Starting Page 1
Ending Page 28


Open content in new tab

   Open content in new tab
Source: ACM Digital Library