【作者】 郭武斌；

【导师】 胡祥培；

【作者基本信息】 大连理工大学 ， 管理科学与工程， 2009， 博士

【摘要】 多尺度空间数据模型在车辆导航领域具有重要的理论意义和现实意义。在车辆导航系统硬件资源和通讯条件受限的情况下,如何快速精确地获取较优的导航方案是该研究领域面临的一大难题。针对这一难题,本文以提高物流车辆导航路径分析的速度和精度为目标,按照“分解导航地图空间关系到网络中各个节点→滤取对于行车目标重要的网络元素→重新综合生成所需尺度的导航地图”的思路,引入系统科学和社会网络分析相关理论与方法,重点研究导航地图网络节点间连通性的度量、物流车辆导航多尺度空间数据模型的建立及该模型在车辆导航系统中的应用,为车辆导航空间数据分析的快速、精确处理开展探索性研究。本文的具体研究工作如下：(1)基于网络节点重要性的连通性度量指标的研究。现有指标难以精确度量网络节点相对于行车目标的连通性,为此本文提出了一种基于节点重要性的连通性度量指标——相对连通系数,利用该指标来量化与目标节点相关的连通关系集合,将其分解到网络中各个节点上；并可按需合成与指定目标节点集最相关的空间关系；为在实际应用中快速计算该指标,提出了“以形估数”的计算方法,利用与节点相关联的子树形状,快速估计连通关系路径集合的计数规模。(2)基于广义尺度的车辆导航系统空间数据多尺度模型的研究。针对现有模型生成的导航地图路径分析精度难以保证的问题,建立了基于广义尺度的多尺度空间数据模型,为空间数据服务的高精度、按需生成提供了一种定量分析工具；并在此基础上,将上述方法拓展到网络抽样问题的化简中。(3)车辆导航地图分解算法的研究。针对车载终端计算能力难以适应导航地图庞大数据量的问题,构建了基于主成分分析的车辆导航地图分解算法。该算法可以利用车载设备有限的计算能力,获得快速的反应速度和较高的求解精度,为物流车辆导航提供了兼顾速度和精度的解决方案。在求最短路的实验中,该算法在对网络规模作大幅压缩的情况下(压缩比率达到20%-30%),仍有效地控制了网络分解造成的网络分析精度损失,同时将车载终端求最短路的计算时间由秒级降到了百毫秒级。本研究是地理信息科学、系统科学等学科理论和方法的交叉与渗透,为解决车辆导航空间数据分析的快速、精确处理这一热点和难点问题进行了有益的探索。其研究成果在车辆导航和地理信息科学领域具有广阔的应用前景,将在物流车辆实时导航与调度工作中发挥重要作用。更多还原

【Abstract】 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.更多还原