详情

原文传递基于分层区域限制的车辆导航路径规划问题研究

论文题名：	基于分层区域限制的车辆导航路径规划问题研究
关键词：	车辆导航系统;路径规划;区域限制;蚁群算法
摘要：	车辆导航系统作为智能交通系统核心的内容之一，旨在减少交通拥挤和交通事故，但是随着城市交通路网规模度、复杂度日益增大，交通拥挤和交通事故压力日益增大。尤其面对越来越庞大的城市道路网，最短路径算法计算量大，而且交通拥堵实时变化，现有导航系统无法满足出行者对躲避拥堵道路的要求。因此，考虑大规模路网交通拥堵的最短路径规划问题已成为当前研究的热点问题。本文从三个方面开展研究: 　　(1)针对时间依赖路网模型不能完全体现道路属性信息的缺点，建立基于边成本分析的时间依赖路网模型。模型中的道路属性及路口属性以集合形式表现，道路属性集合依附于路网模型边集合，路口属性集合依附于路网模型节点集合;定义道路属性集合内参数及路口属性集合内参数，给出参数综合影响边成本的公式，并以边属性的路段平均行驶速度参数为标准确定路段不同程度拥堵状态并将拥堵状态分成五个等级。　　(2)针对多层级路网每层路网均需逐层参与搜索且不能动态躲避通行能力差道路的缺点，通过建立矩形限制区域降低参与路径搜索的路网节点数量以提高算法运算效率;基于道路空间分布特点和不同等级道路通行能力划分高低层路网，算法优先搜索高层路网达到保证路径行程时间最短目的;基于实时变化的交通拥堵动态切换算法搜索的高层、低层路网，在高层规划路径出现交通拥堵情况下，根据交通拥堵程度适时转入低层路网重新规划路径，达到躲避交通不便道路的目的。　　(3)针对分层限制区域单种群蚁群算法运算时间长、局部收敛的劣势提出多种群蚁群路径优化改进算法。通过改进基于分层限制区域单种群蚁群算法状态转移公式，建立多种群蚁群信息素共享与更新策略，设计了种群内部信息交流、种群间信息交流、拥堵路段信息交流结合的策略，使多个种群共同维护一个相同的路网结构图完成一次路径搜索，通过聚集所有子种群最优路径确定信息素的更新方案，并将更新信息素传递给子种群实现信息素共享达到全局最优的目的。　　本文实验仿真采用速度拟合函数随机分配速度值方案，将分层限制搜索区域Dijkstra算法、不分层不限制搜索区域单种群蚁群算法、分层限制搜索区域单种群蚁群算法、分层限制区域多种群蚁群算法进行对比，从算法运行时间和规划路径质量两个方面分析。结果表明，在大规模路网情况下，基于分层限制搜索区域的策略具有一定优势，而同样采用分层限制搜索区域策略，蚁群算法平均搜索时间明显小于Dijkstra算法的搜索时间。实验也表明，虽然多种群蚁群算法规划路径长度较长，但是时间要小于其它算法，原因是考虑了交通拥堵因素，出现交通拥堵适时转入低层路网选择走拥堵道路附近的支路或次干路，从而节省了因拥堵造成的等待时间。
作者：	杨智新
专业：	计算机应用技术
导师：	宁红云
授予学位：	硕士
授予学位单位：	天津理工大学
学位年度：	2014
正文语种：	中文