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

摘要

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

目录

声明

摘要

第一章 绪论

1．1 研究背景与研究意义

1．2 国内外研究现状

1．2．1 车辆导航系统的国内外发展现状

1．2．2 路径规划问题的国内外研究现状

1．3 存在问题分析

1．3．1 大规模路网运算效率问题

1．3．2 动态回避交通拥堵问题

1．4 研究内容与论文结构

1．4．1 本文主要内容

1．4．2 论文结构

第二章 时间依赖的路网模型

2．1 基本路网模型的改进思路

2．1．1 时间依赖的基本路网模型

2．1．2 基本路网模型存在问题的实例分析

2．1．3 改进思路及原理

2．2 基于边成本分析的改进路网模型

2．2．1 多因素属性参数定义

2．2．2 影响边成本的综合分析

2．3 模型中拥堵路段的处理

2．3．1 路段平均行驶速度

2．3．2 拥堵路段处理

2．3．3 交通拥堵划分标准

2．4 本章小结

第三章 用分层限制区域算法求解路径规划问题

3．1 分层限制区域路径规划算法求解路径规划问题简介

3．1．1 依道路空间分布特性划分路网搜索区域的研究

3．1．2 基于道路等级的分层限制区域路径规划算法思想

3．2 大规模路网矩形区域限制策略现有算法存在问题

3．2．1 静态道路等级不能完全表达实际通行能力

3．2．2 实时导航的动态路径规划能力差

3．2．3 没有充分考虑交通拥堵的实时状况

3．3 分层限制区域路径规划算法的改进

3．3．1 区域限制策略

3．3．2 结合道路等级和实际通行能力的分层策略

3．3．3 交通拥堵转移策略

3．3．4 具有方向引导机制的分层限制区域路径规划算法

3．4 本章小结

第四章 基于分层限制区域的蚁群算法改进

4．1 基于分层限制区域的单种群蚁群算法改进

4．1．1 基本蚁群算法原理

4．1．2 能见度函数的改进

4．1．3 分层限制区域及交通拥堵对转移概率的改进

4．1．4 基于分层限制区域的单种群蚁群算法

4．2 多种群蚁群算法的信息素共享策略

4．2．1 多种群策略

4．2．2 种群内信息交流原则

4．2．3 种群问信息交流原则

4．2．4 拥堵路段信息交流原则

4．3 基于分层限制区域的多种群蚁群算法改进

4．3．1 多种群蚁群算法

4．3．2 分层限制区域的多种群蚁群算法

4．4 本章小结

第五章 实验结果与分析

5．1 实验背景及介绍

5．2 交通网络的数据表达

5．3 基于分层限制区域的单种群蚁群算法实验对比与分析

5．3．1 算法初始参数设定

5．3．2 实验结果与分析

5．4 基于分层限制区域的多种群蚁群算法实验对比与分析

5．4．1 算法初始参数设定

5．4．2 实验结果与分析

5．5 本章小结

第六章 总结与展望

6．1 本文主要工作

6．2 展望

参考文献

发表论文和科研情况说明

致谢