Cellular Route Planning And Density Adaptive Representation Of Road Network In Vehicle Navigation

Vehicle navigation road network(VNRN) is the basis of vehicle navigation system. Route planning and network representation on navigation device screen of VNRN constitute the core functions of vehicle navigation, which directly impact user experience of the navigation system. Nowadays, some road network characteristics, such as huge network scale, complicated network topology and significant regional differences of road network density, lead to performance degradation of route planning and regional deterioration of network representation. To solve the problem, a cellular route planning method and a density adaptive representation method are proposed. By establishing a cellular logic road network model and its corresponding route planning algorithm, fast and optimal route planning of VNRN can be realized. By designing a representation level adaptive selection method based on hierarchical road network model, homogeneous and reasonable representation of VNRN can be realized.Firstly, the cellular node model is built, which brings a unified extensible structural unit to organize network topology information. The cellular node model decouples the topology information usage dependent among road network objects, which makes the information easy to use in the processes of road network topology optimizing and route planning. Based on the cellular node model, the cellular logic road network is established. In the logicalization process to generate cellular logic network, logic direct connections that span many nodes are built between original not connected two nodes, which optimizes the network topology with reserving the optimum route information of road network. The obtained cellular logic network provides the basis for fast and optimal route planning.Secondly, the cellular route planning algorithm and the optimal vector route reduction method are built. The cellular route planning algorithm accomplishes the expanding procedure of route planning in cellular logic road network, which comprehensively considers the topology information usage of the network, the corresponding relationship of node external and internal topology cost and so on. After the expanding, an optimal cellular route that includes logic direct connections is acquired. With the optimal cellular route, an optimal vector route reduction method is put forward to get the optimal route information corresponding to original road network, which can be used for real navigation. Combined with the fast reduction model, the engineering practicability of the mentioned cellular route planning is guaranteed.Finally, a density adaptive representation method of road network is built. By using hierarchical road network model, the road network representation data in different network level with different density can be provided. Combined with the proposed representation level adaptive method, the most appropriate network representation level of current representation region can be calculated and the most reasonable road network representation can be achieved. At the same time, a two-stage implementation scheme of density adaption is designed to alleviate computational complexity of vehicle navigation device, which ensures the application of the density adaptive method.Tests show that: the cellular route planning of road network can greatly improve route planning speed while guaranteeing the optimality of the obtained route, which obviously improves user experience; the density adaptive representation of road network can realize appropriate road network representation anywhere with only little additional computing resources of navigation devices, which improves representation effects of VNRN.