Customizable Contraction Hierarchies

Computing optimal routes in road networks has many applications such as navigation, logistics, traffic simulation or web-based route planning. Road networks are commonly formalized as weighted graphs and the optimal route is formalized as the shortest path in this graph. Unfortunately, road graphs tend to be huge in practice with vertex counts in the tens of millions, rendering Dijkstra's algorithm [18] impracticable for interactive use: It incurs running times in the order of seconds even for a single path query. For practical performance on large road networks, preprocessing techniques that augment the network with auxiliary data in a (possibly expensive) offline phase have proven useful. See [4] for an overview.