| 摘要 |
Customizable route planning is a technique for computing point-to-point shortest paths in road networks. It includes three phases: preprocessing, customization, and queries. The preprocessing phase partitions a graph into multiple levels of loosely connected components of bounded size and creates an overlay graph for each level by replacing each component with a clique connecting its boundary vertices. Clique edge lengths are computed during the customization phase. The query phase comprises a bidirectional Dijkstra's algorithm operating on the union of the overlay graphs and the components of the original graph containing the origin and the destination. The customization may be made even faster, enabling a wide range of applications including highly dynamic applications and on-line personalized cost functions. In an implementation, to compute overlay arc costs, Dijkstra's algorithm may be supplemented or replaced by other techniques, such as contraction and the Bellman-Ford algorithm.
|
