Back to Search
Start Over
Candidate Sets for Alternative Routes in Road Networks
- 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.
- Subjects :
- Computer science
business.industry
Computation
Legacy system
Algorithm engineering
Machine learning
computer.software_genre
Theoretical Computer Science
Contraction hierarchies
Shortest path problem
Overhead (computing)
Preprocessor
Artificial intelligence
Data mining
Routing (electronic design automation)
business
computer
Subjects
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