Efficient best path monitoring in road networks for instant local traffic information
Shuo Shang, Ke Deng, Kai Zheng · 2010
The shortest path problem has been well studied previ-ously. To improve the utility, the traffic conditions can be modeled to associate a weight to each road segment. The recent trend is to apply data mining techniques over use history which usually covers a long period of time such as months. However, this method fails to reflect the instant (i.e. temporary) traffic conditions change such as traffic accident or road work. Due to the temporary nature, the local instant traffic conditions makes more sense when an object is moving in road networks. In this work, we in-vestigate the shortest path monitoring problem while the instant traffic conditions in local region update repeatedly around a moving object to a given destination. A simple way is to apply A * algorithm repeatedly. However, the weakness is obvious. Because only a small fraction, i.e. the local area, of the whole networks have changed and the other parts keep intact. That means, for many vertices, that their paths (or the lower bounds of their paths) to the des-tination are still valid. This motivates us to maintain these information and reuse in the following computations. Our method is based on two tree structures where one records the previous computing results and the other aims to re-duce the search space of subsequent processing. The ex-periments over real data set demonstrate an improvement of processing efficiency by one degree of magnitude at a small memory cost. In addition, the tree can be shared when monitoring the shortest paths for several moving ob-jects to the same destination.