A quick route planning algorithm in vehicle navigation system

A quick route planning algorithm is proposed in the paper to improve searching efficiency and shorten calculating time. In order to reduce the data of computing and storage, the road network is divided into several small road networks called division road networks at first. The division road network is connected by boundary nodes and boundary edges. The start point and the end point are belonging to different division road networks. Then, the shortest path among the start point, the end point and boundary nodes is searched, the shortest path from the beginning point to the end point can be found by combining these shortest paths. By dividing the road network, searching space is reduced and searching time is shortened. Moreover, due to the shortest paths between boundary nodes are calculated and saved in computer in advance, so the computing time is shortened a lot. In the end of the paper, a practical application example of the algorithm in realtime vehicle navigation systems is given. The experimental results show that it's a good and efficiency way of calculating the shortest path between two arbitrary points within the road network.© (2007) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.