基于浮动车数据的隧道路段在线地图匹配方法

何兆成，褚俊飞，庄立坚，叶伟佳

（中山大学 工学院 智能交通研究中心，广州 510006）

1 引言

随着经济的发展，汽车保有量的增加，城市交通拥堵现象越来越严重.为了实现城市交通分流、缓解城市交通拥堵，修建城市隧道越来越成为解决这一问题的重要举措，隧道路段车辆信息的采集对于整个城市交通信息的发布具有重要意义.

近年来，浮动车技术作为获取道路交通信息的先进技术手段在智能交通领域得到了快速发展，国内外存在大量相关的研究，章威等[1]提出了浮动车地图匹配模型族的解决方案，包括道路初次匹配模型、平行方向道路识别模型、节点匹配模型和延时匹配模型；Wang Wei等[2]提出了一种曲线匹配和基于概率分析模型的算法框架，引入基于模糊逻辑和最短路径算法的路径确定算法；Marchal等[3]提出了一种基于大规模历史GPS数据后期处理的地图匹配方法，但该方法不能满足交通信息实时发布的需求；Yin Lou等[4]提出了一种面向低采样率GPS数据的全局地图匹配算法，算法采用了时空分析方法生成一个候选图，并将拥有最高匹配得分的路段序列作为最终匹配结果；Liao Wen-jie等[5]提出了一种基于交叉口数据结构的地图匹配算法，用于解决城市交叉口处的匹配问题.

已有的大量针对地图匹配的研究主要是面向城市普通道路的，基于城市隧道路段的特殊性，已有研究并没有考虑车辆在隧道路段及辅道上行驶时交通状态的差异性，无法适用于隧道路段地图匹配.本文针对城市隧道路段的特点及浮动车数据采样率低的现状，引入道路时空可达性和隧道路段车辆行为模式两种信息，并运用模糊逻辑对权重进行分配，提出了针对隧道路段的在线地图匹配方法.方法能够根据实时GPS信息来识别车辆的行驶路径，鉴别车辆是否行驶在隧道路段.以广州市为例，采用实地调查数据对方法的精度进行了验证.

2 问题描述

2.1 隧道路段的概念

如图1所示，隧道路段是指车辆从隧道与辅道的分流点处进入，到两者的合流点处离开所经过的路段区域.本研究中的隧道路段包含了与隧道进出口具有连通关系的相关路段，所提出的方法主要适用于与隧道进出口有连通路段的城市隧道或者隧道实体部分有露空足以留下GPS点的城市隧道，对于一些与隧道进出口没有连通路段且隧道实体部分无露空的隧道，不是本文讨论的内容.

图1 隧道路段示意图Fig.1 Tunnel section

研究以广州市2万多辆安装了GPS定位设备的出租车作为浮动车的数据源，每天回传的数据超过3千万条，覆盖了广州市80%以上的主干路网.出租车在通过隧道路段时，在连通路段和露空的隧道实体部分可能留下GPS点信息，并在运营过程中记录下车辆行驶的状态信息（车牌号、GPS时间、经纬度、航向、速度、车辆状态和数据有效性等），同时以一定周期向数据中心传回数据，采样间隔在10s-80s之间，其中以15s采样间隔的数据量最多.浮动车数据主要信息如表1所示.

表1 浮动车数据主要信息Table 1 Main information of FCD

2.2 问题关键

实际情况下，隧道路段和相应辅道是平行的，且距离很短，在二维电子地图中，隧道路段和相应辅道是基本重叠的.如图2所示，车辆经过黄埔大道西，回传若干个GPS点，在隧道路段与辅道重叠的区域，传统的匹配算法无法鉴别车辆是否行驶在隧道路段.

图2 GPS点分布Fig.2 The distribution of GPS

3 匹配原理

本文基本思想是确保隧道路段待匹配点序列的起点和终点均为置信点(CP)[6]，同时结合最大延时约束动态时间窗(MDCDTW)[6]的概念.利用置信点和最大延时约束动态时间窗不仅能够有效消除传播误差和提高匹配精度，还可以满足匹配实时性需求.其中MDCDTW包含三部分：①等待匹配的点序列WP；②WP相应的候选路段集WL；③自定义的最大延时约束tMDC.

当车辆行驶在简单路网时，利用简单的匹配算法[7,8]就能获得良好的匹配效果，而当车辆行驶在高复杂度的路网时，如隧道、跨线桥、高架路等，只考虑单一定位点信息难以实现正确匹配.本研究基于路段的思想，提出一种针对隧道路段适用于长时间间隔浮动车数据的点序列匹配方法，该方法综合车辆的行驶轨迹信息（由GPS点序列构成）、几何和拓扑信息，通过找到匹配权重总和最大的路径作为最终的匹配路段.方法分为两个部分：①道路时空可达性；②隧道路段车辆行为模式.

3.1 道路时空可达性

本文中的道路时空可达性包含拓扑连接可达性和行驶时间合理性.行驶在路网上的车辆可以从路段1到达路段2的基本要求是路段1和路段2之间在拓扑上是连通的，对于两个连续定位点的正确匹配路段必须具备拓扑连接可达性；行驶时间合理性是指驾驶员选择相对较短的路径、花费较少的时间从路段1到达路段2.以下给出两种满足拓扑连接可达性的情况：

（1）前后两个连续候选路段为同一个路段.

（2）前后两个连续候选路段是不同路段并且第一个路段的终点和第二个路段的起点在拓扑上是连通的.

在WL中，一个路段是最优路径的组成部分的必要条件是：该路段与下一个相邻的候选路段集中的某一路段满足道路时空可达性要求.因此，对任意一对在相邻候选路段集中的路段要进行道路时空可达性检测.当且仅当两个被检测路段可以完全满足道路时空可达性要求时，才为它们之间的连接线赋予可达性标识，拥有该标识才可以进行下一步的连接权重赋值.如图3所示，为一个完成了道路时空可达性检测的时间序列有向图.

图3 一个完成了道路时空可达性检测的时间序列有向图Fig.3 A time series directed graph completed accessibility detections

3.2 隧道路段车辆行为模式

通过实地调查发现，在实际的驾驶行为中，如果车辆沿道路直行的话，一般选择隧道路段行驶.本研究选择了广州市的黄埔大道西—马场路隧道和黄埔大道西—体育东路隧道，分别统计了直行出租车车辆数及直行出租车中选择走隧道的车辆数，统计结果如表2所示.

表2 直行出租车选择隧道路段的比例Table 2 The percentage of straight taxies choose tunnel section

由表2可知，超过88%的直行出租车会选择隧道路段行驶，因此，提高直行出租车匹配到隧道路段的权重是可行的.

建设城市隧道的目的是使得主要方向的交通流不受信号交叉口的影响快速通行.通过比较发现隧道路段与其辅道存在着显著的差异，辅道存在信号交叉口影响，使得车辆在隧道路段和辅道行驶分别具有不同的行为模式.以下给出在平稳交通流状态下车辆在隧道路段及辅道上行驶时其行为模式的差异性：

（1）由于受红绿灯、交叉口的干扰影响，车辆在辅道上行驶时经常会出现走走停停的现象，其行驶速度一般低于隧道路段的车速.

（2）直行出租车一般选择隧道路段行驶.

（3）由于隧道路段不允许出租车上下客，因此出租车在隧道路段不会发生重车—空车相互转换的情况.

在判断隧道路段车辆行为模式时，需要考虑多种定性因素，模糊逻辑可以有效解决有关定性条件的问题，在地图匹配的研究中，模糊逻辑得到了广泛的应用[9,10].根据以上对车辆行为模式差异性的总结，本文选取当前GPS点的瞬时速度(IS)、隧道路段车辆的平均速度(AS)、当前GPS点车辆是否直行(GS)、当前GPS点与前或后一个GPS点车辆状态是否发生空车—重车状态转换(ST)4个因素作为隧道路段车辆行为模式的输入变量，输出变量是当前GPS点匹配到隧道路段的可能性P.模糊集合为：IS模糊化为零速(Z)、低速(L)、高速(H)；AS模糊化为低速(L)、高速(H)；GS模糊化为True和False；ST模糊化为True和False，其隶属度函数如图4所示.对于输出变量P，其模糊集合为Positive=1和Negative=-1.

图4 输入变量的隶属度函数Fig.4 Membership functions of input variables

在对模糊逻辑进行去模糊化的过程中，本文采用Max-Min方法.结合广州道路交通情况及车辆在隧道路段及辅道上行驶其行为模式的差异性，本文给出10条模糊规则，如表3所示.

表3 模糊规则表Table 3 Fuzzy rules

3.3 连接权重赋值

为了找到最优匹配路径，必须对时间序列有向图中的所有拥有可达性标识的连接线进行连接权重赋值，式（1）给出了连接权重的计算方法.

式中 WGt,Gt+1(Lm,Ln)表示定位点Gt的候选路段Lm到定位点Gt+1的候选路段Ln的连接权重，WG(L)表示定位点G的候选路段L的匹配权重，由式（2）得到.

式中 Wi表示简单地考虑了距离权重和航向权重的点到线匹配权重，可以由参考文献[6]得到，Wj表示隧道路段车辆行为模式权重.

基于时间序列有向图，把每一个候选路段看成一个阶段，构造多阶段决策的求解模型，利用动态规划可以获得最优匹配路径.

3.4 隧道路段地图匹配框架流程图

隧道路段地图匹配流程如图5所示.

图5 匹配框架流程图Fig.5 Flow chart of matching framework

4 实例分析

本文选择广州市的4条隧道对方法进行验证，4条隧道的信息如表4所示.设定最大延时约束tMDC=5 min.作为对比实验，本文在不考虑道路时空可达性和隧道路段车辆行为模式两种信息的情况下，仅仅考虑基于传统因素（如距离、航向等信息）地图匹配算法的情况下，利用采集到的相同数据源也进行了验证（对比算法），验证结果如图6、图7所示.

表4 隧道信息Table 4 Tunnel information

图6 匹配正确车牌数Fig.6 The number of correct matching license plate

图7 匹配精度Fig.7 Matching accuracy

由图7可知，针对隧道路段，在加入道路时空可达性和隧道行为模式两种信息时，匹配精度明显优于未加入时的算法，可以有效鉴别车辆是否行驶在隧道路段.在上述实验中，本文只研究了在平稳交通流状态下，考虑道路时空可达性和隧道路段车辆行为模式对区分隧道路段及其辅道的有效性.然而，当隧道路段发生交通拥堵时，其交通状态与正常情况相比将出现极大的差异，车辆行为也将发生明显变化，直接影响是车速严重降低而出现类似辅道车辆走走停停的情况，这可能导致隧道路段车辆行为模式失去作用，最终导致匹配错误，下一步将针对此方面进行深入研究.

5 研究结论

本研究提出了一种面向浮动车数据的隧道路段在线地图匹配方法，方法主要适用于与隧道进出口有连通路段的城市隧道或者隧道实体部分有露空足以留下GPS点的城市隧道.研究引入道路时空可达性和隧道路段车辆行为模式信息，总结了车辆在隧道路段及辅道上行驶时其行为模式的差异性，并运用模糊逻辑对权重进行分配.方法能够满足匹配实时性和准确性要求，能够根据实时GPS信息来识别车辆的行驶路径，鉴别车辆是否行驶在隧道路段.最后，选取广州市的4条隧道路段对方法进行效用评价.结果表明，该方法的匹配精度超过90%，可以用于城市隧道路段的交通信息处理.

[1] 章威,徐建闽,林绵峰.基于大规模浮动车数据的地图匹配算法[J].交通运输系统工程与信息，2007，2(1):39-45.[ZHANG W,XU J M,LIN M F.Map matching algorithm of large scale probe vehicle data[J].Journal of Transportation Systems Engineering and Information Technology,2007,2(1):39-45.]

[2]Wang W,Jin J,Ran B,et al.Large-scale freeway net⁃work traffic monitoring:A map-matching algorithm based on low-logging frequency GPS probe data[J].Jour⁃nal of Intelligent Transportation Systems,15(2):63-74.

[3]Marchal F,Hackney J,Axhausen K.Efficient map matching of large Global Position System data sets:Tests on speed-monitoring experiment in Zürich[J].Transportation Research Record:Journal of the Trans⁃portation Research Board,2005,1935(-1):93-100.

[4]Lou Y,Zhang C,Zheng Y,et al.Map-matching for lowsampling-rate GPS trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,2009,352-360.

[5]Liao W,Lv W,Zhu T,et al.A map matching algorithm for intersections based on Floating Car Data[C]//10th In⁃ternational Conference on Advanced Communication Technology,2008,311-316.

[6]He Z C,She X W,Zhuang L J,et al.On-line mapmatching framework for floating car data with low sam⁃pling rate in urban road networks[J].Institution of Engi⁃neering and Technology,2013.MLA.

[7]赵凯,杨育红,曲保章.基于位置点匹配的GPS/DR组合导航系统地图匹配算法[J].制导与引信,2003,24(3):22-27.[ZHAO K,YANG Y H,QU B Z.A pointbased map matching algorithm for GPS/DR integrated navigation systems[J].Guidance&Fuze,2003,24(3):22-27.]

[8]陈佳瑜,肖桂荣.基于权重的地图匹配算法[J].计算机工程与应用,2005,41(11):168-170.[CHEN J Y,XIAO G R.A weight-based map matching algorithm[J].Com⁃puter Engineering and Applications,2005,41(11):168-170.]

[9]Qudus M A,Noland R B,Ochieng W Y.A high accuracy fuzzy logic based map matching algorithm for road trans⁃port[J].Journal of Intelligent Transportation Systems,2006,10(3):103-115.

[10] 丁露,陈家斌,张丽华.拓扑结构/模糊逻辑的车载导航系统地图匹配算法[J].火力与指挥控制,2008,33(6):52-54.[DING L,CHEN J B,ZHANG L H.Mapmatching algorithm based on topological structure/fuzzy logic for the vehicle navigation system[J].Fire Control and Command Control,2008,33(6):52-54.]