Shortest Path Computation On Dynamic Road Networks

To compute exact point-to-point shortest path in road networks is one of the real world applications of graph algorithms. The classic Dijkstra’s algorithm and its bidirectional variant, developed in1950’s and1960’s respectively, turn out to be far too slow in large road networks. This classical problem received considerable attention over the past decade. Furthermore, significant progress has been made in large road networks, leading to methods which are faster than Dijkstra’s algorithm by several orders of magnitudes. Goal-directed search and hierarchical techniques are two typical classes of algorithms, both of which have undergone rapid development. In addition, clever combinations of the two, i.e., adding goal-direction to hierarchical methods, give out the most promising results in many aspects. Though the performances are good in experimental studies, no theoretical bounds are known to support these observation results. This is because there is no strict definition to describe road networks, a specific type of graph which is sparse, almost planar, and reveals hierarchical properties.However, most of the existing algorithms are static in the following sense:in order to handle the incoming shortest path queries they need large amounts of auxiliary data, which leads to a time-consuming preprocessing. Therefore, those techniques can hardly arrange with changes in reality such as traffic jams and road works even if these changes are rather small compared to the whole road network. This paper focuses on the dynamic version of the most advanced routing technique, Transit-Node Routing, which has a one million speedup compared to Dijkstra’s algorithm in experimental performance. We keep the transit nodes unchanged, and efficiently recompute the affected access nodes and distance table required by the query algorithm without starting from scratch. In real world applications, these updates usually accumulate and our method will take advantage of this feature to deal with several updates in batch. Extensive experiments are carried out to evaluate the preprocessing time, space overhead, query performance and update runtime.