《基于局部搜索的GPS地图匹配算法》由会员分享，可在线阅读，更多相关《基于局部搜索的GPS地图匹配算法（10页珍藏版）》请在金锄头文库上搜索。
1、原文翻译基于局部路径搜索的浮动车数据地图匹配算法摘要道路交通流信息的获取对于城市交通控制与管理是必要的。浮动车数据（FCD）是采样城市大规模道路网络交通流的新兴技术，它可以提供有效的手段来模拟和分析道路交通状况。地图匹配是FCD的关键技术之一。典型的导航地图匹配技术不适合处理浮动车数据大采样间隔。通过分析浮动车数据的特点，我们首先提出基于局部路径搜索的浮动车数据地图匹配算法。可以利用之前已经匹配的GPS点信息显著减少搜索空间。矩形置信区的构造用于减少候选路段的数量。该算法不仅可以达到高精度浮动车数据定位要求，而且可以监测车辆的运动轨迹。实验结果表明，我们的方法适用于不同的浮动车数据采样间隔。关
2、键字：浮动车数据；局部路径搜索；地图匹配；采样间隔；矩形置信区1. 引言道路交通流信息的获取对于城市交通控制、管理以及交通规划是必要的。现有的道路交通流采集方法主要采用定点模式，包括感应圈、微波、雷达和视频技术，这些方法有一些缺点如覆盖区域限制、成本高及维修困难等。与定点模式采样相比，FCD具有覆盖区域广、易于维护及成本低等优点。它可以提供大规模的动态交通信息，因此有效运用于实时指导、管理和控制中。FCD在过去几十年受到显著关注。地图匹配算法已经成为浮动车数据研究的一个课题。到目前为止，浮动车数据地图匹配主要依赖于导航地图匹配算法。导航地图匹配算法在文献中被归纳为四类：几何分析法、拓扑法、概率
3、法和其他的高级方法。常用的几何分析法包括点-点、点-线、线-线地图匹配算法。考虑道路的形状，这些方法利用空间路网数据的几何信息实现地图匹配，具有简单、快速的优点。由于没有考虑道路之间的连接关系，这些方法在交叉口、平行道路、环形道路下的匹配效果较差。基于拓扑的地图匹配算法是指结合路段的几何特性、路段之间连通性和邻接关系的地图匹配算法。但拓扑法没有考虑车辆的行驶方向和速度信息，所以此方法法对异常值非常敏感。概率匹配法在定位附近构建椭圆或是矩形的误差区。误差区域可以由GPS定位误差的方差来确定。误差区域内的道路路段是候选方案。这些算法使用行驶方向、连接性、远近程度等来进行地图匹配。高级地图匹配算法利
4、用卡尔曼滤波、证据理论、模糊逻辑和神经网络等方法。这些方法在相同条件下优于其他三种方法，但是高级地图匹配算法通常需要更多的输入数据，并有一些缺点如较慢的匹配速度实现复杂等。导航地图匹配算法在高采样频率下也能够获得好的结果（如1Hz）。然而FCD的采样间隔从10s到2分钟之间，并且它可能由于噪声和错误随时间变化。因此很难利用导航地图匹配算法处理浮动车数据。到目前为止，只有少量与浮动车数据地图匹配的工作成果。Liao et al等人提出了基于数据结构交叉点的双向启发式地图匹配算法以应对十字路口。该算法利用交叉的数据结构将交叉点从普通地图匹配中分离出来，并且降低了浮动车数据地图匹配的错误。然而由于增
5、加了过多的节点和链路使得计算复杂性显著增加。基于GIS数字地图网格划分。Wang et al提出一种快速的浮动车数据地图匹配算法。这种方法设计了一种道路网络结构，其将道路网络划分为两个层次，并将道路网络划分成网格。然而要确定网格的大小却十分困难。这项工作的目的是研究适用于数据量大及动态的采样的浮动车数据的地图匹配算法。根据对浮动车数据的特征分析，我们首先提出了基于局部路径搜索的浮动车数据地图匹配算法。最大可能距离作为启发式信息以减少搜索空间。矩形置信区中心位置由GPS确定，它的建立用来确定候选匹配路段的有效性，并且在中心位置的车的方向和距离用来纠正与浮动车数据匹配的路段。本文的其余部分安排如下
6、：第2节介绍浮动车数据匹配，启发式局路径搜索原理和矩形置信区方法提出的解释。第3节给出了浮动车数据地图匹配算法的描述。在第4节，给出了实验测试的结果并讨论。最后一节总结了全部工作。2. FCD地图匹配原理地图匹配是浮动车数据技术的关键技术。每个浮动车数据记录包括车辆ID、经度与维度、时间、行驶方向、瞬时速度等。FCD技术主要被应用于给交通管理者和使用者提供道路网络的交通状况。考虑到通信成本，浮动车数据采样的频率是10到120秒之间。环境的干扰可能导致两个FCD的时间间隔大于30秒在远程监测中心。针对FCD动态采样间隔我们提出了一个基于局部路径搜索的的地图匹配算法。该方法可以确定车辆在两个GPS
7、位置间的移动路径，这也是基于浮动车数据技术获取交通指导、控制和交通状态估计所必要的。该算法主要包括三个步骤：局部路径搜索，矩形置信区确定和地图匹配。对与浮动车数据包中第一个GPS点的位置固定问题，考虑到相关信息不可用，我们采用点-线法定位以获取高精度的GPS点。2.1 局部路径搜索GIS（GIS：地理信息系统）数字地图是一个有向连通图。该匹配算法首先搜索当前匹配点的前一个匹配点作为起始点，获得候选路径集合。由于城市道路网络规模庞大，所以引入了最大可能行驶距离作为路径搜索的限制条件，从而降低搜索算法的复杂度。它的定义如下： (1)这里是车辆城市道路上所允许的最高速度，是车辆在两个相邻GPS点的时
8、间间隔。路径搜索的终止条件为： (2)其中，是路径长度，是由于环境干扰造成的GPS误差 。搜索空间可以通过引入最大可能距离显著降低。在遍历路网后，所有满足公式(2)且不是回路的路径都是候选路径。2.2 矩形置信区的确定经过局部路径搜索处理所得到的候选匹配路径集还是较大。因此，定义矩形置信区以进一步减少候选路径的数量。矩形置信区的确定根据中心点和距离（如图1所示）。具体描述如下。假设是当前GPS匹配点，是上一个匹配点。中心点的坐标是(,)， 的坐标是(,)，这里的和是经度，和是纬度。矩形置信区的定点坐标可以根据到每一个边和中心点的距离来计算。纬度的误差可以由公式(3)获得。 (3)这里。经度的误
9、差可以有公式(4)和(5)计算得到。 (4)(5)最终，矩形置信区的顶点坐标可以如下获得：矩形置信区可用于进一步选择候选匹配的路径。如果候选路段的结尾路段在矩形置信区内，则该路段是有效的。下一步是确定匹配路段。候选路段是否被选取取决于纠正后的浮动车数据记录中的车俩的方向信息。如果车辆方向和和候选道路结束方向的差满足误差范围（如15度），那么这条路保留，否则，将它从候选路段集合中除去。最终，从固定点到终点之间的所有候选路段都是符合计算要求的候选路径。其中具有最短距离的就是目标匹配。GPS固定点由匹配路段的结束来确定。3. FCD地图匹配的描述设为GPS误差阈值，是方向角误差阈值，为车辆的最大行驶
10、速度。基于局部路径搜索的FCD地图匹配算法描述如下。初始化参数、和；如果当前的待处理的GPS点是浮动车数据包中的第一个点，则利用点-线法进行匹配处理；否则重复以下步骤；为前一个GPS匹配点，取同一辆车FCD中的GPS数据赋值给计算，从开始遍历路网，一个无回路且满足的路径是匹配的候选路径，将其存储在，这里的是路径长度，矩形置信区由坐标顶点确定：从集合删除路段终端不在矩形置信区的路径，计算候选路段终点方向和FCD记录中车辆方向的差值，如果，则将该候选路段保留，否则从集合去除，对于集合中的所有候选路段，计算路段终端和GPS点之间的距离，距离最短的路段将会被选取，将点投影在路段终端，直到处理完所有的F
11、CD记录。4. 试验与讨论为了评价这个算法，我们调查了中国合肥市道路网络的相关数据。通过2000多条FCD记录建立一个采样库以验证我们的算法。首先，分别用我们的算法和“点-线”法进行较准确的试验。在实验中，FCD的采样间隔是10秒钟，一共使用了5组数据FCD数据包，每一组有400条FCD记录。试验结果记录在表1，从表1中我们可以看出我们算法的匹配准确度达到85.2%，相应的“点-线”发匹配准确度达到82.4%。另外，我们分别采用了50秒和100秒的FCD记录以测试采样间隔对于该算法的影响。在这个试验中，选取了三组试验。每一组有200条FCD记录。试验结果在表2中显示。很明显我们的算法对于不同FCD采样间隔的匹配精度不会有大的变化。5. 结论FCD地图匹配是城市交通动态路线指导的关键技术之一。导航地图匹配方法并不适用于处理大采样间隔的FCD记录。我们通过分析FCD记录的特点，提出了基于局部路径搜索的的FCD地图匹配算法。FCD时间信息用来显著减少搜索空间。此外，引入矩形置信区的概念以减少候选匹配路径。该算法匹配精度高且对于不同采样间隔适应性好。它可以实现FCD地图匹配并同时识别车辆行驶轨迹。这项工作提供了一个高效的FCD地图匹配方法。
