An Alternative Approach to Alternative Routes: HiDAR. Technical Report

Alternatives to a shortest path are a common feature for modern navigation providers. In contrast to modern speed-up techniques, which are based on the unique distance between two locations within the map, computing alternative routes that might include slightly suboptimal routes seems a way more dicult problem. Especially testing a possible alternative route for its quality can so far only be done utilizing considerable computational overhead. This forces current solutions to settle for any viable alternative instead of nding the best alternative routes possible. In this paper we show a new way on how to deal with this overhead in an eective manner, allowing for the computation of high quality alternative routes while maintaining competitive query times.