一种基于有向图的高速公路5.8G多义性路径纠错识别算法

覃力更 李旭

摘要：随着高速公路不断建设，路网日趋复杂，多义性路径精确识别及通行费的计算拆分逐渐成为目前收费管理研究的热点。文章探讨了5.8G多义性路径识别在高速公路有向图中面临的问题，通过优化最短路径算法，对逆向标识数据进行自动纠错。该算法基于广西高速公路通行数据进行仿真实验，通行费计算准确度达到99.99%，逆向标识数据纠正率达到100%，同时计算效率能满足高速公路出口快速通行的要求。

关键词：5.8G DSRC;多义性路径识别;有向图

中图分类号：U491 文献标识码：A DOI：10.13282/j.cnki.wccst.2019.07.045

文章编号：1673-4874（2019）07-0150-04

0引言

随着我国高速公路不断建设，公路网结构变得错综复杂，路径多义性问题日益严峻。特别是我国目前实施高速公路联网收费，呈现出投资主体多元化以及管理结构形式多样性的特点，如不考虑车辆实际行驶路径，单单依靠记录车辆通过高速公路入、出口信息来实施收费操作，这种方式既不科学又不准确，也影响了不同投资主体的收费利益。通行费的拆分直接关系到高速公路收费运营工作，关系到各条高速公路的合法利益。

在基于视频车牌识别技术的基础上，5.8G DSRC已成为新的多义性路径标识技术标准，许多省份已进行了相关的试点研究。随着高速公路“营改增”不断深化，货车ETC、取消高速公路省界收费站等相关政策的不断推进，5.8G多义性路径识别技术、基于多义性路径识别的通行费精确计算与拆分显得尤为重要。

1问题描述

车辆从入口进入高速，经过存在多义性的路段被标识点标识，从出口驶出高速，收费车道系统需要根据该车辆的实际行驶路径进行收费并将相应的收费额清分给对应的路段业主。因为目前高速公路的模式是封闭式收费模式，若标识点数据足够完备，可以还原车辆的实际行驶路径。将高速路网转换成有向图，则该问题转换为求从起点依序经过指定点序列最终到达终点的最短路径。与此同时，在有向图模型中采用5.8G短程专用通信标识行驶车辆，还会存在标识点重复标识和标识点逆向标识这两个问题。

1.1标识点重复标识

在标识点所在路段拥堵时或者OBU、CPC卡多次唤醒的情况下，可能会发生同一标识点对同一个车辆（OBU、CPC卡）多次标识的情况，在出口读取标识点数据时会产生多次行驶经过该标识点的情况，干扰通行费的計算。

1.2标识点逆向标识

目前使用的5.8G标识点天线通信范围为扇形区域，容易误将对向车辆标识。CPC卡信号角度较广，有较大几率发生逆向标识的情况，而OBU安装位置固定且信号角度较窄，发生逆向标的几率很小。此外，若半幅路面封路维修，封路方向的车辆会改道至另外半幅路面，在原本单向的车道内双向通行，必然会发生逆向标识的情况。

由于使用的是有向图，收费系统在出口计费的时候采用逆向标识数据会导致计算出来的路径绕圈通行逆向的标识点，造成通行费额与实际不符。因此，一方面通过限制天线信号范围、采用信号范围控制较好的CPC卡和OBU减少逆向标识的发生;另一方面，在计费的算法中也要考虑如何处理逆向标识的情况。

2有向图多路径纠错识别算法

2.1基于有向图的高速公路路网建模

高速公路路网拓扑中包含的主要元素为互通立交、收费站出入口等。通过将互通立交、出入口等元素转换为方向确定的基本路段与道路节点的组合，可建立高速公路路网拓扑的有向图模型。

其中，表示W（X，y）道路节点X到道路节点y的最短路径收费额，可使用dijkstro最短路径算法求得0。本算法采用基于堆优化的dijkstro最短路径算法，并处理标识点重复标识与逆向标识的问题。

2.2标识数据预处理

为了避免标识点重复标识干扰费率计算，同时初步减少逆向标识的影响，本算法对于从OBU和卡内读取的标识点数据根据标识时间进行预处理。预处理规则为：

若在设定的时间间隔阈值内出现重复的标识点数据，则认为该车辆为单次通行多次标识，只保留该标识点第一次标识的数据;若标识时间间隔大于设定的阈值，则认为是不同的标识动作，不改变标识点序列。

2.3逆向标识数据纠正

由于高速公路限速且车辆的行驶速度有上限，我们可以通过行驶速度来判断行驶路径的合理性，从而筛选出逆向标识的情况并实现自动纠正。例如，一辆车经过标识点的原始通行方向速度为100 km/h，若逆向经过该标识点的速度为90 km/h，我们认为该车辆实际在通行标识点时被逆向标识了。在计算通行费时纠正标识点的方向，不仅影响当前子路径（以该标识点为终点）的通行费计算，还会影响下一条子路径（以该标识点为起点）的通行费计算。因此，在判断逆向标识数据时不仅要考虑当前路径的行驶速度，还需要考虑下一条子路径的行驶速度。

如果正向与逆向的行驶速度都超过速度阈值或者都在速度阈值内，即无法判断该标识点是否为逆向标识的情况，我们认为司机更倾向于走里程更短的路径，因此选择里程更短的标识方向。

3试验分析

3.1试验准备

为了验证本算法的有效性，我们采集一段时间内广西全区高速公路的收费数据进行计算验证。试验数据的要求指标见表1，试验考查的指标见下页表2。

在试验中，我们采用多个评价标准来评估本算法的有效性，如表2所示。

3.2结果分析

3.2.1收费一致性

车型收费的总体收费一致性为99.9983%，通行费误差比例平均值为17%，标准差为14%;计重收费的总体收费一致性概率为99.9953%，通行费误差比例平均值为10%，标准差为8%。收费一致性均高于99.99%。在不同标识点数量下的收费一致性如图1所示，个别计算结果与MTC实际收费不符，主要原因为车辆在收费站广场调头、个别标识点系统时间校准异常。

3.2.2逆向标识纠正率

首先对每个标识点数据做逆向处理后再进行通行费计算，然后与原始标识点数据的计算结果进行比较。所有标识点数据逆向之后计算得到的结果与原始计算结果一致，在试验中对逆向标识的纠正率为100%，表明本算法对于逆向标识具有很好的处理能力。

3.2.3无标识点收费一致性

试验通过遍历所有入出口及车型组合，计算通行费并与实际收费进行比较。试验结果与本算法的无标识点收费一致性为100%，表明在未启用5.8G多义性路径识别的条件下，本算法也能正确计算通行费，保证与现有收费系统的计费一致性。

3.2.4算法效率

试验使用CPU为Core i34330TE 2.4GHz，系统环境为32位Linux。本算法在不同标识点数量下的计算效率如图2所示，随着标识点数量增加，求最短路径的计算次数也会增加，导致计算耗时变大。

从总体计算效率角度进行评价，按车型收费的平均计算耗时为9 ms，在车辆经过所有标识点都是逆向标识的极端情况下，平均耗时为26ms;计重收费的平均计算耗时为8ms，在车辆经过所有标识点都是逆向标识的极端情况下，平均耗时为27ms。由此，我们可以看到算法的计算效率较高，能满足MTC及ETC的收费计算要求。

4结语

在高速公路路网有向图模型的基础上，本研究指出了有向图中5.8G多义性路径标识带来的问题，通过标识数据预处理过滤重复标识的数据，根据车辆行驶速度对逆向标识进行纠正，然后采用基于堆优化的dijkstra最短路径算法分析车辆通行路径并计算通行费用。本算法基于广西高速公路路网数据与MTC实际通行数据进行仿真实验，计算准确度达到99.99%，并且能有效地处理逆向标识数据。此外，本算法具有较高的计算效率，能满足高速公路出口快速通行的需求。同时需要注意，本计费方案自动纠正逆向标识依赖于标识记录的时间，因此对标识点系统的时间同步精度要求较高。

基于现有研究，下一步针对差异化收费、货车ETC、取消省界收费站等新的应用场景优化扩充算法。通过二义性路径大数据分析，为高速公路管理方提供稽查数据支持。