复杂路网情况下路径清分算法研究

郝建明，　李长亮

(中海网络科技股份有限公司，上海 200135)

复杂路网情况下路径清分算法研究

郝建明，李长亮

(中海网络科技股份有限公司，上海 200135)

摘要:为使高速公路中的通行费清分更加公平、公正、高效，从复杂路网入手，参考国内多个省份的路径清分算法，结合贵州路网结构，提出一种基于二义性区域的路径清分算法。将该算法应用于实际中，很好地解决了在二义性区域内拆分给最短路径业主带来的不公平问题。其同样适用于相似路网结构的联网收费清分系统。

关键词:清分算法；最短路径；二义性区域

0引言

近年来，我国的高速公路产业随着经济的发展得到了迅猛发展，大部分省、市、自治区的高速公路都已陆续实现联网收费、统一清分。但在统一清分过程中，经营业主最关心的是通行费清分是否公平、公正、高效，因此，对从入口站到出口站有多条路径情况下的通行费清分算法和原则进行研究显得尤为重要。

通行费的计算大多采用的最小费额法，即按路网中从入口到出口所有可能的行驶路径中收费最少的路径(简称最小费额路径)收取的原则进行计算；通行费清分则根据所有可能的行驶路径中的最短路程(简称最短路径)进行。若路网结构中最小费额路径与最短路径不相同且两者的业主不一致，则按照最短路径清分就显得不够公平。

二义性区域是指同一个入口点到出口点中存在着两条具有竞争性且分属不同的业主的路径。二义性区域内的各条路径统称“二义性”路径，现有路网结构中普遍存在。在二义性区域中合理清分以做到公平公正是一个难题。对此，参考国内多个省份的路径清分算法，结合贵州路网结构，提出一种基于二义性区域的路径清分算法，在实际运行过程中起到了良好的效果。

1国内外研究现状

国外对高速公路进行呈规模收费的不多，且营运公司或单位比较单一，研究重点主要是电子不停车收费，甚至结合全球定位系统(Global Positioning System,GPS)，属于精确跟踪定位，不存在“二义性”路径问题。

近几年，由于重型卡车的增加导致高速公路的建设和维护成本增加，德国开始对此类车征收通行费，采取GPS与移动通信相结合的技术方案，在车上安装一个带有GPS导航功能的移动通信终端，当车辆在高速公路上行驶时，此设备就将该车的行驶状态发送到数据处理中心，这样其“二义性”路径问题就可以直接从GPS导航信息中获取。

目前我国许多省份的联网收费里程都已有几千公里，路网结构越来越复杂，“二义性”路径问题也越来越突出。在解决“二义性”路径问题的方案中，不同省份采用的方式各不相同，总体来说技术路线分为以下两种。

1) 射频识别法：基于RFID技术，在高速公路的路径识别点安装射频识别设备，当车辆经过采集点时，将标识站点信息写入通行介质，同时将车辆信息上传至收费中心系统。采用该方法的省份有广东、四川。

2) 车牌识别法：即在高速公路的路径识别点安装车牌识别设备，用于采集车牌号码，将车牌信息上传至收费中心系统，通过后台匹配出入口车牌和路径识别点上传车牌来确定车辆的行驶路径。采用该方法的省份有湖北、江西、贵州等。

2清分算法研究

2.1路径清分算法研究

2.1.1路径清分算法的核心问题

在高速公路实施联网收费后，确定车辆行驶路径成为了通行费清分的核心问题。待车辆的行驶路径确定后，再按照各经营路段所占通行费的比例进行通行费的清分工作。但是，受设备损坏、设备识别精度等因素影响，无论是射频识别法还是车牌识别法，都无法完全定位车辆的行驶路径。

基于上述提出的划分二义性区域方法，在进行通行费清分工作时，对于经过二义性区域的车辆，首先将通行费清分到二义性区域上(即得出二义性区域总的清分金额)，然后对二义性区域内部的各路径进行二次清分。清分算法分为以下两种情况:

(1) 在二义性区域内车辆行驶路径明确，该种情况下按照普通车辆清分规则清分；

(2) 在二义性区域内车辆行驶路径不明确，该种情况下需采用模糊清分算法清分。

2.1.2模糊路径清分算法

目前各省份所用的模糊路径清分算法不尽相同，比较常用的为以下两种:

(1) 最短路径法，即认为车辆在二义性区域内总是按照最短的路径行驶，将通行费分配给最短路径上的经营业主；

(2) 按比例分配法，即认为车辆在二义性区域内选择哪条路径行驶存在比例分配，通常用各路径上精确识别的车辆清分金额比例来分配模糊路径的通行费金额，比例的取值范围通常采用当天的清分金额比例。

2.1.3贵州复杂路网路径清分算法

在进行二义性区域内明确路径的通行费清分时，清分规则与普通路径清分规则一致。

在进行二义性区域内模糊路径的通行费清分时，最短路径法适用于二义性区域内的竞争性路径里程差距较大的情况。贵州的二义性区域内各条路径的里程差距较小，因此不适合采用最短路径法。

对于按比例分配法，考虑到车牌识别设备的故障率等因素，采用当天的比例可能导致某车牌识别设备损坏的业主模糊通行费损失较大。因此，提出采用清分日前30天的平均比例作为模糊路径通行费的清分比例，以此降低设备故障对通行费清分的影响，保证各家经营业主的合法权益。

2.2路网结构分析

目前贵州全省高速公里建设里程已经突破4 000 km，随着建设里程逐渐增加，路网的复杂度也随之成几何倍数增加。

1) 简单二义性路径，即同一出入口之间存在两条竞争性收费路径。图1为贵阳-晴兴组成的简单二义性区域示意图，为使示意图简洁，贵阳周边的8个相关收费站没有全部标出。

2) 嵌套二义性区域，即一个二义性区域内的某条路径上存在一个嵌套子二义性区域。图2为贵阳-思南组成的二义性区域(以下简称外层二义性区域)示意图，其中贵阳-剑河-思南线上还有一个贵阳-都匀的嵌套子二义性区域(以下简称内层子二义性区域)，为使示意图简洁，贵阳、遵义周边的25个收费部没有全部标出。

图1　贵阳-晴兴组成的简单二义性区域示意图

图2　贵阳周边、遵义周边、思南、剑河组成的嵌套二义性区域示意图

3) 交叉二义性区域，即两个相邻二义性区域有重叠部分。图3为贵阳-思南及贵阳-晴兴两个二义性区域组成的交叉二义性区域示意图，为使示意图简洁，贵阳周边的19个收费站没有全部标出。

图3　思南-贵阳-晴兴组成的交叉二义性区域示意图

3复杂路网清分算法说明

3.1普通路径拆分

普通路径是指同一出/入口之间不存在二义性区域的路径，其清分原则比较明确、统一，即按照最小费额路径进行收费，按照最短路径上的各路段的应收费额比例进行拆分。在拆分通行费金额时，需要精确计算，将计算结果直接四舍五入到分，并将尾差调整给最后1个有收益的业主。计算公式为

(1)

式(1)中：L为路段应收费额。

例如：某一型车从甲收费站驶入高速公路，从乙收费站驶出，共行驶了75 km，先后经过A公司20 km(应收费额为10.67元)、B公司15 km(应收费额为8.1元)；C公司40 km(应收费额为21.33元)、D公司1 km(应收费额为0.55元),收费站实际收费额为40元。其拆分步骤为：

(1) 计算：总应收费额=10.67元+8.1元+21.33元+0.55元=40.65元；

(2) 按照式(1)进行拆分，可得A公司通行费XA=10.50元，B公司通行费XB=7.97元，C公司通行费XC=20.99元，D公司通行费XD=0.54元；

(3) 计算已拆分金额=10.50元+7.97元+20.99元+0.54元=40元；

(4) 进行尾差调整，已拆分金额等于已收金额，无需进行尾差调整。

3.2简单二义性区域拆分

对于简单二义性区域(如图1)，其外部的路段业主收益不能因为车辆在二义性区域内选择的行驶路径不同而有变化，因此需要进行两次拆分。

1) 计算整个二义性区域应拆分的金额。把二义性区域作为一个虚拟业主，其应收费额取其最小费额路径上的路段应收费额之和。

2) 在二义性区域内部，根据车辆精确识别路径或按照该二义性区域前30天精确识别的拆分通行费金额比进行二次拆分。

在二义性区域内，车辆选择通行哪条路径都是有可能的。因此，在两条路径上分别安装车牌捕捉识别仪器，对于识别到的车辆，认为其对于精确识别路径的车辆；对于两个车牌识别仪器都未识别到的车辆，认为其是未识别路径的车辆。此时的第二次拆分可分为以下两种情况。

(1) 对于精确识别路径车辆的通行费，把二义性区域应拆分总金额二次拆分给精确路径上的各个业主；

(2) 对于未识别路径车辆的通行费，首先计算该二义性区域内每条路径上前30天的精确识别车辆所拆分的金额合计，用两者的比例把该二义性区域应拆分总金额分到两条路径上，在每条路径上进行二次拆分。

3.3嵌套二义性区域拆分

1) 把外层二义性区域作为一个虚拟业主(其应收费额是该二义性区域的最小费额路径上各个路段的应收费额之和)，第一次拆分计算出该虚拟业主的应拆分总金额。

2) 根据外层二义性区域的车牌识别情况把外层二义性区域的应拆分总金额拆分到精确识别的路径上或按照比例拆分到两条路径上。如果路径上有内层子二义性区域，把内层子二义性区域作为一个独立的虚拟业主，其应收费额是该内层子二义性区域的最小费额路径各个路段的应收费额之和。

3) 如果含有内层之二义性区域，按照该二义性区域的车牌识别情况把该二义性区域的应拆分总金额拆分给精确识别的路径上或按照该二义性区域前30天精确识别车辆所拆分的合计金额比例拆分给两条路径，内层子二义性区域的拆分可视为1个简单二义性区域的拆分。

3.4交叉二义性区域拆分

对于交叉二义性区域，其含有两个无法精确拆分的二义性区域(分别称为A二义性区域和B二义性区域)，因此需要有4个车牌识别点。根据两对车牌识别点识别的情况，可把交叉二义性区域的拆分分成以下三种情况处理。

1) 对于A和B两个二义性区域都精确识别的，交叉二义性区域的应拆分总金额直接拆分给精确识别的路径(即拆分给A区域的识别路径和B区域的识别路径)。

2) 对于A和B两个二义性区域只有1个精确识别的，精确识别的二义性区域对应的应拆分总金额直接拆分给该二义性区域的精确识别路径，未精确识别的二义性区域对应的应拆分总金额按照该二义性区域前30天精确识别车辆所拆分的金额比例拆分给两条路径。

3) 对于A和B两个二义性区域都未精确识别的，按照前两种情况过去30天内各业主的实际拆分金额比例拆分该区域应拆分总金额。

4算法应用

所提出的算法从2014年7月开始正式启用，取2014-07-05/2014-07-13贵阳-晴兴二义性区域的真实现金流水数据进行对比，原拆分金额(即最短路径拆分)和二义性拆分金额对比表见表1。可见，采用该算法的实际清分结果更公平，更能保障各经营业主的合法权益。

表1　原拆分金额和二义性拆分金额对比表

5结语

该清分路径算法以贵州省高速公路联网收费路径清分系统为对象设计，很好地解决了在二义性区域内拆分给最短路径业主带来的不公平问题。由于贵州省高速公路路网结构在国内较为典型，因此该算法有一定的通用型，适用于其他相似路网结构的清分。对于有嵌套二义性区域和八字形区域组成的路网结构，均可使用该算法提高拆分公平性，提升工作效率。

参考文献：

[1]李猛.基于RFID技术多义性路径识别系统在高速公路联网收费中的应用[J].广东科技,2013(16):155-156.

[2]徐青松,王力鹏,陈健华.典型高速公路路网的清分路径算法[J].上海船舶运输科学研究所学报,2011,34(12)：168-171.

中图分类号：U495

文献标志码：A

A Route Clearing Algorithm in Complex Highway Tolling System

HaoJianming,LiChangliang

(China Shipping Network Technology Co., Ltd, Shanghai 200135, China)

Abstract:The existing highway toll clearing algorithms distribute the toll income according to the principle of the shortest path, which may not fair in some ambiguous areas of complex highway networks. In view of such a problem a new highway toll clearing algorithm is designed based on route distinguishing. The algorithm has been successfully used in highway network in Guizhou province. The algorithm is equally applicable to the clearing systems for similar network structures.

Key words:clearing algorithm; shortest path algorithm; ambiguous section