跨省高速公路通行费快速计算方案

周 钢，徐 杰

(中远海运科技股份有限公司,上海 200135)

0 引 言

近些年，随着我国国民经济快速发展,交通运输业务快速增长，高速公路交通拥堵问题日益严重。为解决该问题，全国29个省(区、市)的ETC(Electronic Toll Collection)车道系统于2015年9月开始联网收费运行，全国的ETC车辆在省界主线收费站实现了不停车缴费通行，显著提高了高速公路的通行效率和服务水平。

2018年，国家提出“推动取消高速公路省界收费站”，进一步提升高速公路的服务能力和服务水平，更好地为经济社会的发展和人们的安全便捷出行服务。为贯彻落实国家的决策部署，交通运输部将重庆、四川、山东和江苏等4个地区作为试点，开展取消高速公路省界收费站的相关工作。高速公路省界收费站拆除之后，将从技术层面和管理层面带来新的问题。

1) 从技术层面看，虚拟省界收费站通过自由流ETC门架交易过往车辆，对车辆通行路径还原和计费有很高的时间要求。同时，对于自由流收费失败的车辆而言，在出口收费车道不仅需计算其所在省市的通行费额，而且需计算其在其他省市的通行费额;各省市的货车计费规则、绿色通行车辆执行标准、特殊车型认定和通行费优惠政策执行标准等都不尽相同，如何实现外省通行路段的计费是一个较难解决的问题。此外，对于省界标识点标识失败的多省通行车辆而言，如何还原其整体行驶路径也是一个急需解决的问题。

2) 从管理层面看，路网边界范围扩大会导致车辆单次通行费用急剧增加，U转通行车辆逃费、通行超时和节假日逃费等问题都会被放大，诱发更多的偷逃通行费行为。同时，车辆单次通行涉及多个省份，一旦出现争议，需多个高速公路通行管理单位联合处理，这会增加协调沟通的成本，增大管理难度。

1 总体方案

出于对目前的联网收费系统进行改造考虑，通过图论算法、云端计费系统、5.8 GHz标识和高清车牌图像识别卡口等技术手段，以“收费站计算为主、云平台计算为辅”为原则，采用“分省计费、统一收费”方式解决上述技术层面的问题。

物理省界收费站拆除之后，在收费广场原址建设省界虚拟收费站。省界虚拟收费站ETC门架交易系统采用5.8 GHz专用短程通信(DSRC)技术对经过的ETC车辆进行交易，生成ETC交易记录上传给省中心。对于经过的MTC(Manual Ton Collection)车辆，ETC门架交易系统将省界标识信息写入CPC卡，生成CPC卡通行记录上传给省中心。

收费站部署2台用于执行多省通行车辆通行费快速计算处理程序的服务器，部署方式应满足高可用性和双机互为备用的需求。对于单省通行的车辆，车道收费系统通过车道计费模块计算通行费;对于多省通行的车辆，车道收费系统通过收费站服务器上部署的多省通行车辆通行费快速计算处理程序计算通行费。

交通运输部联网中心(以下简称“部联网中心”)划分区域建设云端辅助计费系统。实体收费站的入口上道信息、高清车牌识别卡口的车辆高清车牌识别记录、5.8 GHz标识点的标识信息记录和省界虚拟收费站的车辆高清车牌识别信息及车辆通行记录等数据实时上传给部联网中心，作为云端辅助计费系统特殊情况处理和通行费计算的依据。

2 通行费计算实施模式

2.1 基于部联网中心-省中心-收费站的站级计费服务模式

各省中心基于通行费快速算法，以各省为单元生成各省的路网结构参数和费率计算参数，并将其上传至部联网中心。路网结构参数的格式由部联网中心统一定义，各省中心严格按照部联网中心的要求对这些参数进行录入和上传。由部联网中心对各省上传的路网结构参数的准确性、合理性和完整性进行校验，校验通过之后汇总所有省市的路网结构参数，形成一张全国高速公路路网结构图。费率计算参数不用统一，各省以文件包的方式将省内费率计算参数上传给部联网中心。

部联网中心将全国路网结构参数和各省市的费率计算参数文件打包生成联网省份费率参数文件下发给省中心，由省中心下发给收费站，供收费站服务器上的车辆通行费快速计算处理程序加载使用。收费站向车道提供多省通行计费服务接口。虚拟省界收费站由相邻的2个省中心共同建设，分不同的方向各自建设出省方向的自由流交易系统。省界虚拟收费站自由流交易系统从各自的省中心下载路网结构参数和费率计算参数，用于计算单省通行车辆的通行费。图1为基于收费站级服务的通行费计算数据流。

2.2 基于云平台的云端辅助计费系统模式

基于云平台的云端辅助计费系统(即通行费快速计算处理程序)部署在云端，由云端系统完成多省通行车辆的路径还原和通行费计算,同时降低出现单点故障的风险。

在云端辅助计费系统模式下，各省仍需按照收费站级计费服务模式上传路网结构参数和费率计算参数，汇总的联网省份费率参数不再下发。同时,收费站的入口交易记录和省界虚拟收费站的高清卡口标识信息上传给部联网中心云平台，用于辅助还原车辆行驶路径，以便更精确地计算通行费。

车道逐级上报多省通行计费请求至云端系统，计费请求包含车牌信息、车型信息、入口信息和路径信息等。云端辅助计费系统首先会根据省界虚拟收费站的标识信息,按省份划分路径，然后将各省路径信息交给各省费率计算模块进行路径还原和计费处理，从而得出各省的通行路径和车辆通行费。此外,对全部省市的通行金额进行叠加得出多省通行车辆通行费总金额，并将结果逐级返回至出口收费车道。图2为基于云平台的通行费计算数据流。

图1 基于收费站级服务的通行费计算数据流

图2 基于云平台的通行费计算数据流

2.3 具体实施方案

高速公路收费系统属于全天24 h不间断生产系统，其业务特点要求系统必须具有很强的耐用性，即使通信系统发生故障，车道系统仍可正常运行，保证收费秩序正常。因此，基于部联网中心-省中心-收费站的站级计费服务更适合作为常规计费模式。各省应强化收费站的站级计费系统，使收费站具有独立的费率计算能力，防止遭受网络攻击之后出现通信问题导致无法计算跨省费率。收费站站级计费服务系统完成对入口收费站信息和省界标识点信息的多省通行车辆的路径还原和通行费快速计算。

基于云平台的云端辅助计费系统模式能保证路网结构参数和费率计算参数的准确性和及时性。当入口收费站信息或省界标识点信息不完整、出口收费站费率参数未及时更新时，收费站站级收费系统无法及时有效地核查车辆通行情况，无法进行路径还原和通行费计算。基于云平台的云端辅助计费系统拥有这部分流水记录，通过车牌或卡号进行关联获取这部分数据，用于还原缺失的入口收费站信息或省界标识点信息，最终完成多省通行车辆的路径还原和通行费计算。

站级计费模式能摆脱收费站对外部网络的依赖，提高收费站的独立计费能力，增强系统的安全性。基于云平台计费系统模式，能提高参数的安全性，确保费率参数及时更新和参数的一致性；同时,能解决站级计费模式下路径信息不全等特殊情况下无法解决的问题。综上，多省通行车辆的通行费计算宜采用“站级计费服务为主，云端辅助计费系统为辅”的方式。

3 通行费计算方案

3.1 路径还原

路径还原用于还原多省通行车辆的完整行驶路径，从中确定车辆经过的省界虚拟站，得到的省内路径可不作为计费依据。路径还原以实际里程最短为寻优原则。图3为多省通行车辆通行路径示意。

注:1)A省、B省、C省、D省、E省和F省之间共有S1、S2、S3、S4、S5、S6和S7等7个省界虚拟收费站，以及F1、F2、F3和F4等4个标识点;

2)车辆从D省Sin收费站上道，从C省Sout收费站下道，卡内依次包含标识信息F3和F2;

3)通过寻优算法还原车辆完整行驶路径为Sin→S6→F3→S4→F2→S2→Sout，可从中确定车辆经过的省界虚拟收费站为S6、S4和S2；

4)路径还原完成之后，分别按照D省(Sin→S6)、E省(S6→S4)、B省(S4→S2)和C省(S2→Sout)计费，最后汇总计费金额

图3 多省通行车辆通行路径示意

3.2 创建路网结构模型

部联网中心定义统一格式的路网结构参数，各省市按定义完成各自的路网结构参数录制工作并将其上传至部联网中心，由部联网中心构建能使系统识别的由点和边组成的路网结构模型。该模型应保证路网解析方式一致、参数表结构定义和数据定义一致及异常寻优规则一致。

参照重庆市局部路网结构绘制路网元素分布示意,具体见图4。该路网包含标识点、路由节点、省界虚拟站和实体收费站(主线站是一种特殊的实体收费站)等内容。Li为路段编号；Nij为路由节点编号；Fi为标识点编号；Si为实体收费站编号。

图4 路网元素分布示意

路由节点用于定义省内路段间的连接关系和路段内的分支连接关系，同时包括跨省路段间的连接关系。1个路由节点由相交的2条路段上的各自1个虚拟逻辑站组成，1个路段分支点由路段内相交的2条支路上的的各自1个虚拟逻辑站组成。路段分支点是一种特殊的路由节点，本文只针对省内路段间的路由节点进行介绍，路段分支点和跨省路段间的路由节点原理与之相同。

虚拟逻辑收费站用于具体描述路由节点处2条路段的连接关系，是路网结构模型点边元素中的点，没有相应的收费车道，无法进行上下道。虚拟逻辑站编号用Vi表示。

图4为路网元素分布示意。其中：

1) 路网中总共存在9条路段，分别是L1、L2、L3、L4、L5、L6、L7、L8和L9。

2)L1路段包含S101、S102、S103和S104等实体收费站和V199、V198、V197和V196等虚拟逻辑站,其余路段也包含各自的实体收费站和虚拟逻辑站。

3) 路网中存在环的每条边上建设标识点，分别用F1、F2、F3、F4和F5表示。

4) 2条路相交的路由节点处需定义1个路由节点编号，比如L1与L2相交处的N12；3条路相交的路由节点处需定义3个路由节点编号，比如L5、L8和L9相交处的N58、N59和N89；x条路相交的路由节点处需定义个路由节点编号。

5) 相邻2个圆点(包括省界虚拟站、实体收费站及路由节点处定义的虚拟逻辑站)之间的路径定义为边；边的权值既可是实际里程(用于路径还原)，也可是计费金额(用于计费)。

6) 同一个路由节点处的虚拟逻辑站之间的边权值为0。

若以圆点为顶点，以相互之间的权值为边的邻接矩阵为G，则G按以下规则定义：

1) 若顶点Pi与Pj相邻，则G[i,j]=Wij，Wij表示边上的权值；

2) 若顶点Pi与Pj不相邻、不互通，则G[i,j]=无穷大；

3) 若顶点Pi与Pj属于同一路由节点，则G[i,j]=0。

根据路网结构的解析和元素定义结果生成基础参数，结合基础支撑算法，采用全国统一的路径还原寻优规则实现多省通行车辆的路径还原，采用各自省内的计费寻优规则实现车辆通行费动态计算。

3.3 基础参数

根据上述路网结构模型对路网结构中的点和边进行分类归纳，基础参数主要包括站点基础编码信息表、路由节点信息表和路段内费率表。

3.3.1 站点基础编码信息表

该表用来描述路段内的站点信息(包括实体收费站、省界虚拟站、虚拟逻辑站、标识点和掉头位等),组成信息包括路段编码、站点编码、站点名称、站点类型、物理序号、启用时间和版本号等。以图4中的L2路段为例，站点基础编码信息表见表1。

表1 L2路段站点基础编码信息表

3.3.2 路由节点信息表

该表用来描述省内路段与路段之间的关系和跨省路段与路段之间的关系。路由节点由2条不同路段的各自1个虚拟逻辑站点组成，组成信息包括节点编号、节点名称、路段编码1、站点编码1、路段编码2、站点编码2、启用状态、启用时间和版本号等。以图4中的L5、L8和L9路段相交的路由节点为例，路由节点信息表见表2。

表2 路由节点信息表

3.3.3 路段内费率表

该表用来描述路段内相邻2个站点之间的里程、单价和标识点信息，组成信息包括路段编码、站点编码1、站点编码2、实际里程、计费金额、标识点编码、启用时间和版本号等。以图4中的L2路段为例，共有4个站点，应包含12条路段内费率记录，部分记录见表3。

表3 路段内费率表

3.4 基础支撑算法

当前大部分省市都采用“笛卡尔表”将路网的全部路径和对应的通行费罗列出来，通过将实际路径与之匹配得出通行费。省界实体收费站拆除之后路网结构的叠加导致计算复杂度呈几何级增长，全国高速公路仍在不断建设联网接入系统，费率表更新频繁，采用“笛卡尔表”法罗列的全部路径会有十分庞大的数据量，参数的生成、存储、传输、运算和特殊情况处理都将成为问题。

全国路段形成一张大网之后，站点基数激增会导致运算效率下降。因此，本文先将路网的虚拟逻辑站作为点，将路段内虚拟逻辑站与虚拟逻辑站之间的实际里程作为边，计算出不同路段内虚拟逻辑站之间的最短路径，再加上入口收费站到入口路段虚拟逻辑站的路径和出口路段虚拟逻辑站到出口收费站的路径，构成一条完整的路径,最后根据规则从众多完整路径中选取一条最优路径作为最终结果。

因此，基于图论原理，将高速公路路网结构解析成点、边，根据车辆路径信息在“图”中还原车辆行驶路径，最终达到动态计算通行费的目的。

本文采用Dijkstra算法计算不同路段内虚拟逻辑站之间的最短路径，该算法时间复杂度为O(n^2)。

以图4为例，虚拟逻辑站组成的带权有向图见图5，共包含16个点和18条边(7条边权值大于0，用实线表示；11条边权值等于0，用虚线表示)。

图5 虚拟逻辑站带权有向图

现模拟计算L4路段S404收费站与L5路段S504收费站之间的最短距离，步骤如下：

1) 获取L4路段内的所有虚拟逻辑站V499和V498，以及L5路段内的所有虚拟逻辑站V599和V598;

2) 通过Dijkstra算法计算V499到其他虚拟逻辑站的最短距离；

3) 将V499到V599的最短距离和V499到V598的最短距离保留；

4) 重复步骤2)和步骤3)，计算V498到V599的最短距离和V498到V598的最短距离；

5) 将V499到V599的最短距离路径与S404到V499的路段内路径和V599到S504的路段内路径相加，构成一条完整的路径S404—V499—V599—S504；

6) 获取另外3条完整路径为S404—V499—V598—S504、S404—V498—V599—S504和S404—V498—V598—S504，从4条完整路径中选取里程最短的路径作为最终的计算结果。

3.5 费率计算模型

全国各高速公路联网收费省份的货车计费规则、绿通车辆执行标准、特殊车辆车型认定和通行费优惠政策执行标准都不尽相同，为降低取消高速公路省界收费站项目的难度和成本，促进各省计费规则的个性化发展，对于费率计算模型，采用图6所示的模型。

图6 费率计算模型

在该模型中，路径还原和叠加计费结果作为共性模块由部联网中心统一处理，针对具有差异性的各省费率计算模块，部联网中心定义统一的输入输出参数接口，各省按自己的计费规则对路径还原结果进行通行费计算，并将统一格式的计费结果反馈给叠加计费结果模块，形成一个完整的多省通行总通行费结果进行输出。

4 应用实例

2018年12月28日，随着川渝省界10座收费站全部停用，车辆从省界虚拟收费站高速通过，从跨省交易到跨省清分结算,通过了完整的数据周转流程，标志着川渝取消省界收费站取得圆满成功。迄今为止，系统运行平稳、高效，该方案的可行性得到充分验证。

5 结 语

本文所述方案解决了省界收费站拆除之后由于路网结构叠加导致的通行费计算量级呈几何级增长带来的计算效率问题，避免了采用“笛卡尔表” 方式引起的参数生成、存储、传输和运算方面的问题,实现了收费系统计费模块的动态化、实时化和快速化，计费规则更灵活，参数更易维护。同时，计费方案有效保留了联网收费省份各自的特殊收费规则，降低了改造成本。实施模式不仅满足了收费站独立的收费业务处理能力，而且提供了车辆异常通行情况下路径还原和通行费计算的处理通道。

由于当前技术的局限性，省界收费站拆除之后带来的U转车辆逃费、通行超时和节假日逃费等问题无法完全通过技术手段得到解决，可结合个人信用系统和稽查系统进行有效的管理，避免规则漏洞被无限放大利用。此外，关于路网结构中的路段交汇处非互通问题和掉头位问题，由于该方案的应用场景不涉及，因此未作描述，有待进一步研究。