A route planning algorithm for the shortest distance based on the division road network

摘要

A division route planning algorithm for the shortest distance is proposed in the paper. The algorithm promotes searching efficiency and shortens calculating time. This paper first introduces the division road network which is different from traditional road network. The division road network model divide a road network into several division road networks. Vehicle navigation system can be accomplished in these division road networks. These division road networks are connected by TransferNodes and TransferLinks which are defined in ISO 19133 and extended in the division road network model. These division road networks can combine into an integrated road network or be divided further. Topology relationship of the road network is still integrated. The division route planning algorithm for the shortest distance is based on the division road network. The division route planning algorithm constructs the division searching strategy to shorten the route planning time by dividing the road network. A practical application example of the algorithm in real-time vehicle navigation systems is given. And the experimental results show that the result is correct and the time for calculating the shortest path between two arbitrary points within the road network can be shortened efficiently.