Optimizing Landmark-Based Routing and Preprocessing
Sixth ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS '13)
2013
Conference/Workshop
- Contact persons: Dieter Pfoser , Alexandros Efentakis
- Relevant research project: SimpleFleet
Abstract.
Many acceleration techniques exist for the single-pair shortest path problem on road networks. Most of them have been significantly improved over the years to achieve faster preprocessing times and superior performance. In this spirit, our current work significantly improves the classic ALT (A* + Landmarks + Triangle equality) algorithm. By carefully optimizing both preprocessing and query phases, we managed to effectively minimize preprocessing time to a few seconds, making the ALT algorithm also suitable for dynamic scenarios, i.e., road networks with changing edge weights due to traffic updates. We also accelerated the query phase for both unidirectional and bidirectional versions of the ALT algorithm, providing fast enough query times (including full-path unpacking) suitable for real-time services and continental road networks.