Continuous Route Planning over a Dynamic Graph in Real-Time

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, it is necessary 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, the authors propose a continuous route planning algorithm with the idea of greedy principle and substantially speed up processing by reducing the query area.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01751130
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jul 28 2020 3:09PM