大规模探测车数据的地图匹配算法研究

论文摘要

城市交通堵塞已经成为我国城市发展的瓶颈，严重影响到了人们的生活质量和幸福水平。为了改善和提高城市交通服务水平，世界主要发达国家都在发展智能交通系统。作为先进的新型交通信息采集方式，探测车系统为智能交通系统提供基础数据。地图匹配技术是探测车系统的关键技术，直接影响探测车数据质量。本文的研究主题就是探测车系统的地图匹配技术。与实时导航系统数据不同，探测车历史数据一般具有时间间隔长和距离间隔大的特点。经过文献调研和数据特点分析，本文把地图匹配问题抽象成网络最短路径问题，并建立整数规划模型。为了使最短路径尽可能经过GPS点，本文在目标函数中对GPS点附近路段赋予了较小的权重。然后，本文提出把地图两次栅格化的全局地图匹配算法。在算法中，本文把地图匹配过程分为数据预处理、路段匹配和点匹配三个阶段。数据预处理阶段，把地图划分成两类栅格，并抽取与栅格存在覆盖关系的路段；路段匹配阶段，根据GPS点经纬度坐标计算其所处栅格位置，进而获得候选路网；点匹配阶段，把GPS点垂直投影到匹配路段，并用插值法计算路段旅行时间。本文提出的算法，对大规模探测车数据的地图匹配，只在正式匹配开始前做一次栅格与全路网路段关系的判断，而不需要计算GPS点到各路段的距离。本文采用了堆栈化的Dijkstra算法搜寻最短路径。在对算法的实证研究中，本文基于MapInfo二次开发了地图匹配结果检查程序。首次定义了正确匹配路线，并将其作为算法匹配正确率的衡量指标,以弥补传统方法的不足。经过对1000个旅程样本多次试验和人工检查，本文对地图匹配不正确情况进行了严格分类，并且为算法选取了合适的参数。针对局部路段匹配不正确的情况，本文利用正确路段附近GPS点的特点，在基本不增加算法复杂度的前提下，改进了算法，并取得了良好的效果。最后，在进行大规模探测车数据地图匹配试验中，本文的算法在正确率和运行速度两方面均有较好的表现，尤其是运行速度有数十倍的提高。因此，本文不仅具有理论上的创新意义，也具有较高的实际应用价值。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 选题背景
• 1.2 选题意义
• 1.3 本文工作
• 1.3.1 研究目标和技术路线
• 1.3.2 本文完成的工作
• 1.3.3 论文安排
• 第2章 探测车系统及地图匹配技术综述
• 2.1 探测车系统
• 2.1.1 基本概况
• 2.1.2 发展历史与现状
• 2.1.3 数据采集的特点
• 2.1.4 数据误差和采样频率
• 2.2 地图匹配技术
• 2.2.1 描述与简介
• 2.2.2 数学模型
• 2.2.3 地图匹配算法
• 第3章 名古屋交通数据描述与预处理
• 3.1 名古屋数字地图
• 3.1.1 路网的抽象化和数字化
• 3.1.2 数字地图地图的显示
• 3.2 探测车数据的采集
• 3.2.1 探测车的类型
• 3.2.2 探测车数据结构
• 3.3 探测车数据的过滤和抽样
• 3.3.1 数据过滤
• 3.3.2 数据抽样
• 第4章 地图匹配算法的研究
• 4.1 NPVD-AM 的特点
• 4.1.1 时间间隔
• 4.1.2 距离间隔
• 4.2 最短路径问题
• 4.3 地图匹配模型
• 4.3.1 地图匹配问题重述
• 4.3.2 整数规划
• 4.3.3 数学模型
• 4.4 地图匹配算法
• 4.4.1 第一阶段数据预处理
• 4.4.2 第二阶段路段匹配
• 4.4.3 第三阶段点匹配
• 第5章 地图匹配算法的实证研究
• 5.1 检验手段
• 5.2 参数选择
• 5.2.1 匹配结果类型
• 5.2.2 第一类栅格大小的确定
• 5.2.3 缩短率的选取
• 5.2.4 第二类栅格大小的确定
• 5.3 改进地图匹配算法
• 5.4 地图匹配结果及分析
• 5.5 算法性能分析
• 5.5.1 匹配正确率
• 5.5.2 运行速度
• 第6章 总结与展望
• 6.1 全文总结
• 6.2 研究展望
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果