Hierarchical and Exact Fastest Path Computation in Time-dependent Spatial Networks

With real-world spatial networks the edge travel-times are time-dependent, where the arrival-time to an edge determines the actual travel-time on the edge. To speed up the path computation, exact and approximate techniques for computation of the fastest path in time-dependent spatial networks are presented. An exact fastest path computation technique based on a time-dependent A* search can significantly improve the computation time and storage complexity of existing approaches. Moreover, for applications with which approximate fastest path is acceptable, the approximate fastest path computation technique can improve the computation time by an order of magnitude while maintaining high accuracy (e.g., with only 7% increase in travel-time of the computed path on average). With experiments using real data-sets (including a variety of large spatial networks with real traffic data) the efficacy of the disclosed techniques for online fastest path computation is demonstrated.