Multi-Scale Spatial Data Model And Algorithm For Vehicle Navigation

Multi-scale spatial data model is a research subject with theoretical and practical significance in the field of vehicle navigation. To meet the demands of real-time vehicle navigation, a multi-scale spatial data model that can precisely obtain the navigation solution in real-time with the limited power of onboard devices need to be constructed. Constructing this kind of model is also a difficult problem in this field.Focusing on constructing a multi-scale spatial data model for real-time vehicle navigation, this paper aims at improving the speed and accuracy of spatial data analysis for vehicle navigation. According to an online and dynamic processing thought of "spatial relationship decomposition→the most relevant vertices selection→sub-network regeneration", this paper utilizes theories and approaches in System Science and Social Network Analysis, and mainly studies the following several problems:the spatial relationship measurement, the multi-scale spatial data model for vehicle navigation, and the application in vehicle navigation. The detailed contents of the research are as follows:(1) The research on the connectivity index to measure the importance of a vertex in a network. A new connectivity index, which we called the relative connectivity coefficient, is proposed to measure the impact of a vertex to another in a network. The spatial relationship of a network can be decomposed to the network vertices by this index. A simplified method is designed to reduce the computational complexity of the relative connectivity coefficient, which uses the shape of the sub-tree rooted by a vertex to evaluate its relative connectivity coefficient.(2) The research on multi-scale spatial data model based on generalized scale for vehicle navigation. The characteristics of real-time vehicle navigation are analyzed, and a multi-scale spatial data model based on generalized scale is proposed, which can generate sub-network to adapt different destination vertex set. A Principal-Component-Analysis-based method and an Analytic-Hierarchy-Process-based method are proposed to calculate the relative connectivity coefficient for multi destination-vertex set. Furthermore, the main idea of this multi-scale spatial data model is applied to a class of network sampling problem to reduce the computational complexity of network analysis. (3) The research on the network decomposition method for vehicle navigation maps. Computational power of onboard devices is too limited to processing spatial data of vehicle navigation maps. A network decomposition method based on the above mentioned multi-scale spatial data model is proposed to solve this problem. The vehicle navigation maps are decomposed into sub-maps in the monitoring center, and these sub-maps can be downloaded to the onboard devices. The most relevant elements to the destinations are extracted from the entire network to compose sub-maps, so that the computational complexity of network analysis on these sub networks can be reduced with less accuracy loss. This method is applied to a case of searching the shortest path in onboard devices. Experimental evaluation shows that this method can effectively control the accuracy loss caused by network decompositions: there is only 13.85% accuracy loss while the sub network's size is reduced to 20.12% of the original network, and the computational time is reduced from second magnitude to 100 microsecond magnitude at the same time.The research in this paper has promoted the interaction and inosculation between Geographic Science and System Science. It is the beneficial exploration for solving the real-time vehicle navigation problems based on multi-scale spatial data model. And equipped with real-time data collection technique, monitoring technique and scheduling technique for logistic vehicles, the research results in this paper can provide decision support for real-time logistic vehicle navigation and scheduling.