Back to Search Start Over

Candidate Sets for Alternative Routes in Road Networks

Authors :
Dennis Luxen
Dennis Schieferdecker
Source :
ACM Journal of Experimental Algorithmics. 19:1-28
Publication Year :
2015
Publisher :
Association for Computing Machinery (ACM), 2015.

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.

Details

ISSN :
10846654
Volume :
19
Database :
OpenAIRE
Journal :
ACM Journal of Experimental Algorithmics
Accession number :
edsair.doi...........31fd6411757d989ea47f8c60f96d5708
Full Text :
https://doi.org/10.1145/2674395