一种基于ETC门架流水的路径拟合方案--中国期刊网

字体：大中小

首页> 原创作品> 正文

一种基于ETC门架流水的路径拟合方案

发表时间：2021/5/31 来源：《基层建设》2021年第2期作者：李江锦

[导读] 摘要：随着我国高速公路总里程不断突破，高速公路网错综复杂。

        广西交科集团有限公司软件研究院广西南宁 530007
        摘要：随着我国高速公路总里程不断突破，高速公路网错综复杂。取消省界收费站后，车辆按实际通行ETC门架计费，但由于各种原因无法保证所有途经ETC门架的原始流水完整上传。本文提出使用ETC门架流水进行路径拟合，并处理门架反标、误标情况。基于广西区内高速公路数据进行测试，经验证计算效率能满足收费站出口车辆通行需求。
        关键词：高速公路；ETC门架；电子不停车收费系统；路径拟合
        0 引言
        近年来，随着我国经济的快速发展，高速公路的建设也不断加快，同时路网变得错综复杂，里程不断增加，截至2018年底，我国高速公路总里程突破14万公里。2019年5月16日，国务院办公厅印发《深化收费公路制度改革取消高速公路省界收费站实施方案》。方案要求，为进一步深化收费公路制度改革，加快取消全国高速公路省界收费站，实现不停车快捷收费，力争2019年底前基本取消全国高速公路省界收费站。2020年1月1日全国高速公路取消省界收费站后，ETC门架系统成为取消省界收费站后的必备硬件设施。车辆通过ETC门架系统时，按其所管辖里程和收费标准计算，然而，车辆行驶过程中，可能出现司机拔卡和屏蔽OBU的行为，门架系统可能发生网络故障，会导致部分门架流水数据缺失，从而使得违法逃费成为可能。
        因此，需要基于ETC门架原始流水进行路径拟合，通过算法补充缺失的门架路径，还原路网中车辆实际行驶路径。一方面满足稽查人员对车辆行驶轨迹的监控管理，另一方面涉及对应路段通行费额的计算与清分。
        1 行驶路径分析
        车辆驶入收费站入口，驶离收费站出口时，入出口车道软件记录车辆牌识信息（车牌号，车牌颜色，车型，车轴等）、通行编号passid、计费信息、通行时间等并上传存储至省中心在线计费平台数据库。车辆行驶过程中途经ETC门架时，由门架系统通过RSU实现对车辆信息的记录，将其与门架编号、通行时间等数据一并上传至省中心数据库。形成原始的ETC门架流水信息。对路径拟合有重要影响的流水信息有通行编号passid、途经时间、门架编号和牌识信息。
        2 数据建模
        2.1有向图建模
        高速公路路网主要包括收费站入口、收费站出口以及互通（如立交桥或匝道）。高速公路中没有分叉的路段称为基本路段（也称为收费单元），每个收费单元的里程、方向、费率是固定的，且入口标识点和出口标识点均唯一，标识点的入度和出度可以有0个、一个或多个，从而形成路网关系图。对于收费站入出口和互通则建立虚拟标识点，其里程和金额为0。这样就可将标识点转换为路网拓扑结构中的节点，收费单元作为拓扑结构的边。将拓扑结构的节点集合记为V，收费单元记为E，高速公路路网则可用带权有向图G=（V，E）来表示。
        后台系统根据录入的路网信息（如收费站和门架的名称、编号、经纬度，门架编号及管辖的收费单元，收费单元的入出标识点、里程、基础费率）生成路网关系表。其中，可将收费单元的里程或基础费率作为相邻节点的权值。
        2.2最短路径算法
        dijkstra算法是典型的单源最短路径算法，用于计算有向图中一个节点到其它所有节点的最短路径。使用广度优先搜索思想，以起始点为中心，向其它节点层层扩展，直到其它所有节点均遍历完成。在高速公路路网中，一般指定起始节点和结束节点（如收费站入口与收费站出口）。故在遍历节点过程中找到结束节点时即返回结果，不再遍历。
        结合本方案，dijkstra算法核心思想描述如下：
        给定带权有向图G=（V，E），指定起点s和终点e，求v到e的最短路径。将图中顶点集合V分成两组集合：集合S和集合U。集合S用于记录已求出最短路径的顶点，集合U用于记录尚未求出最短路径的顶点。初始时，集合S只有一个顶点（源点s），其余顶点在集合U中。接着在集合U中找路径最短的顶点，将其加入集合S中，在加入的过程中，始终保持从源点s到集合S中各顶点的最短路径不大于从源点s到集合U中任何顶点的最短路径。重复步骤，直至终点e加入集合S。
        在实际项目中使用基于堆优化的dijkstra最短路径算法，以减少算法时间复杂度。
        3 方案设计
        3.1 总体思路
        当车辆达到收费站出口时，车道软件向省中心在线计费平台发起扣费请求，附带数据包含收费站出口信息、passid、牌识信息，等。在线计费平台收到请求后，根据passid和牌识信息查询对应的存储于数据库的门架流水记录，获取途经的门架序列。
        接着对原始门架数据进行预处理。
        再利用dijkstra算法求出收费站入口至收费站出口的最短路径。在此过程中使用行驶速度对原始门架的反标、误标进行判断。需要指出的是，原始门架序列可能缺少部分门架数据，处理反标和误标过程也会剔除部分门架数据，因此只能在处理后的合理节点之间求解最短路径，在行驶速度不超过阈值情况下，假定司机会走更短的路径（但不一定是真实的路径）。
        最后输出拟合后的门架序列及收费单元序列。
        3.2 软件流程
        路径拟合核心流程如图1所示：

图1 路径拟合核心流程图

        图2 收费单元数量与耗时图
        主要步骤描述如下：
        （1）初始化及数据预处理。加载路网信息表数据至内存。判断收费站入出口，时间等参数是否合法。如存在门架序列，则判断其合法性，删除编号重复的门架，对门架序列按时间顺序重新排序。
        （2）利用dijkstra算法求出收费站入口至收费站出口的最短路径，得到默认路径。
        （3）判断是否存在途经门架序列。
        （4）如不存在途经门架序列，或存在途经门架序列但途经门架序列均在默认路径序列中，则默认路径即为最终拟合的路径，流程结束。
        （5）如途经门架序列不在默认路径序列中，则进行反标和误标处理。利用dijkstra算法求出上一门架A到当前门架B的里程，结合两门架流水时间计算出行驶速度，如超过系统速度阈值（设定为120 km/h）认为不合理，再以门架B对向门架B’计算速度，如在速度阈值内则认为B为反标，需将其替换为B’。如果门架A到门架B、门架A到门架B’计算的速度均超过阈值，则认为门架B误标，将其剔除出原始门架序列。
        （6）将经过步骤（5）得到的门架序列标记为新节点，遍历新节点列表，求出两两节点之间的最短路径，最后合并各段最短路径，输出拟合后的门架序列及对应的收费单元序列。
        4 方案验证
        4.1 测试环境
        本次验证在CPU为Intel（R）Core（TM）i5-3210M CPU @ 2.50GHz（双核），内存为2GB，系统为CentOS 7.6 64 bit工控机上进行。采用的数据为最近一段时间内广西全区的收费数据。
        4.2 测试结果
        （1）双向收费一致性
        通行相同路径的正反向时，收费金额应保持一致。经测试，所有通行路径正反向金额均一致。
        （2）性能测试
        本方案在不同收费单元数量的耗时如图2所示。随着收费单元数量增加，平均耗时亦增大。去掉最大和最小耗时，整体平均耗时约在10ms~30ms之间。可以看到算法效率较高，能满足收费站出口车辆通行需求。
        以广西区内最短路径里程最长的收费站为例，两收费站里程约为870公里，包含60个门架，68个收费单元，平均耗时为28ms。所有途经节点均参与dijkstra算法计算，平均耗时为44ms。极端情况下，当60个门架均非合法，平均耗时增长至264ms。
        5结语与展望
        本文通过车辆行驶路径分析，结合高速公路路网拓扑结构创建有向图模型，对原始门架流水序列进行去重、排序处理，使用基于堆排序优化的dijkstra算法求出车辆通行最短路径，并处理反标、误标门架。本方案使用广西区内高速公路数据进行测试，算法效率较高，可以满足收费站出口车辆通行时间需求。本文方案对ETC门架反标、误标的处理依赖于门架记录的时间，如果系统时间未同步或同步精度达不到要求，会导致拟合的路径存在一定误差。
        下一步将在生产环境进行优化算法，另外将路径拟合结果应用到清分结算系统，确保收费金额清分的准确性。
        参考文献：
        [1]中华人民共和国交通运输部．取消高速公路省界收费站总体技术方案[Z]．交办公路函〔2019〕320号，2019.
        [2]中华人民共和国交通运输部．计费模块路径拟合及流程设计指南[Z]．交路网函〔2020〕142号，2020.
        [3]邓国强，韩颖铮．一种基于改进堆优化Dijkstra算法的最小费用最大流算法[J]．计算机与现代化，2020，000（002）：8-11.
        [4]王树西，吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学，2012（5）：223-228.