Continuous Route Planning over a Dynamic Graph in Real-Time
Tianlun Dai, Wenchao Zheng, Jiayue Sun, Cun Ji, Tao Yun Zhou, Mingtong Li, Wei Ping Hu, Ziqiang Yu · Procedia Computer Science · 2020
Central to many location-based services is the route planning over road networks. The immense scale of urbanization and the sharp increase of vehicles on the road make it urgent to explore a navigation system to provide effective and effcient services to users. To achieve it, we need to continuously search a good route from the user’s current position to the destination as the travel time of every road probably changes frequently. Here, the road network is abstracted as a dynamic graph and the fluctuating travel time of each road is viewed as the varying weight of the corresponding edge. Some work has investigated the problem and most of them is to find the exact shortest path for a given query on the entire graph. In fact, it is unnecessary and an approximate optimal path obtained with a much smaller cost also can satisfy the requirements. In this paper, we propose a continuous route planning algorithm with the idea of greedy principle and substantially speed up processing by reducing the query area.