论文部分内容阅读
路径查询是出行信息服务应用中的一项重要功能。随着互联网和移动通讯技术的发展,传统路径查询已由单用户、静态环境转变为多用户、动态环境。针对多用户并发路径查询需求,目前的服务器端导航系统和在线地图网站多采用服务器端调度、任务分配等方式应对高并发情况。动态变化的实时交通状态信息也未能参与到路径查询规划的过程中,无法满足应用需求。 针对多用户和动态环境下的路径查询需求,本文从路径查询过程的各个环节,包括数据、算法、计算策略等,研究了多用户并发环境下的动态最优路径查询优化方法。论文主要内容包括下面四个部分: 1.总结了在线地图网站路径查询服务、高并发解决方案、最短路径查询、缓存技术的现状与进展。提出了多用户并发环境下路径查询优化研究的思路:通过路网数据改造融合动态交通信息、尽可能以可重用的模糊查询代替计算密集的路径规划;并寻求路径查询效率和路径查询精度的定量均衡控制; 2.分析了路网的中介中心性拓扑指标和其层级性能,将传统的静态中介中心性指标升级为动态中介中心性指标。利用中介中心性的层级性对道路网进行动态分层,将动态交通状态信息的影响通过动态分层体现出来。提出了基于动态层次空间推理的路径查询算法,既保留了路网分层概化所带来的路径计算的高效性,又结合了动态交通信息,使路径计算结果更加合理; 3.借鉴数据库管理系统中缓存的思想,探讨了将路径查询的计算过程转换为查询过程的可能性,分析了路径查询起始终止点和查询缓存中路径结果之间的关系,从而确定了路径查询缓存的查询模式和结构设计。针对精确查询和模糊查询需求而提出的缓存的路网层级架构设计,既保证了在原始路网上的精确路径查询计算,又使得缓存路径结果的使用率最大化,大幅度提高了多用户并发环境下路径查询的效率,同时保证了路径查询结果的精度; 4.提出了启发式路径规划算法精度/效率均衡控制模型。基于符号回归方法,以A*算法为例,对A*启发式路径搜索算法效率和精度之间的函数关系进行合理化拟合,在每次路径搜索查询之前,根据并发用户响应效率和精度需求,预先动态确定A*算法中启发式因子取值,同时推算出计算结果精度。对于给定路网数据集,只需一次预先计算就可以得到路径搜索效率和精度的均衡控制曲线。研究所采用的方法也适用于其他路径启发式搜索算法的精度效率均衡控制过程。