基于电子收费数据的车辆轨迹匹配

2022-06-14康爱忠李玉韩文渊傅馨峤赵建东

科学技术与工程 2022年13期

康爱忠，李玉，韩文渊，傅馨峤，赵建东*

(1.中电建冀交高速公路投资发展有限公司，石家庄 050000； 2.北京交通大学交通运输学院，北京 100044)

随着高速公路撤销省界收费站，采取电子收费(electronic toll collection，ETC)收费趋势的发展，高速公路布设了大量的ETC门架系统，并将门架采集的数据为高速公路运营管理提供支撑[1]。门架可能存在读写数据有缺失或者错误的现象，导致车辆行驶经过的ETC门架信息的数据不完全，出现车辆路径的缺失。此时，需对有部分缺失的信息进行路径提取和拟合，实现车辆完整路径的获取，从而对车辆全程进行计算收费。

多义性路径识别即通过特定的识别系统将车辆的行驶路径匹配到实际地图上，并按照识别后的路径作为收取费用的依据。基于无线射频识别(radio frequency identification，RFID)技术的多义性路径识别系统，通过安装路边识别设备，更换多义性路径识别卡，能够准确识别路网中每辆车辆在自由流状态下的实际行驶路径。施俊靓[2]从多义性路径识别系统的构成切入，分析云计算虚拟化技术的应用，提出了利用云计算虚拟化的技术解决系统建设中现存的多路径识别漏洞问题，为路径识别系统的完善过程提供基础。目前，中国主要应用的多义性路径识别解决方案是基于5.8 G的多义性路径识别技术和基于433 MHz的多义性路径识别技术设计的。吴海东等[3]主要从辐射覆盖范围，无差别标识技术等方面对5.8 G路径标识基站的关键性技术进行了详细的分析。许永存等[4]分析了5.8 G射频识别技术原理及其应用特点，以及路径识别系统的主要设备和标识思路，提出了5.8 G统一多路径识别系统的应用方案。在设计算法求得车辆完整路径方面，Amith等[5]提出了一种新的户外环境导航算法，允许机器人沿着规划的路径从一个静态节点移动到另一个节点。在具有多个路径的混合道路网络中进行路径规划，利用机器人在配置好的地图上完成导航，证明了驾驶员辅助系统的有效性。易小泉[6]运用Floyd算法结合真实的路网进行抽象处理，通过绘制有向图并构建二维矩阵，从而规划出租车通行的最优路径，并综合了路网拥堵程度、乘客紧急程度、出租车需求量、天气环境等多方面因素，实现合理规划。

通过相关文献及其研究成果可以看出，目前针对路径还原的所需信息和可用信息以及高速公路收费系统和监控系统的信息采集和应用，还没有规范和标准；现有的许多路径识别系统、收费系统和监控系统都没有经过长时间的验证并大规模应用，在路径拟合的速度和准确性等方面还存在问题。

综上，完善和提升多义性路径识别系统的精确度对高速公路的运行收费管理的重要性日益突出。现对河北省高速公路从南宫收费站至新元收费站的车辆行驶ETC门架数据进行分析和预处理，使用Floyd 算法得到车辆行驶的完整路径，完成多场景下车辆轨迹的地图匹配，以实现车辆完整路径的计费。

1 路径匹配系统需求分析

1.1 河北省ETC联网收费系统

河北省取消省级高速公路收费站也是对原有收费制度的改革。取消原有省界公路主要的收费设施，在省界附近设立虚拟收费站。同时，在高速公路沿线路段设置了ETC门架系统。高速公路收费系统主要由架构系统、业务类系统、数据处理系统等组成。其中架构系统主要有清算费用中心系统、ETC门架系统、ETC车道、MTC车道、ETC/MTC车道组成的收费系统等；业务类系统主要有信息上传系统、监测控制系统、客服服务系统、安全控制系统等；数据处理系统主要有车辆交易数据处理系统、车辆核查数据系统、车辆牌照数据识别系统等[7]。

1.2 ETC门架系统

设置ETC门架系统的原则如下。

(1)在高速公路主线位置上、高速公路出入口互通处设ETC门架。

(2)ETC门架应设置在视野范围好的区域，防止被遮挡。高速公路到门架的直线距离应大于50 m。

(3)ETC门架设备容易被相同频率设备的电磁波干扰，因此不应将5.8 GHz的设备设置在ETC门架附近，避免对门架产生干扰。

(4)相邻门架之间距离不应小于30 m，且距离不能太远。

(5)ETC门架的高不应小于6 m。安装有车牌识别系统的门架应在顶部安装[8]。

ETC门架系统主要由以下设备组成：车道控制器、RSU、车牌图像识别设备、高清摄像机、通信设备、供电设备、交换机、网络安全设备、站级服务器、防雷接地设施、补光灯等。ETC门架系统由上、下行双方向部分组成[9]。

1.2.1 省界ETC 门架系统

设置在省界上的ETC门架系统有上下两个方向。每个门架都配有冗余设置的关键设备。当主设备发生故障时，应立即启动备用设备。省界ETC 门架系统如图1所示[10]。

1.2.2 路段ETC门架系统

设置在非省界上的ETC门架系统有上下两个方向。每个门架都配有冗余设置的关键设备。当主设备发生故障时，应立即启动备用设备。路段ETC门架系统如图2所示[10]。

图2 路段ETC门架布局Fig.2 Layout of the ETC door frame at road section

2 收费系统数据处理

2.1 收费数据特征

高速公路收费系统数据特点主要集中在数据量大、格式复杂和数据冗余较大3个方面。基于河北省高速公路从南宫收费站至新元收费站的车辆行驶ETC门架数据，在分析数据特征后，提取与本研究相关的字段信息，包括车型、交易时间、途径门架名称、门架编号、车牌号。

2.2 数据预处理

数据处理的过程主要包括数据清洗和聚集。重复扣费、超时等情况需要进行数据的清洗；根据ETC系统对车牌识别采集到的信息进行聚集。进行数据的预处理，首先需要处理异常数据[11]。在对河北高速公路收费数据进行分析与研究后，确定异常数据类型分别是冗余数据、缺失数据、噪声数据。

2.2.1 冗余数据

同一车辆同一时间的数据应是唯一的，由于采集或保存过程发生错误导致出现多条数据相同的信息，即为冗余数据。

2.2.2 缺失数据

数据缺失现象主要是记录中出入口站编号、出入口站日期/时间、车型、车种、轴数等字段缺失。与冗余现象产生的情况相类似，可能因为相关设备出现故障、信号传输中断或倒卡逃费行为。当缺失数据不易被系统监测到时，可能会导致大量数据缺失，没有被系统记录到[12]。

2.2.3 噪声数据

高速公路收费数据中噪声数据通常指不符合常理的损坏的数据，如入口站时间晚于出口站日期/时间、出入站时间不在数据调取的范围内、出入站编号有误[13]，即无法对应实际收费站、出入站编号相同，即车辆从同一收费站进出、车型、车种无法识别，即显示为“0”。其中出入站相同情况可能为换卡逃费或逃费行为以及系统内部错误。噪声数据通常被认为是会影响研究结果的没有意义的数据。由于系统故障或程序混乱会造成数据的产生。

故需针对以上异常数据做删除处理。

3 路径匹配算法研究

3.1 路径匹配的原则

在所给数据中筛选出一辆车所经过的门架信息数据，并将路径情况分为经过门架信息数据完整和经过门架信息数据缺失，其中经过门架信息缺失又分为在叉路口处缺失和不在岔路口处缺失。由于实际车辆行驶过程中，基本上所有的车主都会选择距离最短的路线，从经济方面考虑，既能节省通行时间，也能减少油费以及过路费等。因此当途经门架数据缺失，即路径不连续、不能拼接时，便按照两点间的最短距离所反映的路径作为车辆路径匹配的处理。

3.2 最优路径算法选择

在路径还原的应用中，常用的最优路径选择算法有Floyd算法、Dijkstra算法、逐次逼近算法。Dijkstra算法和逐次逼近算法虽然能得出最短路径的最优解，但由于计算时遍历的节点较多，效率较低，因此选取Floyd算法来寻找最优路径。

3.2.1 Floyd算法

Floyd算法又称插点法，是一种基于动态规划思想的最短路径算法。可以求解网络中任意两个节点之间的最短路径。最短路径的标记方法也各不相同，通常标记的最短路径需要反向查找[14]。为加速求解最短路径过程中的迭代。

给定图G及其边(i，j)的权wij(1≤i≤n；1≤j≤n)。

步骤1初始化距离矩阵W(0)和路由矩阵R(0)。

(1)

(2)

步骤2已求得W(k-1)和R(k-1)，依据下面的迭代求W(k)和R(k)。

(3)

(4)

步骤3若k≤n，重复步骤2；若k>n，终止。

3.2.2 Floyd加速算法

步骤1初始化距离矩阵W(0)和路由矩阵R(0)。

(5)

(6)

(7)

步骤3若W(k+1=W(k))迭代终止；否则返回步骤2。Floyd算法流程如图3所示。

图3 Floyd算法流程Fig.3 Flow chart of Floyd

3.2.3 Floyd算法的应用

Floyd算法的核心是利用局部最优解计算全局最优解，该算法可分为两个阶段:寻找最短路径长度，记录寻找路径长度的路径，即可以得到还原后的路径[16]。

3.3 路径匹配情况分类

3.3.1 经过门架信息数据完整

根据ETC门架数据，选取一辆车经过的路径，并在程序中输入该车辆经过的门架编号：path=[1,2,3,4,5,6,7,8,9,18]。程序运行后，输出结果为[1,2,3,4,5,6,7,8,9,18]，即车辆路径经过的门架编号依次为1,2,3,4,5,6,7,8,9,18。最后将结果得到的门架编号匹配到地图上，可以看出程序输出结果中的门架就是车辆实际路程经过的门架，由此完成了数据完整情况下车辆轨迹匹配，如图4所示。

图4 门架信息完整时车辆轨迹匹配结果Fig.4 Vehicle trajectory matching results when door frame information is complete

3.3.2 经过门架信息数据缺失

1)数据不在互通处缺失

根据ETC门架数据，选取一辆车路径信息并输入其经过的门架编号：path=[1,10,11,14,15,16,9,18]。将该车经过的门架匹配到地图上，如图5所示。初步断定编号为12、13的门架数据为缺失数据，在图5中用黑色门架符号标出。12号和13号为数据缺失门架，两门架在同一路段上，不在路段互通处，此种情况归类为数据不在互通处缺失的情况。

图5 门架数据缺失时车辆轨迹的地图匹配Fig.5 Map matching of vehicle tracks when missing door frame data

程序运行后，输出结果为[1,10,11,12,13,14,15,16,9,18]，即车辆路径经过的门架编号依次为1,10,11,12,13,14,15,16,9,18。将结果得到的门架编号匹配到地图上，如图6所示，程序输出结果中的门架就是车辆实际路程经过的门架，即图6中红色门架所在的路径为车辆行驶轨迹地图匹配后的路径。编号为12、13的门架为数据缺失的门架，此时完成了数据不在互通前后缺失时的情况下车辆轨迹匹配。

图6 门架数据缺失时车辆轨迹的地图匹配Fig.6 Matching results of vehicle tracks when door information is not at interoperability

2)数据在路段互通处缺失

当两个门架不在同一路段内时，而且数据在两个路段之间缺失，将此种情况归类为数据在路段互通处缺失，具体解释如下。

如图7所示，设车辆从RA门架行驶到RD门架，路段1的出口门架为C1、C2；路段2的入口门架为R1、R2；RA至路段出口的直达路径为RA-C1、RA-C2；路段2的入口至RD有2条路径R1-RD、R2-RD；C1、C2至R1、R2有4条直达路径信息：C1-R1、C1-R2、C2-R1、C2-R2。

计算过程如下：①查询信息表，获取RA门架的路段为 L1，RD门架的路段为 L2；②查询路段节点表，获取路段L1的出口门架分别为C1、C2，路段L2的入口门架为R1、R2；③查询路段L1的直达路径信息表，获取L1至路段出口的直达路径RA-C1、RA-C2；④查询路段L2的直达路径信息表，获取路段入口至RD的直达路径为R1-MD，R2-MD；⑤查询路段间直达路径表，获取C1、C2 至 R1、R2的直达路径信息C1-R1，C1-R2，C2-R1，C2-R2；⑥将3个结果组合，获得4个直达路径RA-C1-R1-RD、RA-C1-R2-RD、RA-C2-R1-RD、RA-C2-R2-RD；⑦选取拟合里程最少的路径作为计费路径。

图7 简易路径图Fig.7 Simple path map

根据ETC门架数据，选取一辆车经过的路径，并根据路径信息输入经过的门架编号，为path= [1,3,9,18]。将该车经过的门架匹配到地图上，中间途径的门架数据为缺失数据，如图8所示，用黑色门架符号标出数据缺失的门架。由于车辆从1号门架行驶到了3号门架及从3号门架行驶到了9号门架，中途路径数据上不可知。从1号到3号门架中间有两处互通，从3号到9号门架中间有两处互通，因此将此种情况归类为数据在互通处缺失的情况。

程序运行后，输出结果为[1,2,3,4,5,6,7,8,9,18]，即车辆路径经过的门架编号依次为1,2,3,4,5,6,7,8,9,18。将程序输出结果得到的门架编号匹配到地图上，程序输出结果中的门架就是车辆实际行驶经过的门架，如图9所示，红色门架所在的路径为车辆行驶轨迹地图匹配后的路径。编号为2,4,5,6,7,8的门架为数据缺失的门架，此时完成了数据在互通前后缺失时的情况下车辆轨迹匹配。

3)大量数据缺失

根据ETC门架数据，选取一辆车经过的路径，并根据路径信息输入经过的门架编号：path=[1, 18]。并将该车经过的门架匹配到地图上，此时只知道其起点和终点经过的门架，中间的门架数据缺失，并不知道这辆车走了哪条路径。如图10所示，数据缺失门架在下图中用黑色的门架符号标出。中间路径有四处互通处，并不知道车辆在互通处的行驶情况，因此归类为大量数据缺失。此时出现了多义性路径问题，需要进行车辆轨迹的识别。

图8 门架数据在互通前后缺失时车辆轨迹的地图匹配Fig.8 Map matching of vehicle tracks when gate data is missing before and after interoperability

程序运行后，输出结果为[1,2,11,12,13,14,15,16,9,18]，即车辆路径经过的门架编号依次为1,2,11,12,13,14,15,16,9,18。将程序输出结果得到的门架编号匹配到地图上，程序输出结果中的门架就是车辆实际行驶经过的门架，如图11所示，红色门架所在的路径为车辆行驶轨迹地图匹配后的路径。编号为2，11，12，13，14，15，16，9的门架为数据缺失的门架；编号为3，4，5，6，7，8，10，14，15，17为不经过的门架，即图11中标示出的黑色门架。此时完成了数据在大量缺失的情况下车辆的轨迹匹配，由此得出了多义性路径问题下车辆经过的门架结果。