面向城市交通的简化路网模型及路径规划问题的研究

论文摘要

随着城市中交通堵塞情况的越来越严重,出行者对简洁、高效的路径规划算法的要求日益迫切。如何根据现实的道路交通状况构建合理而有效的路网模型,并在路网模型的基础上设计出满足出行者需求的简捷有效的路径规划有着非常重要的意义。在实际应用中,比较常见的路网模型都考虑了比较复杂的交通限制信息（例如:路宽、车流量、由于施工、交通事故等对道路进行限行的规定）,而路径规划的目标也会在路网模型的基础上根据出行者的要求进行多目标或单目标的规划。目前,国内外研究提出的道路交通网络模型比较多,包括各种复杂的静态路网模型、动态路网模型、以及实时路网模型等。这些复杂路网模型虽然在一定程度上可以更好地描述现实交通路况,但这些模型考虑的因素普遍比较繁多,比如为了计算交叉口的时延就考虑排队等待的长度、环形道的长度、交叉口的车流量等,另外还有考虑动态交通流以及红绿和交叉口延时等,因此导致路径规划算法的设计过于繁琐,不仅计算效率显著下降,而且所需道路信息难以实时精确地采集,从而不能很好地响应城市内出行者的导航要求。针对这种情况,本文重点研究了如何在保证路径规划效果的前题下,尽可能考虑较少的因素来简化路网模型,更好地响应城市出行者的导航要求。论文研究主要贡献如下:①首先,考虑城市交通的基本特点,研究提出了一种简洁实用的的简化静态路网模型。并在该模型的基础上设计了改进的Dijkstra算法,即S-Dijkstra算法,来解决城市路径规划问题。该模型仅要求采集很少的道路通行信息,却能简接地反映道路转弯延时、通行速度、红绿灯和斑马线等复杂因素对车辆通行时间的间接影响,具有简单实用的特点。②进而,通过按照城市交通动态变化的特殊规律,将一个工作日内道路通行时段划分为不同的时间段,对上述简化模型进行扩展,构建了一种基于时间段划分的简化动态路网模型。并给出了能在该模型上正常运行的改进Dijkstra算法,即D-Dijkstra算法,来解决适合城市内汽车导航的动态路径规划问题。③最后,本文通过将限定搜索的矩形区域法和分层方法结合运用到上述提出的路径规划算法中,设计出了缩小搜索空间的高效的Dijkstra算法,新方法通过对路径搜索空间的降维,能显著提高导航算法的运行效率。本文提出的简化路网模型,所需数据采集简化,容易实施,算法简单高效,能够满足于城市路径导航的实际需要,对相关研究开发具有较好的参考价值。

论文目录

• 中文摘要
• 英文摘要
• 1 引言
• 1.1 研究背景与意义
• 1.2 国内外研究现状
• 1.3 论文研究内容
• 1.4 论文组织结构
• 2 简化的静态路网模型及其路径规划算法
• 2.1 简化的静态路网模型的描述及其应用
• 2.1.1 常见的路网模型及其特点
• 2.1.2 简化的静态路网模型的研究背景
• 2.1.3 简化的静态路网模型
• 2.2 简化的静态路网模型中的路径规划算法
• 2.2.1 经典的Dijkstra 算法
• 2.2.2 简化的静态路网模型中改进的Dijkstra 算法的数据结构
• 2.2.3 S-Dijkstra 算法的描述
• 2.3 本章小节
• 3 基于时间段划分的动态路网模型及其路径规划算法
• 3.1 基于时间段划分的动态路网模型
• 3.1.1 动态路网模型的研究背景
• 3.1.2 基于时间段划分的动态路网模型
• 3.2 求解动态路网模型中的最优路径算法
• 3.2.1 动态路网模型中的改进的Dijkstra 算法的数据结构
• 3.2.2 D-Dijkstra 算法的具体步骤
• 3.3 本章小节
• 4 两种模型及其对应算法的有效性验证
• 4.1 模拟软件系统介绍
• 4.1.1 软件开发环境
• 4.1.2 软件功能模块
• 4.2 简化的静态路网模型及S-DIJKSTRA 算法的实验及分析
• 4.2.1 实验数据的获取
• 4.2.2 静态路网模型中不考虑堵塞的实验
• 4.2.3 静态路网模型中考虑交叉口和环形道堵塞的实验
• 4.2.4 静态路网模型中考虑转弯限制的实验
• 4.3 基于时间段划分的动态路网模型及D-DIJKSTRA 算法的实验及分析
• 4.3.1 实验数据的获取
• 4.3.2 动态路网模型中路径规划的实验
• 4.3.3 不考虑交通堵塞和考虑交通堵塞下的对比实验
• 4.4 本章小节
• 5 动态路网模型中缩小搜索空间的改进 DIJKSTRA 算法
• 5.1 缩小搜索空间的方法及其特点
• 5.1.1 缩小搜索空间的常见算法
• 5.1.2 缩小搜索空间算法的优点
• 5.2 改进的缩小搜索区域的高效DIJKSTRA 算法
• 5.2.1 算法的步骤
• 5.2.2 算法的优点
• 5.3 本章小节
• 6 总结与展望
• 6.1 本文研究工作与总结
• 6.2 展望
• 致谢
• 参考文献
• 附录
• A. 作者在攻读学位期间发表的论文目录
• B. 作者在攻读学位期间取得的科研成果目录