福建省高速公路多义性路径识别技术的研究

■林宇宁

（福建省高速公路信息科技有限公司，福州 350013）

1 研究背景

高速公路联网收费系统中的多路径问题已经逐步成为全国各省市高速公路收费中的一个突出问题，截至2017年末，福建省高速公路通车里程5228km，高速公路主体骨架网络已经形成，路网结构复杂，多义性路径数量已超过10万条。如果简单的采用最短路径法收费对高速公路的投资者显然是不公平的，那么如何确认车辆的实际行驶路径呢？如何根据高速公路路网特点以及车辆行驶习惯建立一套适合本省联网收费系统的多路径处理方案，各省都在不断研究探索新的技术和新的方法，来解决联网收费管理和高速公路发展的需要。

目前国内存在两种方法来解决多义性路径问题，一种方法是概率识别法，一种是精确识别法。概率识别法相对精确识别法来说，具有投资相对较小，系统改造风险较低等特点，故全国高速公路多数采用了概率识别法来解决多路径问题。

车辆路径的概率识别是通过交通均衡或非均衡理论为基础，建立各种理论模型和算法，分析计算特定高速公路网络的通行车辆交通分布与分配，从而确定路网中整体出行交通的行驶路径或单车的可能行驶路径。通过概率计算，可以确定路网中车辆整体行驶路径的分布，因此，当联网收费的拆分模式是由结算中心统一拆分时，就可以根据路网中车辆整体行驶路径的分布，按某一时间间隔拆分多路径的通行费。福建省采用了高清车牌照识别的方法来判断车辆的行驶路径，并基于识别出的车辆收费金额的比例对多路径的通行费进行拆分。下面详细讨论多义性路径识别系统在福建高速的具体实现方法及应用场景。

2 多义性路径生成

福建省高速公路路网基础数据是由表示路网顶点的收费站（包括互通枢纽）及表示路网边的区间构成。多义性路径生成就是要计算出每个收费站出发到达其他各收费站的车辆可能通行的路径。

2.1 多义性路径定义

福建省高速公路对多义性路径的判断依据：

(1)多义性路径环上“环外进、环内出”的车辆，若相对里程差30%以下，且绝对路径里程差距小于50km的，即为竞争性路径；否则为非竞争路径。

(2)多义性路径环上“环外进、环外出”的车辆，若相对里程差30%以下，且绝对路径里程差距小于50km的，即为竞争性路径；否则为非竞争路径。

(3)多义性路径环上“环内进、环外出”的车辆，若相对里程差30%以下，且绝对路径里程差距小于50km的，即为竞争性路径；否则为非竞争路径。

(4)多义性路径环上“环内进、环内出”的车辆，若相对里程差20%以下，且绝对路径里程差距小于50km的，即为竞争性路径；否则为非竞争路径。“环内进、环内出”。采用相对较低的相对里程差，是因为与其他情况比，这种情况的司机具有较好的方向感。

（5）青州大桥所在区间仅允许通行一次，通过绕环网调头而两次经过青州大桥的路径视为不存在的非法路径。

2．2 使用路网基础数据进行多义性路径计算的问题

在实际开发的过程中，发现仅使用代表路网顶点的收费站与虚拟收费站（互通枢纽）及代表路网边的双向区间进行多义性路径生成存在如下问题：

（1）存在部分收费站因单侧高速未修建轧道导致从该测通行的车辆无法下高速或者上高速后只能往一侧通行（如漳港、水古等），见图1A。

图1 路网特殊情况

（2）对于互通需要特殊判断每个互通只能连续通过两个节点，不允许通过多于两个节点如互通A→互通B→互通C这样的路径，见图1B。

（3）因路网特殊点轧道连接实际情况导致不允许通行的情况 （如漳州→福井可以通行，福井→紫泥可以通行，漳州→福井→紫泥不允许通行，需要在福井收费所下高速重新上高速才可以通行），见图1C。需要将每一个不允许通行的情况都记录下来特殊处理，容易遗漏且会大幅增加路径计算时间。

2.3 增加虚拟收费站点及用单向边表示高速区间

针对上述的问题，本系统中通过将一个收费站化作多个节点（A道、B道、高速入口、高速出口等）以及用单向边表示高速区间的办法对路网结构进行处理后，可以用图结构表示出高速路网的真实情况，避免上述的问题。

相连站点的A道与A道连接、B道与B道连接，AB道之间不存在相互连接，如图2A。

对实体收费站，入口点连接AB道表示双向均有轧道可以上高速；AB道连接出口点表示双向均有轧道可以下高速。而特殊的某一测无上下高速轧道的收费站可以通过只有单向连接出入口来表示，如图2B。

对于互通枢纽的虚拟站点，将其化作两个节点（互通入口、互通出口），外部站点进入互通连接到互通的入口点，互通的出口点连接到外部站点出高速。而互通枢纽虚拟站点之间，每个互通枢纽的入口连接其他互通枢纽的出口，如图3所示。这样可以从路网结构图上直接屏蔽互通站点内部通行的可能性，简化多义性路径查找的算法。

图3 对图1 B的处理

最后生成的用于多义性路径生成的路网图其中部分如下图4所示（正常站点的出入口节点不再画出）。图中可以看出存在很多特殊地点因轧道修建情况导致无法通行，如果只使用收费站点及双向的区间是无法表示，需要特殊处理。

图2 对图1 A的处理

图4 对图1 C的处理

2.4 计算出入口点对间可能路径的算法选择

将路网转化为由虚拟节点和单向车道组成的图结构之后，就可以直接使用图的通用算法进行多义性路径的查找工作。

在查找多义性路径时，理论上可以先使用Dijkstra算法找出最短路径，然后以该最短路径的长度作为限制，优化深度优先算法的搜索范围，砍掉不需要搜索的路径。但是由于福建高速青州大桥所在区间有特殊规则，其AB向车道总计只能够通行一次，而水古收费所以北的站点到水古收费所因只修了单侧匝道，需要经过马尾枢纽绕小环后折返，经过青州大桥两次返回水古另一侧车道下高速。这一实际上的最短路径不满足福建高速青州大桥只能通过一次的规则，需要当作非法路径处理。

所以Dijkstra算法找出最短路径的方法无法适应这一特殊规则。并且其他非遍历的查找最短路径的算法也无法适应这一规则。因此最终的软件实现采用深度优先遍历，并在过程中更新从该入口出发到每一个顶点的最短距离，以此来限制遍历深度的做法。

3 车辆多义性路径识别

3.1 高清车牌设备部署要求

福建省高速公路对所有存在多义性路径出入口点对间的每条竞争路段上至少安装一套高清车牌照识别设备，确保能识别到路径比例计算的“公平、公正、科学、合理”。

竞争路段指两个存在多异性路径的收费站之间的几条路径中不重叠的路段部分。

3.2 多义性路径标示串生成

多义性路径按照路径上所有的识别器，按照从入口到出口的顺序将识别器编号连接起来为该路径的车牌识别器标识串。而所有多义性路径均有经过的车牌识别器，并不会影响到对车辆多义性路径的判断，所以可以不列入车牌识别器标识串中。

如图5所示的环网中，边上的编号为安装的高清车牌识别器的编号。从A收费站出发到G收费站，共计有四条多义性路径，见下表1。其中在所有多义性路径公共部分的车牌识别器因为不影响具体路径的识别过程，所以可以不考虑（1001及1009）。

图5

表1

3．3 车辆行驶轨迹标识串生成

针对每一条存在多义性路径的点对之间的过车流水（无多义性路径点对间的流水不参与比例计算），根据流水的入口时间、出口时间及车牌，查找路径识别器数据中满足 （识别器抓拍车牌 =流水出口车牌且流水入口时间<识别器抓拍时间<流水出口时间）的所有识别器数据。将查询出的识别器数据按照抓拍时间排序并生成识别器串。其中车牌匹配要求为完全匹配，包括车牌的颜色在内需要和流水中的车牌完全一致。

如对车牌蓝闽A00001，在通行时间范围内有抓拍数据的识别点如下表2：

表2

则车辆行驶轨迹标识串为1002@1004（1001在环外不计）。

3.4 车辆行驶轨迹标示串与多义性路径标示串的匹配规则

车辆行驶轨迹标示串与多义性路径标示串的匹配规则为：车辆行驶轨迹标示串的每一个识别器均在多义性路径标示串中存在且前后顺序一致。

以表1中的四条路径为例：

表3

3.5 不能精确匹配的车辆二次分配规则

在多义性路径匹配中能唯一匹配到一条路径上的流水数据，根据费率路径在环内部分费额占总费额的比例直接将环上部分的金额及车次累加到对应路径上。

如果不能唯一匹配到一条路径上则将所有可能的路径记录并分配金额。表3中的过车流水经过一次分配结束后结果如下表4所示：

表4

二次分配时对不能精确匹配的金额及车次进行重新分配，分配规则为按照一次分配的金额及车次的比例，将二次分配的金额及车次分配给对应的路径。表4经过二次分配后最终环网金额及车次比例见下表5：

表5

4 多义性路径识别系统在福建高速的应用

目前本系统在福建省高速已有如下应用场景：

（1）收费收入在各路段公司的拆分

根据多义性路径过车金额比例，将每个出入口点对间的过车收入按照比例分配到不同的路线上，再根据每一条路线上的区间归属的路段公司将收入分配到路段公司上，最终累加所有点对上分配的收入获得路段公司拆帐总分配收入。

（2）估算区间车流量

根据多义性路径车流量比例，将每个出入口点对间的车流量分配到不同多义性路径上，可得不同路径上的车流量。最终累加所有点对上的车次获得高速每一个区间的估算车流量。

（3）测算精确路径收费的影响

目前福建省高速公路收费采用按照最低价路径收费的标准。通过多义性路径识别系统可以计算能够精确识别通行路径的车辆占高速总过车数的比例，并且通过车辆实际通行路径的费额可以估算车辆按照实际通行路径收费对全省收费额的影响。

（4）高清车牌识别器可以用电子车牌信息读取器等设备替代

高清车牌识别器在本系统中起到的仅仅是定位车辆位置及唯一标识车辆信息的作用。如今后车辆均安装电子车牌后，可替换成使用电子车牌信息读取设备，同样适用于本系统。只需要识别点的输入信息换成电子车牌信息读取器读取到的车牌信息即可，系统整体结构无需变化。