Experimental Evaluation of Indexing Techniques for Shortest Distance Queries on Road Networks

Shortest distance calculation between two locations in road networks is an important problem and has many applications. This problem has been widely researched for over two decades. Several advanced algorithms have been developed since the last formal evaluation. This paper provides a comprehensive experimental evaluation of these state-of-the-art algorithms. Our evaluation provides several important insights on the advantage/disadvantages of these algorithms, and it enables us to recommend the most suitable algorithm for some application scenarios. We are able to confirm some previous experimental results and raise questions on some others. We also evaluate the effect of a simple path compression technique on these algorithms.