基于局部搜索的gps地图匹配算法

《基于局部搜索的gps地图匹配算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、原文翻译基于局部路径搜索的浮动车数据地图匹配算法摘要道路交通流信息的获取对于城市交通控制与管理是必要的。浮动车数据（FCD）是采样城市大规模道路网络交通流的新兴技术，它可以提供有效的手段来模拟和分析道路交通状况。地图匹配是FCD的关键技术之一。典型的导航地图匹配技术不适合处理浮动车数据大采样间隔。通过分析浮动车数据的特点，我们首先提出基于局部路径搜索的浮动车数据地图匹配算法。可以利用之前已经匹配的GPS点信息显著减少搜索空间。矩形置信区的构造用于减少候选路段的数量。该算法不仅可以达到高精度浮动车数据定位要求，而且可以监测车辆的运动轨迹。实验结果表明，我们的方法适用于

2、不同的浮动车数据采样间隔。关键字：浮动车数据；局部路径搜索；地图匹配；采样间隔；矩形置信区1.引言道路交通流信息的获取对于城市交通控制、管理以及交通规划是必要的。现有的道路交通流采集方法主要采用定点模式，包括感应圈、微波、雷达和视频技术，这些方法有一些缺点如覆盖区域限制、成本高及维修困难等。与定点模式采样相比，FCD具有覆盖区域广、易于维护及成本低等优点。它可以提供大规模的动态交通信息，因此有效运用于实时指导、管理和控制中。FCD在过去几十年受到显著关注。地图匹配算法已经成为浮动车数据研究的一个课题。到目前为止，浮动车数据地图匹配主要依赖于导航地图匹配算法。导航地图

3、匹配算法在文献中被归纳为四类：几何分析法、拓扑法、概率法和其他的高级方法。常用的几何分析法包括点-点、点-线、线-线地图匹配算法。考虑道路的形状，这些方法利用空间路网数据的几何信息实现地图匹配，具有简单、快速的优点。由于没有考虑道路之间的连接关系，这些方法在交叉口、平行道路、环形道路下的匹配效果较差。基于拓扑的地图匹配算法是指结合路段的几何特性、路段之间连通性和邻接关系的地图匹配算法。但拓扑法没有考虑车辆的行驶方向和速度信息，所以此方法法对异常值非常敏感。概率匹配法在定位附近构建椭圆或是矩形的误差区。误差区域可以由GPS定位误差的方差来确定。误差区域内的道路路段是候

4、选方案。这些算法使用行驶方向、连接性、远近程度等来进行地图匹配。高级地图匹配算法利用卡尔曼滤波、证据理论、模糊逻辑和神经网络等方法。这些方法在相同条件下优于其他三种方法，但是高级地图匹配算法通常需要更多的输入数据，并有一些缺点如较慢的匹配速度实现复杂等。导航地图匹配算法在高采样频率下也能够获得好的结果（如1Hz）。然而FCD的采样间隔从10s到2分钟之间，并且它可能由于噪声和错误随时间变化。因此很难利用导航地图匹配算法处理浮动车数据。到目前为止，只有少量与浮动车数据地图匹配的工作成果。Liaoetal等人提出了基于数据结构交叉点的双向启发式地图匹配算法以应对十字路口

5、。该算法利用交叉的数据结构将交叉点从普通地图匹配中分离出来，并且降低了浮动车数据地图匹配的错误。然而由于增加了过多的节点和链路使得计算复杂性显著增加。基于GIS数字地图网格划分。Wangetal提出一种快速的浮动车数据地图匹配算法。这种方法设计了一种道路网络结构，其将道路网络划分为两个层次，并将道路网络划分成网格。然而要确定网格的大小却十分困难。这项工作的目的是研究适用于数据量大及动态的采样的浮动车数据的地图匹配算法。根据对浮动车数据的特征分析，我们首先提出了基于局部路径搜索的浮动车数据地图匹配算法。最大可能距离作为启发式信息以减少搜索空间。矩形置信区中心位置由GP

6、S确定，它的建立用来确定候选匹配路段的有效性，并且在中心位置的车的方向和距离用来纠正与浮动车数据匹配的路段。本文的其余部分安排如下：第2节介绍浮动车数据匹配，启发式局路径搜索原理和矩形置信区方法提出的解释。第3节给出了浮动车数据地图匹配算法的描述。在第4节，给出了实验测试的结果并讨论。最后一节总结了全部工作。1.FCD地图匹配原理地图匹配是浮动车数据技术的关键技术。每个浮动车数据记录包括车辆ID、经度与维度、时间、行驶方向、瞬时速度等。FCD技术主要被应用于给交通管理者和使用者提供道路网络的交通状况。考虑到通信成本，浮动车数据采样的频率是10到120秒之间。环境的干

7、扰可能导致两个FCD的时间间隔大于30秒在远程监测中心。针对FCD动态采样间隔我们提出了一个基于局部路径搜索的的地图匹配算法。该方法可以确定车辆在两个GPS位置间的移动路径，这也是基于浮动车数据技术获取交通指导、控制和交通状态估计所必要的。该算法主要包括三个步骤：局部路径搜索，矩形置信区确定和地图匹配。对与浮动车数据包中第一个GPS点的位置固定问题，考虑到相关信息不可用，我们采用点-线法定位以获取高精度的GPS点。1.1局部路径搜索GIS（GIS：地理信息系统）数字地图是一个有向连通图。该匹配算法首先搜索当前匹配点的前一个匹配点作为起始点，获得候选路径集合。由于