基于浮动车GPS轨迹点数据的地图匹配算法研究

摘 要：文章研究基于GPS浮动车轨迹点数据的地图匹配原理及地图匹配方法。提出了基于GPS点到校正点的匹配，并且利用连续几个GPS点的轨迹确定结果，最终获取较为正确的路网匹配结果，实现城市道路网络浮动车GPS样本数据与电子地图的匹配速度与精度。为实时掌握与分析道路交通状态提供基础数据。

关键词：浮动车；GPS；地图匹配；轨迹点

引言

建立城市交通综合信息平台，通过对庞大的城市交通网络中的实时交通信息进行深入分析，为改善城市交通信息服务水平，提高决策科学性，缓解城市交通拥堵提供了基础。交通综合信息平台的数据支撑来源于交通基础信息的实时采集，科学决策的依据在于数据分析的快速、准确。

GPS浮动车是获取道路实时车速便捷有效的方法，可以通过车载GPS定位信息获取道路实时车速及运行状态（拥堵、畅通、缓行），其作为一种便捷廉价、可操作性高的车速采集手段已经被各城市普遍采用，特别是公交车与出租车安装车载GPS设备最为常见。通过对公交车及出租车的GPS返回数据与城市道路网的匹配、分析来获取道路的实时车速，进而实现对道路状态的有效判断。因此确保GPS浮动车轨迹点数据与信息平台电子地图快速、准确匹配是管理决策的基础，研究准确适用的GPS浮动车轨迹点数据的地图匹配算法是非常重要的。

1 GPS数据的地图匹配原理

地图匹配（Map-Match）简称MM技术，就是利用电子地图的路网信息和GPS数据来实行对车辆行驶准确位置的确定，它是一种定位误差修正技术。

浮动车所上报的GPS数据中包含有经纬度等地理信息，但这些GPS坐标只能反映车辆位置情况，而不能与实际路网路段直接相关联。因此，车辆在路网中行驶的情况，必须要依赖于地图匹配算法来完成车辆位置信息与路网位置的关联。

地图匹配算法的直接目的是将GPS测得的车辆位置或行驶轨迹，与现有的电子地图道路路段数据进行比较，继而找到车辆所处的道路，计算出浮动车辆在道路上所处的位置。一般地图匹配过程有以下几个步骤：

（1）通过对获取的GPS数据的预处理及匹配模板的分析、描述，提取出点和道路的轨迹特征。

（2）根据对地图匹配规则的制定，计算出GPS样本和匹配模板两者的相似度、匹配度。

（3）选取待匹配点距离最近或者是轨迹相似度、匹配度最高的道路曲线模板，可更正匹配样本的位置或轨迹，作为匹配结果[1]。

图1 地图匹配原理图

地图匹配原理一般可分成两个过程来表达：即寻找GPS待匹配点最可能归属的道路，并将GPS浮动点投影到这条它所归属的道路上面。

以上两个过程的关键在于需找GPS待匹配点最可能归属的道路，基本的思想即是在GPS点四周一定范围内搜索所有的可匹配点，然后根据匹配度计算，淘汰匹配度较低的点，选出最优点。并将此最优点作为GPS浮动车车辆的当前行驶路线。这样，寻找最优点成为算法性能优劣的关键所在，如果搜索范围过大，需对周围各条道路一一筛选，增加了算法计算量，导致匹配速度缓慢。反之，如果搜索范围过小，则有可能未能准确寻找到最佳匹配点，出现匹配错误，降低匹配的准确率。

2 基于GPS轨迹点的浮动车地图匹配算法

可实现地图匹配的算法很多，在GPS数据量极大，且算法应用的场景为实时车速展示，需要选择一个合适的方法，保证匹配的准确性和匹配速度。因此文章提出的地图匹配算法是基于GPS点到校正点的匹配，并且利用连续几个GPS点的轨迹确定结果，最终获取较为正确的路网匹配结果。

2.1 网格匹配

Step1：计算GPS点所归属网格。

当在系统中导入GPS数据信息后，可从这些原始数据中提取出坐标信息。可设为（x，y）。然后对该GPS坐标信息进行可信度检测，首先取网格划分中最大和最小的两个坐标点，其中最大的坐标点位于地图的右上角，假设为（xm，ym），最小的坐标点则位于地图的左下角，假设为（xn，yn）。如果待匹配点坐标（x，y）满足以下条件：

则认为该GPS点在研究坐标范围之内，转到下一步计算。

Step2：搜寻所在网格匹配

根据该GPS点的坐标信息，在网格列表中搜寻其所属的网格。假设网格编号为G0，若

（x，y）∈{G0}

则判定该点位于G0网格内。

在搜寻到所在网格后，将所在网格G0中的所有校正点加入到待匹配集合。但在该匹配中需要注意的是当GPS点与网格边距离小于1/3时，则需要将其相邻网格（G1……G8）所包含的校正点一并加入待匹配集合，进行匹配度计算。（见图2）

2.2 节点匹配

Step1：计算GPS与路段的距离和方向差

在网格匹配中搜寻出的校正点集合被称为待匹配集合。需要将GPS点与带匹配集合中的各个校正点进行匹配，找寻出最佳匹配点。

计算GPS点与各待匹配校正点之间的距离。设GPS点坐标为（x，y），GIS校正点坐标为（xr，yr），由于两点距离较近，两点接近于平面，则可根据平面距离公式

得出GPS点与各校正点之间的距离d。

计算GPS点与路段各校正点之间的夹角。取GPS数据的角度为？渍0，再与网格内的GIS路段校正点的切线方向角度？渍r（取正北方向为0°）求差值。可得出GPS点与路段方向的夹角α。

Step2：匹配度计算

匹配度是判断校正点优劣的重要标准，是描述GPS点与一条道路的匹配程度，用实际算法所求得的数值进行量化，匹配度越大，就认为发出这个GPS数据的浮动车越有可能位于这条道路。对于匹配度的计算，主要考虑的是GPS与路段的距离及其与路段的夹角。

图3 GPS点匹配

Step3：Confidence Point（CP点）判断

针对GPS浮动车地图匹配的特殊性，本文提出了Confidence Point判断。所谓Confidence Point，就是可信点[8]。判断是否为CP点，主要判断其所有匹配点是否位于同一路段。

由于浮动车地图匹配的最终目的是为城市各条道路得到路段平均速度提供起点、终点以及时间信息，而当车辆距离路口（包括城市立交路口、普通平面交叉路口、主辅路的出入口等）比较近时，由于GPS浮动车减速、并线等驾驶行为导致GPS数据中的方向信息等变化较大、准确性降低，使得系统比较难以确定车辆的准确位置。 但是考虑到GPS浮动车地图匹配的一个最终目的是获取路况实时信息，因此，如果无论车辆当前在哪条道路上行驶，只要能确定车辆必定通过或者必定离开某个路口，就可以根据GPS浮动车辆的下一个GPS定位数据确定其这一段时间的行驶轨迹。

因此当GPS数据处于路口节点或分合流点附近时，它所对应的匹配点并不在同一路段上，系统将这样的数据判定为非CP点，作为延迟匹配点，利用行驶路径进行匹配。反之，若GPS数据所对应的匹配点位于同一路段，则系统将其判定为CP可信点，对其各匹配点进行匹配度计算。

其中对于CP可信点，系统按照step3中匹配度计算中所确定的方法进行匹配度计算。取匹配度最大的点为最佳匹配点。对于非CP点，则转入下一步。

Step4：延迟匹配

对于上一步所提到的非CP点，并无法通过单一的GPS数据匹配来确定浮动车的确切位置，这时就需要通过相同浮动车的多个GPS数据来联合判断车辆的行驶路线轨迹。

图5 非CP点延迟匹配示意图

假设某浮动车连续的n个GPS数据组成的序列Pn（n=1，2，3，……，k），满足以下条件：

（1）P1点为CP点，P2为非CP点，且k小于延迟匹配的允许最大值；（2）Pk为已经确定的CP点，并能按照地图匹配方法正确寻找到最佳匹配点。

则可利用前后两个CP点P1和Pk，寻找这相邻两个CP点的最短路径L。再利用最短路径L对P2，P3，Pn-1进行匹配，去掉不属于L的匹配点，再取最大匹配度点作为最佳匹配点。

3 结束语

文章所使用的地图匹配方法通过获取GPS浮动车数据，利用GPS坐标信息，通过比对电子地图各条路段的地理信息，将浮动车位置关联到路网上。

研究表明，该匹配算法具有以下优缺点：

（1）匹配速度快。由于将电子地图网格化，避免了将GPS数据坐标与地图中所有节点坐标的一一进行计算，而是仅选取了比较小范围的节点进行匹配。提高了运算、匹配的效率。

（2）匹配精度较高。由于在匹配方法上采取了多种方法进行联合使用，针对不同位置的GPS数据点运用不同的匹配方法，保证了每个GPS数据点匹配的准确性。特别是基于连续GPS点轨迹来判断位置，使得匹配的结果更为准确。

重庆市政府在2011年开展“重庆市交通综合信息平台”建设，信息平台对重庆城区的干路网交通信息进行采集与汇聚。文章的研究依托交通信息平台的基础数据，研究成果应用于重庆市主城区路网运行情况的评估与监控，经过实测对比，验证了该算法的良好精度和适用性。

参考文献

[1]张其善，吴金培，杨康凯.智能车辆定位导航系统及应用[M].北京：科学出版社，2002.

[2]肖锋.面向道路交通状态监测的GPS与GIS数据预处理关键技术研究[D].重庆大学硕士毕业论文，2008.

[3]重庆市交通综合信息平台试点工程技术报告[R].2012.

[4]孙棣华，等.基于预处理的城市路网拓扑结构构建算法[J].计算机工程与应用，2008（08）.

[5]车莉娜.车辆导航定位中的关键技术研究[D].辽宁工程技术大学硕士论文，2008.

[6]Weiliang ZENG， Zhaocheng HE and Xiwei SHE. Data Repair Method for Real Time Urban Link Speed Estimation，ASCE2011.

[7]王华.GIS城市道路最短路径算法研究[J].测绘科学，2010.

[8]章威，等.基于大规模浮动车数据的地图匹配算法[J].交通运输系统工程与信息，2007（4）.

[9]程志华，刘小勇.基于GIS 的城市路网拓扑关系的自动建立及最短路径分析[J].新疆农业大学学报，2007.

作者简介：孙静怡，女，昆明理工大学交通工程学院副教授。