一种改进的快速浮动车地图匹配方法

张健钦，李明轩，段颖超，杜明义

(1. 北京建筑大学测绘与城市空间信息学院，北京 100044； 2. 现代城市测绘国家测绘地理 信息局重点实验室，北京 100044)

一种改进的快速浮动车地图匹配方法

张健钦1,2，李明轩1,2，段颖超1,2，杜明义1,2

(1. 北京建筑大学测绘与城市空间信息学院，北京 100044； 2. 现代城市测绘国家测绘地理 信息局重点实验室，北京 100044)

浮动车地图匹配算法能够实现浮动车离散点与路段的快速准确匹配,是浮动车路况信息生成技术中的核心环节。本文针对现有方法的不足，实现了建立定位点的有效阈值缓冲区，并依据空间关系检索候选匹配路段，研究实现了一种利用行驶速度、行驶方向、投影距离、行驶距离4个参数进行行车轨迹判别的逻辑匹配算法。试验表明，该方法无需对路网数据进行大量的前期处理工作,简化了候选匹配路段的检索过程，在保证匹配正确率的同时也表现出了更高的效率。

路网匹配；浮动车数据；路况信息；路段

路况信息是反映城市道路交通通行状况的综合信息，其主要表现为城市交通道路的拥堵或畅通情况。随着高新信息技术在交通中的广泛应用，交通信息采集、处理和发布技术日趋成熟和多样化，而浮动车系统是近些年发展起来的交通路况信息采集技术。一般使用具备一定样本量的出租车或公交车作为浮动车，通过已安装的GPS车载装置和无线通信设备，将车辆信息(如时间、速度、坐标、方向等参数)实时地传送到浮动车信息中心，经过与路网数据匹配处理后形成实时动态路况信息，为交通管理部门提供调度依据,为公众提供出行参考,还可作为道路建设规划、拥堵缓解等各项工作中定量数据分析的基础[1]。

浮动车数据反映在地图上是一个个具有空间坐标的离散点要素，但受到定位系统、数据传输、地图矢量化，以及不同空间坐标参考系的选取和转换过程中多种因素的共同作用，使其绝大多数游离于路网线要素之外，无法与道路直接匹配形成路况信息。因此，将浮动车定位点真实地归属到城市路网中的某路段，并确定其在路网线上匹配点的处理过程，是路网匹配算法及路况信息生成的核心。传统的导航地图匹配算法不适用于浮动车数据，原因包括:①浮动车数据量较大，且对系统的实时处理计算速度要求较高；②数据采样间隔较大，导致定位点之间的空间相关性较差；③城市路网密集且结构复杂，对数据的匹配容错率要求较高。因此，近年来国内外学者对此展开了大量研究，并主要引入逻辑条件和数学模型参与算法判别，成果显著，对于大规模浮动车数据的匹配效率也有较大提升[2-12]。但仍存在优化和改进空间，一方面算法匹配精确度高但前期需对路网数据进行大量处理工作；另一方面许多算法将GPS定位点视为独立对象进行匹配，较少考虑路况信息更新周期内同名定位点的逻辑关系，往往导致效率提高而准确率降低。针对这两方面的不足，本文提出并实现阈值缓冲区确定候选匹配路段，利用4个参数进行行车轨迹判别的逻辑匹配算法，在考虑匹配正确率的同时也表现出较高的效率，而且无需对路网数据进行大量前期处理工作，拥有更好的算法实用性。

1 候选匹配路段

候选匹配路段是指位于浮动车定位点周围的可能与之匹配的路段集合。从全路网线要素中快速检索出每个定位点的候选匹配路段是一个高效路网匹配算法的前提。文献[2]的算法在总结了以往算法的基础上开展了以下研究：基于网格的候选路段确定，基于距离、航向、可达性权重的定位点匹配，以及基于最短路径的行驶轨迹选择的算法研究，算法能够满足浮动车地图匹配准确性与实时性的要求。虽然基于网格划分法的定位点周边路段查找具有索引方法灵活、提取目标要素快速等特点，但在实际应用中也存在着一些不足。

1.1 基于网格法的不足

1.1.1 大量零碎路段

由于地图格网的网格大小相同，而城市路网疏密程度不同，因而不易控制由格网断开后的路段长度，在实现过程中往往会出现大量被截断且长度较小的零碎路段，给匹配处理额外增加了一定程度的性能负担。如对北京市区全路网进行200 m×200 m的网格划分，路段总长小于10 m的占到了一定比例，其中部分路段信息及其局部放大图如图1所示。

图1 过多的零碎路段

1.1.2 格网确定过程较为复杂

基于网格划分的检索方法通常是利用GPS定位点距离网格4条边的距离，并对比GPS定位点精度的阈值范围来判断是否获取当前网格或周边邻域网格中的路段。但由于邻域网格数量随定位点位置有3、5、8个，随方向有上、下、左、右、左上、左下、右上、右下多种情况(如图2(a)所示，黑色为定位点网格，阴影为邻域网格)，因而一方面查找过程较为复杂，另一方面容易将本身不符合条件的路段也作为候选对象(如图2(b)所示路段1、2、3、4)，需要进一步判断才能排除。

图2 网格查找法的几点问题

1.2 阈值缓冲区法

针对上述不足，本文提出阈值缓冲区法检索候选匹配路段，利用功能性节点层划分路网形成路段单元，在定义索引编码的前提下，对每个浮动车定位点动态生成其最大阈值缓冲区，进而利用空间面线关系来判别和获取候选匹配路段集合。该方法能一次性确定各个点的候选匹配路段，即只要是该集合中的元素，都是需要进行后续判别的候选路段对象。具体如图3所示，P1、P2、P3、P4分别是定位点生成的缓冲区，其半径设定为浮动车数据的最大有效阈值(允许半径不同)；seg1、seg2、…、seg11分别为各功能性节点形成的路段单元。综合考虑二者的空间面线关系，得到关于P1的相交路段seg2、P2的相切路段seg5、P3的相交路段seg7和seg9。其中，P1、P2、P3与路段相切或相交，对应定位点与路段距离小于或等于最大有效阈值，属于有效漂移点；P4与路段seg3和seg11相离，属于漂移严重的无效点。seg2是对应P1、seg5是对应P2、seg7和seg9是对应P3定位点的候选匹配路段。

图3 阈值缓冲区法查找候选匹配路段

2 行车轨迹判别

对于浮动车数据，其在城市路网中的整体表现是一个时间段上的点集。在理想情况下不同车辆在一段时间内拥有相同的点数，但实际上每辆车的一个时间序列很可能会因漂移严重或建筑物遮挡造成部分定位点丢失。因此，可以综合考虑各车辆自身属性及同名车辆在时间序列中的逻辑规则，进行行车轨迹的推测和判别，并最终确定匹配路段和匹配点。具体判别过程主要包含以下4个参数：

2.1 行驶速度

图4 行驶速度参数判别分析

2.2 行驶方向

行驶方向判别方法是根据GPS记录中车辆行驶方向与路段方向的相似度进行判别的方法。一方面浮动车数据中记录有车辆某时刻的方位角，另一方面候选匹配路段由于已经过了各类功能性节点的打断处理，各路段单元近似为一条直线，因而该路段方向完全可以由其矢量起终点的连线方向表示。研究发现，虽然行驶方向是一个瞬时概念，在实际行车过程中会随着当时的驾驶情况(直行、左转、右转等)发生较大的偏差，其取值不总是与道路或路段方向保持一致。但是，在正常行驶状态(即不发生逆行、倒车等突发状况)的前提下，车辆行驶方向与所属路段方向的夹角总能保持在一定的变化区间内，即夹角差的绝对值不超过90°。图5分别是在直线道路和曲线道路条件下根据行驶方向来取舍候选匹配路段的处理方法。如图5(a)所示，已知nodei和nodej是某道路的两个相邻节点，浮动车P行驶在它们生成的路段segi,j内，其正常行驶状态下的众多方向dir1、dir2、dir3始终与道路方向Dirroad保持着一定范围内的一致性；如图5(b)所示，浮动车定位点P位于曲线道路road的路段segi,j中，匹配点P′的方向记为dirp′，根据几何关系容易得出dirp′即是过匹配点P′并与路段segi,j相切的切线方向，而此时由于road方向不能代表某个区间的走向，因此通过连接匹配点所在路段始末节点nodei和nodej形成的有向线段，并以它的方向作为道路方向参与方向夹角判断。

2.3 投影距离

图5 行驶方向参数判别分析

图6 投影距离参数判别分析

2.4 行车距离

2.5 匹配流程

基于上述方法设计完整的路径匹配算法，其主要步骤和具体流程如图8所示。

2.6 路况生成

路段上车辆的平均速度是表征路况的主要信息，因此在进行浮动车数据的路网匹配之后，还需要按顺序计算各路段上同名车辆匹配点的平均速度，以及整条路段上所有车辆的平均速度，从而最终完成由“车的信息”向“路况信息”的转换过程。此外，还可以根据路段与各道路路链、兴趣线路或区间的从属关系，对相应道路平均行车速度值进行符号化和地图渲染，生成能够直观表达出道路拥堵状态的路况专题图，以及计算区域的交通拥堵指数等。

图7 行驶距离参数判别分析

3 实例研究

目前参与北京市浮动车系统的车辆约35 000辆，每辆车如果每分钟上传一个GPS数据，那么数据处理中心每天接收到的数据量就有5000余万条，为了研究算法的实用性，选取北京市市区道路网和2008年某日1000辆出租车GPS数据(采集频率30 s一次)作为试验对象，将本文算法运行于2.53 GHz、2 GB内存的计算机上进行验证，结果见表1，分别是以5 min为路况更新周期下的连续1个、2个和5个周期的10次匹配结果均值。

表1 不同数量下匹配算法耗时结果

结果表明，算法的平均正确匹配率为97.4%，单点的平均匹配时间为0.882 ms。相对于现有实时运转的浮动车地图匹配算法，正确匹配率平均在95%左右，单点匹配时间在几毫秒至几十毫秒之间。本文算法在保证较高准确率的基础上，极大地提高了匹配效率，能够满足目前北京市浮动车系统地图匹配的准确性要求及每分钟35 000点的计算速度要求，同时对比文献[2]的方法，本文的方法解决了网格法的不足，同时匹配正确率和匹配效率也有提高。

图8 路网匹配算法流程

4 结束语

本文提出并实现了一种基于阈值缓冲区确定候选匹配路段，并利用行驶速度、行驶方向、投影距离和行车距离4个参数进行行车轨迹逻辑判别的匹配算法。试验表明，该方法能够高效且准确地筛选和判断出浮动车定位点的匹配路段，对浮动车路况信息的生成具有很好的实用价值。本文研究的路况信息匹配生成算法所考虑的因素较多，对于一些非常复杂的路段区域，随着待定方案的增多会导致部分性能的降低。后续研究工作将针对这些特殊区域路段的特点，对算法性能的稳定性进行改进和优化。

[1] 邵春福,熊志华,姚智胜.道路网短时交通需求预测理论、方法及应用[M].北京:清华大学出版社,2011.

[2] 王美玲，程林.浮动车地图匹配算法研究[J].测绘学报,2012,1(41),133-138.

[3] 刘培.基于浮动车数据的地图匹配算法研究[D].北京:北京交通大学,2007.

[4] 尹相勇,贾顺平. 基于MapObjects的浮动车中心地图匹配综合算法开发[J]. 计算机工程与应用, 2008, 44(36): 881-884.

[5] 诸彤宇,郭胜敏. 浮动车信息处理技术研究[J]. 中国图象图形学报, 2009, 14(7):1230-1237.

[6] 章威, 徐建闽, 林绵峰. 基于大规模浮动车数据的地图匹配算法[J]. 交通运输系统工程与信息, 2007, 7(2):40-45.

[7] QUDDUS M A,NOLAND R B,OCHIENG W Y.A High Accuracy Fuzzy Logic Based Map Matching Algorithm for Road Transport[J]. Journal of Intelligent Transportation Systems, 2006, 10(3): 103-115.

[8] NAJJAR M E E,BONNIFAIT P.A Road-matching Method for Precise Vehicle Localization Using Belief Theory and Kalman Filtering[J]. Autonomous Robots, 2005,19(2):173-191.

[9] JABBOUR M, BONNIFAIT P, CHERFAOUI V. Map-matching Integrity Using Multihy Pothesis Road-tracking[J]. Journal of Intelligent Transportation Systems, 2008, 12(4): 189-201.

[10] 吕卫锋,吴东东,诸彤宇. 基于向量识别的启发式路径推测算法[J]. 计算机学报,2009,32(7):1443-1450.

[11] 李宇光,李清泉. 利用地图栅格化的海量浮动车数据道路匹配快速算法[J]. 武汉大学学报(信息科学版),2014,39(6):724-728，733.

[12] RAHMANI M,KOUTSOPOULOS H N.Path Inference from Sparse Floating Car Data for Urban Networks[J]. Transportation Research Part C:Emerging Technologies, 2013(30):41-54.

[14] CHERITON D R, BECHTOLSHEIM A V. Method for Traffic Management,Traffic Prioritization,Access Control,and Packet Forwarding in a Datagram Computer Network: U.S. Patent 6,091,725[P]. 2000-07-18.

[15] MCCLOGHRIE K,GAI S,MOHABAN S. Method and Apparatus for Identifying Network Data Traffic Flows and for Applying Quality of Service Treatments to the Flows: U.S. Patent 6,286,052[P]. 2001-09-04.

[16] DE FABRITIIS C,RAGONA R, VALENTI G. Traffic Estimation and Prediction Based on Real Time Floating Car Data[C]∥Proceedings of the 11th International IEEE Conference on Intelligent Transportation Systems. Beijing：IEEE, 2008: 197-203.

[17] LEDUC G. Road Traffic Data: Collection Methods and Applications[J]. Working Papers on Energy, Transport and Climate Change,2008(1): 55.

[18] FUSHIKI T, YAMANE K, INOUE T, et al. Method of Presuming Traffic Conditions by Using Floating Car Data and System for Presuming and Presenting Traffic Conditions by Using Floating Data: U.S. Patent 6,721,650[P]. 2004-04-13.

[19] EHMKE J F, MEISEL S, MATTFELD D C. Floating Car Data Based Analysis of Urban Travel Times for the Provision of Traffic Quality[M].New York：Springer, 2010: 129-149.

[21] YOSHIDA M. Traffic Information System: U.S. Patent 5,699,056[P]. 1997-12-16.

AnImprovedAlgorithmforFastMap-matchingofFloatingCar

ZHANG Jianqin1,2,LI Mingxuan1,2, DUAN Yingchao1,2,DU Mingyi1,2

(1. School of Surveying and Urban Spatial Information, Beijing University of Civil Engineering and Architecture,Beijing 100044,China; 2. Key Laboratory for Urban Geomatics of National Administration of Surveying, Mapping and Geoinformation，Beijing 100044, China)

Floating car map-matching algorithm enables fast and accurate matching between the discrete points of floating car and the road segments. It is the core part of floating car traffic information generation technology. For the deficiencies of the prior method, an efficient logical matching method is proposed and implemented. Firstly it establishes buffer zones with effective threshold for the anchor points, and then searches the road segments that intersect with the buffer zones. After that, it discriminates the driving track by four parameters(driving speed, driving direction, projection distance and driving distance). The experiments show that this method does not require extensive work to deal with road network data. It simplifies the process of searching candidate matching road segments and ensures matching accuracy while also shows a higher efficiency.

road network matching; floating car data; traffic information; road segments

P283

A

0494-0911(2017)01-0087-06

张健钦，李明轩，段颖超,等.一种改进的快速浮动车地图匹配方法[J].测绘通报，2017(1)：87-92.

10.13474/j.cnki.11-2246.2017.0019.

2016-02-27

张健钦(1977—)，男，博士，副教授，研究方向为交通GIS、三维GIS及智能交通系统。E-mail：yc.duan@qq.com