浮动车地图匹配算法研究

王美玲，程 林

北京理工大学自动化学院，北京100081

1 引 言

浮动车系统是伴随着ITS新技术应用而在近几年发展起来的新型交通流信息采集技术。一般使用大量的出租车或公交车作为浮动车，通过已安装的GPS车载装置和无线通信设备，将车辆信息（如时间、速度、坐标、方向等参数）实时地传送到浮动车信息中心。浮动车输出的动态实时交通信息不仅能为相关部门提供道路交通实况，而且可作为道路建设规划、拥堵缓解等各项工作中定量数据分析的基础［1－4］。

地图匹配技术是浮动车数据处理的关键技术之一，只有判断出车辆在哪条道路上行驶，才能将GPS数据转化为道路的交通状态［5－7］。

浮动车系统具有数据量大，实时性要求高和采样点间隔比较大等特点。浮动车地图匹配在应用于现代城市复杂路网时主要面对3大关键技术难点［8－9］：① 数据需要实时处理，数据量较大，因此对系统的计算速度要求较高；② 数据间隔一般较大，导致定位点信息之间的相关性比较差；③ 现代城市路网密集且结构复杂，因此对系统的匹配容错率要求较高。

文献［10—11］所述的传统导航地图匹配算法，由于GPS采样点的间隔仅为1s，因此比较容易获得准确的轨迹曲线作为匹配样本，能够实现基于轨迹曲线的线到线的地图匹配。然而，以北京市为例，每辆浮动车每分钟上传一个GPS点数据，前后两点间的相关性差决定了浮动车系统无法采用线到线的地图匹配方法；此外，浮动车系统的数据量大，反映在单个GPS定位点上，其匹配时间远少于1s。可见，传统的导航地图匹配算法不能直接应用于浮动车系统。

浮动车实时路况处理技术在我国各大城市还处于示范阶段，目前参与北京市浮动车系统的车辆约35 000辆，每辆车如果每分钟上传一个GPS数据，那么数据处理中心每天接收到的数据量就有5000余万条。随着浮动车数量的日益增多，文献［1—9］所述的浮动车地图匹配算法已难以满足当前应用环境下准确性与实时性的要求。可见，提高浮动车地图匹配的准确性与实时性，是需要进一步研究的课题。

2 路网构建

道路网络的精度和属性结构直接关系到地图匹配算法的性能。为此，本文首先给出Super－Map GIS平台下的路网构建方法。

2.1 拓扑处理

以经过配准后的栅格地图为背景，通过以直线代替曲线的方式创建道路中心线，将曲线道路分解为若干直线段；对于异面道路，合理设置非打断线参数，以真实再现立体交通；完成拓扑处理［12］。

将路网中的假节点称为形状点，图1给出拓扑处理后的部分道路网络。

图1 部分道路网络Fig.1 Part of road network

2.2 属性编辑

地图匹配算法将利用道路网络的如下属性：

（1）路段编号SmID；

（2）路段起点SmFNode；

（3）路段终点SmTNode；

（4）路段正向阻力SmResistanceA；

（5）路段反向阻力SmResistanceB；

（6）路段长度SmLength；

（7）路段方向类别Head。

其中，（4）、（5）、（7）为需要编辑与创建的字段。在SuperMap Deskpro中道路网络的部分属性如图2所示。

图2 SuperMap Deskpro中路网属性Fig.2 Attribute of road network in SuperMap Deskpro

其中，Head为新建字段，字段值“1”表示双向道路，将SmResistanceA与SmResistanceB均设置为0；字段值“2”表示单向道路，且方向为起点F→终点T，将SmResistanceA与SmResistanceB分别设置为0和∞（由10 000表示）；字段值“3”表示单向道路，且方向为终点T→起点F，将SmResistanceA与SmResistanceB分别设置为∞（由10 000表示）和0。

3 地图匹配算法

基于浮动车数据的地图匹配算法流程如图3所示。

图3 地图匹配算法流程Fig.3 Process of map matching algorithm

在地图匹配前，首先进行浮动车GPS数据的预处理，剔除存在漂移错误以及记录为空载、驻车及停运的数据，以求真实反映当前路况；然后进行坐标变换，与电子路网地图采用的坐标系一致。

3.1 基于网格的候选路段确定

按照一定的步长l（本文取70m），将导航电子地图道路网络从上到下、从左到右网格化分块，将道路网络分为M×N个相同的网格，记为Grid （i），（i＝0，1，…，MN－1），记道路网络左下角的坐标为O （X0，Y0），如图4所示。

图4 道路网络的网格分块Fig.4 Grid block of road network

设某定位点坐标为（x，y） ，则其所在的网格为Grid （［（Y0＋Ml －y）／l ］N＋［（x－X0）／l］）。

对于每一个网格 Grid （i），将其扩展为边长为2l的网格 Grid′（i），如图5中虚线所示，记录在网格 Grid′（i）之内（如路段AB、BC、AE、BD、DF、DE）及与网格 Grid′（i）相交（如路段AH、EG）的路段编号，将各路段作为落入网格G rid （i）内的GPS定位点的候选路段。

图5 候选路段的确定Fig.5 Candidate road determination

3.2 基于权重的定位点匹配

算法为每条候选路段计算权重，包括距离权重WD、航向权重WH及可达性权重WR，并计算每条候选路段的权重总和W，以此确定匹配路段和匹配点。

3.2.1 距离权重

距离权重表示为［13］

式中，DW表示距离权重系数D表示定位点到候选路段的距离，当定位点到候选路段的垂足不在候选路段上时，分别计算定位点到候选路段起点F和终点T的距离，并选择较小值，如图6所示，定位点P到候选路段BD和EF的距离分别为PH和PE的长；DTH为距离阈值，本文将DTH设置为25m。

图6 定位点到候选路段的距离Fig.6 Distance between the GPS point and the candidate road

因此，当0≤D≤2DH时，f（D ）取值在1到－1间，并随D的增加而线性减小。当D＞2DH时，将f（D ）设置为－1。

3.2.2 航向权重

航向权重表示为

式中，HW表示航向权重系数；f（Δθ ）＝cos（Δθ），Δθ表示车辆航向与路段方向的夹角。设θ表示GPS接收机输出的车辆航向，范围是［0，2π），正北方向为0；θ0表示道路倾角，范围是［0，π），正北方向为0；（xf，yf）和（xt，yt）分别表示候选路段起点F与终点T的坐标。则当xf＝xt时，θ0＝0；否则，θ0＝π／2－arctan ［（yt－yf）／（xt－xf）］。Δθ的取值如表1所示。

表1 Δθ的取值Tab.1 The value ofΔθ

续表1

3.2.3 可达性权重

可达性权重表示为

式中，RW表示可达性权重系数；将候选路段上距当前定位点最近的点（垂直投影点、起点或终点）称为该候选路段的虚拟匹配点，如果上一匹配点到该候选路段虚拟匹配点的最短距离不大于浮动车在该时间间隔内能够行驶的最大距离（取1200m），X取1，否则取－1。

最短路径的求解采用Dijkstra算法［12，14－16］，以上一匹配点和当前虚拟匹配点所在网格为对角网格，并将两对角网格构成的矩形区域作为Dijkstra算法的搜索区域。在解算过程中，各路段权值为路段长度与阻力之和［12，14］，即

正向权值为

反向权值为

如图7所示，定位点P1已经匹配到路段AB上的P点，对于当前定位点P2，点E和F分别为其候选路段AD和CD的虚拟匹配点，其中路段CD为单向道路。点P到E和F的最短路径分别为P－A－E和P－B－C－F，而路径P－B－C－F的距离大于浮动车在该时间间隔内能够行驶的最大距离，因此，候选路段AD较CD具有更高的可达性权重。

图7 可达性权重Fig.7 Reachability weight

3.2.4 权重总和

权重总和表示为

算法为每条候选路段计算权重总和W，选出具有最高和次高权重和的两候选路段，比较两权重，如果相差大于1%，则将具有最高权重和的候选路段作为匹配路段，将该候选路段的虚拟匹配点作为匹配点。

反之，如果两权重和相差在1%之内，视为模糊情况，将当前定位点匹配到两候选路段的上游节点，即上一匹配点到两候选路段虚拟匹配点的最短路径所经过的最后一个相同节点。如图8所示，点P是已经匹配到路段AB上的匹配点，对当前定位点Q，候选路段EF与DG分别具有最高和次高的权重和，点M与N分别为其虚拟匹配点。点P到M与N的最短路径分别为P－B－C－D－E－M和P－BC－D－N，由于两权重和相差在1%内，因此将定位点Q匹配到路段EF和DG的上游节点，即D点。

图8 上游节点匹配Fig.8 Upstream node matching

3.3 基于最短路径的行驶轨迹选择

由于浮动车系统上传数据的时间间隔较大，同一辆车前后两点很可能相距几个路段。因此，算法对某一定位点结束匹配之后，在充分考虑路网拓扑关系的前提下，选择当前匹配点与上一匹配点间的最短路径作为车辆的行驶轨迹，这与大多数熟悉路网的司机在一般情况下会选择最近的道路到达目的地的实际情况相符。最短路径的求解同3.2.3节所述方法，路段权值设置同式（4）和式（5）。

4 算法验证

将本文算法应用于北京市道路网络，距离、航向与可达性权重系数DW、HW与RW均设置为1／3。图9给出同一辆浮动车连续3个定位点的正确匹配结果；图10和表2分别给出了其中第2个定位点的匹配情况，在表2中，ID表示候选路段编号，R表示上一匹配点到当前定位点候选路段虚拟匹配点的距离；图11给出传统算法直接将具有最高权重的候选路段作为匹配路段时的错误匹配结果。

图9 正确地图匹配结果Fig.9 The correct map matching result

图10 第2个定位点的匹配结果Fig.10 Matching result of the second GPS point

表2 第2个定位点的候选路段Tab.2 Candidate roads of the second GPS point

由此可见，本文设计的算法能够正确计算候选路段的各项权重，有效排除不可能的候选路段；同时，候选路段11和176分别具有最高与次高的权重，且相差1%之内，176为车辆实际经过的路段，算法将定位点匹配到两路段的上游节点，而如图11所示，如果直接选择最高权重的候选路段作为匹配路段，将造成连续的匹配错误。浮动车地图匹配的最终目的是为城市路况模型提供车辆行驶轨迹，模糊情况下的上游节点匹配虽然带来较大的单点匹配误差，但却避免由于单点匹配错误而造成的连续匹配失败。

图11 错误地图匹配结果Fig.11 The wrong map matching result

此外，采用NovAtel FlexPak－G2GPS接收机接收同一辆浮动车在不同时间段内行驶于多条路线时的定位数据。利用此数据，将本文算法运行于2.53GHz CPU、2G内存的计算机上进行验证。经统计，算法的平均正确匹配率为96.55%，单点的平均匹配时间为0.931ms。

对于现有实时运转的浮动车地图匹配算法，正确匹配率平均在95%左右，单点匹配时间在几毫秒至几十毫秒之间。可见，本文算法在保证较高准确率的基础上，极大地提高匹配效率，能够满足目前北京市浮动车系统地图匹配的准确性要求及每分钟35 000点的计算速度要求。

5 结 论

针对现有浮动车地图匹配算法应用于城市复杂路网时面临的关键技术难点，对浮动车地图匹配展开研究，主要包括以下方面：

（1）给出道路网络的构建方法，充分考虑道路网络的空间分布特性，使构建的网络区别于普通平面网络。合理编辑属性表结构，有效降低了地图匹配算法的计算复杂度。

（2）基于网格的候选路段确定，根据GPS定位点所在网格，直接得到其候选路段，极大地提高了算法的运行效率。将各网格扩展为原来边长的2倍，将新网格所包含的路段作为候选路段，能够保证正确路段在候选路段之中，克服潜在的匹配错误。

（3）基于距离、航向和可达性权重的定位点匹配，距离的计算，考虑投影点与候选路段的位置关系，准确得到虚拟匹配点。根据道路属性，给出车辆航向与路段方向夹角的各种可能。可达性权重的引入使车辆处于单向道路、立体交通道路时保证地图匹配的精度。模糊情况下的节点匹配，适于城市路网结构复杂、主辅路并行和交叉口繁多的特点，避免连续匹配失败。

（4）基于最短路径的行驶轨迹选择，适于浮动车数据采样间隔大的特点，对Dijkstra算法搜索区域的合理限制，有效保证路径选择的实时性。

由于不同的权重系数会给匹配结果带来一定的影响，车辆在两匹配点间的行驶轨迹并不是在任何情况下都是两点间的最短路径，因此，为进一步提高算法的准确性，根据车辆的行驶状态和所处的路网环境合理调整权重系数，以及考虑更多的因素确定车辆在两匹配点间的行驶轨迹，是下一步的研究方向。

［1］ LIU Pei.Study on Map－matching Algorithm Based on Probe Car［D］.Beijing：Beijing Jiaotong University，2007.（刘培.基于浮动车数据的地图匹配算法研究 ［D］.北京：北京交通大学，2007.）

［2］ YIN Xiangyong，JIA Shunping.Synthesized Map Matching Algorithm for Floating Cars Processing Center［J］.Computer Engineering and Applications，2008，44（36）：881－884.（尹相勇，贾顺平.基于MapObjects的浮动车中心地图匹配综合算法开发［J］.计算机工程与应用，2008，44（36）：881－884.）

［3］ ZHU Tongyu，GUO Shengmin.A Study on Floating Car Based Information Processing Technology［J］.Journal of Image and Graphics，2009，14（7）：1230－1237.（诸彤宇，郭胜敏.浮动车信息处理技术研究 ［J］.中国图象图形学报，2009，14（7）：1230－1237.）

［4］ ZHANG Wei，XU Jianmin，LIN Mianfeng.Map Matching Algorithm of Large Scale Probe Vehicle Data［J］.Journal of Transportation Systems Engineering and Information Technology，2007，7（2）：40－45.（章威，徐建闽，林绵峰.基于大规模浮动车数据的地图匹配算法 ［J］.交通运输系统工程与信息，2007，7（2）：40－45.）

［5］ WANG Dongzhu，DONG Jiming，LI Yameng，et al.Mapmatching Method Based on Zero－speed Points in Floating Car Data［J］.Journal of Transport Information and Safety，2009，27（6）：38－42.（王东柱，董继明，李亚檬，等.浮动车数据中零速度点数据地图匹配方法 ［J］.交通信息与安全，2009，27（6）：38－42.）

［6］ XUE Ming，LV Weifeng，ZHU Tongyu.Study on Key Technology of Floating Car Information Processing System［J］.Control and Automation，2006，22（11）：244－246.（薛明，吕卫锋，诸彤宇.浮动车信息处理系统关键技术的研究［J］.微计算机信息，2006，22（11）：244－246.）

［7］ LIU Yanting，WU Jianping，ZHANG Ge.A Map Matching Algorithm for Public Traffic Control Center Based on Long Space and Limited GPS Data［J］.Journal of Transportation Engineering and Information，2007，5（2）：69－74.（刘彦廷，吴建平，张鸽.基于长间隔大规模数据的地图匹配算法研究［J］.交通运输工程与信息学报，2007，5（2）：69－74.）

［8］ ZHU Liyun，WEN Huimin，SUN Jianping.Floating Car Based Real－time－traffic－info Collection System in Beijing［J］.Urban Transport of China，2008，6（1）：77－80.（朱丽云，温慧敏，孙建平.北京市浮动车交通状况信息实时计算系统［J］.城市交通，2008，6（1）：77－80.）

［9］ ZHU Liyun，GUO Jifu，WEN Huimin，et al.A Mapmatching Algorithm of Real－time Floating Car System for Complex City Road Network［J］.Computer and Communications，2007，25（6）：81－84.（朱丽云，郭继孚，温慧敏，等.一种适用于复杂城市路网的浮动车实时地图匹配技术［J］.交通与计算机，2007，25（6）：81－84.）

［10］ SU Jie，ZHOU Dongfang，YUE Chunsheng.Real－time Map－matching Algorithm in GPS Navigation System for Vehicles［J］.Acta Geodaetica et Cartographica Sinica，2001，30（3）：252－256.（苏洁，周东方，岳春生.GPS车辆导航中的实时地图匹配算法［J］.测绘学报，2001，30（3）：252－256.）

［11］ TANG Jinjun，CAO Kai.An Adaptive Trajectory Curves Map－matching Algorithm［J］.Acta Geodaetica et Cartographica Sinica，2008，37（3）：308－315.（唐进君，曹凯.一种自适应轨迹曲线地图匹配算法 ［J］.测绘学报，2008，37（3）：308－315.）

［12］ CHENG Lin，WANG Meiling，ZHANG Yi.An Improved Algorithm Based on SuperMap GIS［J］.Journal of Geoinformation Science，2010，12（5）：649－654.（程林，王美玲，张毅.一种基于SuperMap GIS的改进Dijkstra算法［J］.地球信息科学学报，2010，12（5）：649－654.）

［13］ VELAGA N R，QUDDUS M A，BRISTOW A L.Developing an Enhanced Weight－based Topological Map－matching Algorithm for Intelligent Transport Systems［J］.Transportation Research Part C—Emerging Technologies，2009，7：672－683.

［14］ CHENG Lin，WANG Meiling.A New Path Planning Algorithm Based on Partitioned Urban Transportation Network［C］∥Proceedings of 2010International Conference on Computer Application and System Modeling（ICCASM 2010）.Taiyuan：IEEE，2010：13－17.

［15］ HAN Gang，JIANG Jie，CHEN Jun，et al.An Arc Based Dijkstra Algorithm for Road Turning Penalty in Vehicle Navigation System［J］.Acta Geodaetica et Cartographica Sinica，2002，31（4）：366－368.（韩刚，蒋捷，陈军，等.车载导航系统中顾及道路转向限制的弧段Dijkstra算法［J］.测绘学报，2002，31（4）：366－368.）

［16］ LU Feng.Shortest Path Algorithms：Taxonomy and Advance in Research［J］.Acta Geodaetica et Cartographica Sinica，2001，30（3）：269－275.（陆锋.最短路径算法：分类体系与研究进展［J］.测绘学报，2001，30（3）：269－275.）