The computation of shortest paths in a graph is a well-known problem in graph theory. One of the most obvious practical applications is route planning in a road network, i.e., finding an optimal route from a start location to a target location. We assume that a given road network does not change very often and that there are many source-target queries on the same network. Therefore, it pays to invest some time for a preprocessing step that accelerates all further queries.
We present a new speedup technique for route planning that exploits the hierarchy inherent in real-world road networks. In a preprocessing step, we investigate the given road network in order to extract and prepare a hierarchical representation. Our route planning algorithm then takes advantage of this data. It is an adaptation of the bidirectional version of Dijkstra's algorithm, massively restricting its search space.
In several experiments, we concentrate on the computation of fastest routes in Western Europe and the USA. Both networks consist of about 20 million nodes each. Our algorithm preprocesses these networks in 30 minutes using linear space. Queries then take around 2.5 milliseconds to produce optimal routes. This is more than 4 000 times faster than using Dijkstra's algorithm. There are numerous possibilities to further improve and extend our approach.