GIS中时变最短路径理论及算法研究

论文摘要

最短路径问题作为地理信息系统(GIS)、通信、物流管理等领域的研究热点,多年来产生了大量的研究成果。在这些研究成果中,绝大部分是基于静态网络的,也就是说路径寻优中网络弧段的权值是固定不变的。然而实际生活中的很多问题,如交通导航,其网络弧段的权值是随时间变化的,而静态最短路径算法无法解决这类问题。论文基于城市道路网络,对时变最短路径(TDSP)理论及三种常见的时变最短路径问题进行了分析和研究,并从搜索策略和网络分布特征入手对算法进行改进,提高了算法效率。论文的研究成果主要包括：1)利用GIS技术提取了北京市区道路网信息,构建出静态道路网络拓扑结构。2)对城市交通流统计特性进行分析,建立了时变道路网络模型。根据日常出行需要,对三类时变最短路径问题及算法进行研究：出发时间给定的TDSP问题,出发时间域给定的TDSP问题以及到达时间给定的TDSP问题。3)针对D TDSP算法(出发时间给定情形)在搜索过程中的盲目性,采用启发式搜索策略,提出了带启发因子的A_TDSP算法,加快了算法的收敛速度。4)针对A_TDSP算法实现过程中偶尔出现的启发信息不足的情形,根据道路网络特征对算法进行改进。基于网络的统计特征数据,提出了限制搜索区域的R_TDSP算法。5)基于所构建的北京市区时变道路网络平台,对上述所有算法进行了实验仿真。实际系统运行结果及算法实例表明文中所提出算法的正确性和有效性。而且,A_TDSP算法、R_TDSP算法与D_TDSP算法相比,具有明显的优越性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 研究意义
• 1.1 最短路径问题研究历史及现状分析
• 1.3.1 静态最短路径问题的研究
• 1.3.2 时变最短路径问题的研究
• 1.4 论文的研究内容
• 1.5 论文的组织结构
• 2 GIS技术及道路网络分析
• 2.1 GIS概述
• 2.2 数字地图的空间数据
• 2.3 道路网络特征及拓扑结构的构建
• 2.3.1 道路网络的模型与存储结构
• 2.3.2 建立道路网络拓扑结构
• 2.3.3 初始化道路拓扑网络图
• 2.4 本章小结
• 3 传统的搜索策略和最短路径算法
• 3.1 搜索策略
• 3.1.1 宽度优先搜索
• 3.1.2 深度优先搜索
• 3.1.3 两种搜索策略的比较
• 3.1.4 启发式搜索
• 3.2 最短路径算法的分类
• 3.3 Dijkstra算法
• *算法'>3.4 A^*算法
• 3.5 本章小结
• 4 时变最短路径问题理论及算法研究
• 4.1 引言
• 4.2 时变交通网络分析建模
• 4.2.1 交通流统计特性分析
• 4.2.2 时变道路网络模型
• 4.2.3 路段的时间特性及计算方法
• 4.3 城市交通网络的FIFO特性
• 4.4 出发时间给定的TDSP问题
• 4.4.1 TDSP问题的前提说明
• 4.4.2 出发时间给定的TDSP问题定义
• 4.4.3 出发时间给定的TDSP问题理论分析
• 4.4.4 出发时间给定的TDSP算法思路
• 4.4.5 实例分析
• 4.5 出发时间区域给定的TDSP问题
• 4.5.1 出发时间区域给定的TDSP问题定义
• 4.5.2 出发时间区域给定的TDSP算法思路
• 4.6 到达时间给定的TDSP问题
• 4.6.1 到达时间给定的TDSP问题的定义
• 4.6.2 到达时间给定的TDSP问题理论分析
• 4.6.3 到达时间给定的TDSP算法思路
• 4.7 三种TDSP问题的算法仿真
• 4.7.1 构建TDSP算法的仿真平台
• 4.7.2 出发时间给定的TDSP问题仿真研究
• 4.7.3 出发时间域给定的TDSP问题仿真研究
• 4.7.4 到达时间给定的TDSP问题仿真研究
• 4.8 本章小结
• 5 时变最短路径算法的改进
• TDSP算法研究'>5.1 A_TDSP算法研究
• TDSP算法的思想'>5.1.1 A_TDSP算法的思想
• TDSP算法理论分析和算法步骤'>5.1.2 A_TDSP算法理论分析和算法步骤
• 5.1.3 实例分析
• TDSP算法研究'>5.2 R_TDSP算法研究
• TDSP算法的思想'>5.2.1 R_TDSP算法的思想
• TDSP算法的限制区域构造'>5.2.2 R_TDSP算法的限制区域构造
• TDSP算法的具体步骤'>5.2.3 R_TDSP算法的具体步骤
• 5.3 TDSP问题改进算法的仿真
• 5.4 本章小结
• 6 总结
• 致谢
• 参考文献