车载导航路网的胞式化寻路与密度自适应

发布时间：2018-04-12 16:24

本文选题：车载导航 + 路网　；参考：《清华大学》2015年博士论文

【摘要】：车载导航路网是车辆导航系统运行的基础,而车载导航路网的寻路与其在导航设备屏幕上的表达构成车辆导航系统的核心功能,直接决定用户对于导航的使用体验。目前,实际路网规模庞大、道路连通关系复杂,路网分布地区性差异较大,导致车载导航路网的寻路性能出现下降、路网表达出现区域性恶化等问题。对此,本文提出了车载导航路网的胞式化寻路与密度自适应,通过建立胞式逻辑路网模型及其相应寻路算法实现路网的快速最优寻路,通过建立分层路网模型下的表达层级自适应算法实现路网的均匀合理表达。首先,建立胞式结点模型,利用统一的可扩展结构单元组织路网拓扑信息。在数据使用上解除了路网拓扑信息间的耦合,便于路网拓扑优化过程和实际寻路过程对拓扑数据的使用。在此基础上,构建胞式逻辑路网模型,通过拓扑连接的逻辑化过程,在不丢失路网最优路径信息的前提下优化路网拓扑结构,建立跨越多结点的逻辑直连,为快速最优寻路提供数据基础。其次,建立胞式化寻路算法与最优矢量路径还原方法,实现胞式逻辑路网下的最优路径信息获取。其中,胞式化寻路算法完成胞式逻辑路网中的寻路拓展,综合考虑拓展过程中的拓扑信息使用,结点内、外部拓扑代价对应等问题,得到包含逻辑直连的最优胞式路径;最优矢量路径还原方法将最优胞式路径还原至与原始路网对应,得到可供导航使用的最优矢量路径信息,结合快速还原模型,保证车载导航路网胞式化寻路的工程实用性。最后,建立车载导航路网的密度自适应方法。通过分层路网模型提供具有密度梯度变化的路网数据,结合表达层级自适应算法得到当前表达区域最为适宜的路网表达层级,进而实现该区域路网的合理表达。同时,设计两段式密度自适应方法,减轻车载导航设备的运算压力,确保密度自适应方法的工程应用。相关试验表明:车载导航路网的胞式化寻路在保证路径最优性的前提下,能够大幅度提高寻路速度,改善导航寻路的用户体验;车载导航路网的密度自适应在仅额外占用极少量导航设备计算资源的条件下,能够实现任意位置的路网合理表达,改善导航中路网的表达效果。
[Abstract]:The vehicle navigation network is the basis of the vehicle navigation system, and the road finding of the vehicle navigation network and its expression on the navigation equipment screen constitute the core function of the vehicle navigation system, which directly determines the user's experience of navigation.At present, the actual road network scale is huge, the road connection relation is complex, the distribution of the road network is very different, which leads to the decline of the road finding performance of the vehicle navigation network and the regional deterioration of the road network expression.In this paper, the cellular routing and density adaptation of vehicular navigation network are proposed. The cellular logic network model and its corresponding routing algorithm are established to realize the fast and optimal route finding of the road network.The uniform and reasonable representation of the road network is realized by establishing the hierarchical adaptive algorithm under the hierarchical road network model.Firstly, the cellular node model is established, and the topological information of road network is organized by the unified extensible structure unit.In the use of the data, the coupling between the topological information of the road network is uncoupled, and it is convenient to use the topology data in the process of the topology optimization of the road network and the practical road finding process.On this basis, the cellular logic network model is constructed. Through the logical process of topological connection, the topology structure of the road network is optimized without losing the optimal path information of the road network, and the logical direct connection across multiple nodes is established.It provides the data base for fast and optimal route finding.Secondly, the cellular route finding algorithm and the optimal vector path restoration method are established to obtain the optimal path information under the cellular logic network.Among them, the cellular routing algorithm completes the routing expansion in the cellular logic network. Considering the use of topological information in the expansion process and the corresponding topological cost within the node and the external topology, the optimal cellular path including the logical direct connection is obtained.The optimal vector path restoration method restores the optimal cellular path to the original road network, and obtains the optimal vector path information for navigation. Combined with the fast restoration model, it ensures the engineering practicability of cellular route finding in the vehicular navigation network.Finally, the density adaptive method of vehicle navigation network is established.The hierarchical road network model is used to provide the road network data with the change of density gradient, and combining with the expression level adaptive algorithm, the most suitable network expression level for the region is obtained, and the reasonable representation of the regional road network is realized.At the same time, a two-stage density adaptive method is designed to reduce the operational pressure of the vehicle navigation equipment and ensure the engineering application of the density adaptive method.The related experiments show that the cellular route finding of the vehicle navigation network can greatly improve the speed and the user experience of the navigation search under the premise of ensuring the optimal path.The density adaptation of vehicle navigation network can realize the reasonable expression of the road network at any position and improve the expression effect of the navigation network under the condition that only a few additional computing resources are occupied by the navigation equipment.
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：U495

【相似文献】