0 引言

近年来，随着高速公路基础建设的快速发展，高速公路路网逐步由树状结构逐步转化为网状结构。入口到出口之间往往存在多种可能的路径。由于高速公路投资主体的多元化，使得车辆行驶多义性路径识别问题不仅涉及通行费费率计算，更涉及通行费如何拆分到各投资主体的问题。因此，多义性路径识别问题的解决是确保通行费收入能够准确、合理、公平进行分配的关键环节^[1-4]。

现有高速公路费率计算方法普遍采用最短路径方法^{[1, 4]}，通过路网分析从入口到出口之间的最短路径，进行相应的计费与拆分计算。这种方法在路网越来越复杂的情况下，势必会引起越来越多的歧义，直接影响高速公路投资者的利益^[3-4]。

为了识别车辆行驶的实际路径，需要在路网中设置标识站^[5-6]，记录车辆经过的路径。标识站可以采用5.8G DSRC技术^[7]、433 M射频技术^[8-9]、视频车牌识别技术^[10-11]、基于运营商基站的标识技术等。这些技术将车辆经过的标识站点信息记录在车辆携带的OBU或CPC卡中，或者直接传送到收费站。车辆在出口时，通过读取这些信息，分析出车辆路径，进行计费和拆分处理。具体分析过程一般采用标识点之间最短路径方法^{[1, 4]}。

这种基本的多义性路径识别方法在实际使用中存在两个问题。首先是路径标识系统存在一定的不可靠性，形成了漏标记或者误标记。视频车牌识别技术极易受到天气状况的影响，另外还存在车牌污损、大车遮挡小车、车主套牌等问题，识别率只能达到90%左右^[10-11]。433M射频技术辐射距离远，容易对其他过往车辆产生误标^[8-9]。运营商基站信号的复杂性也会产生较多的漏标或误标。5.8G DSRC技术标识准确度虽然能达到99%以上，但由于卡片老化、标识天线故障、外部干扰等原因，也存在一定的漏标可能性^[7]。

另外，高速公路出口车流量极大，尤其是ETC车辆会在极短的时间通过出口，需要采用快速的多义性路径分析方法。

本研究提出一种基于有向图的高速公路多义性路径贝叶斯识别方法，将复杂的路网结构模型化为一个有向图，并将标识站点映射到该有向图中。对车辆标识站信息，采用贝叶斯分析方法，分析出车辆的实际路径。另外在实现过程中，采用两级结构，在中心级，对路网和标识站进行预分析处理，在收费站处，进行快速的匹配运算，保证车辆的快速通行。

1 基于有向图的多义性路径贝叶斯识别方法 1.1 基于有向图的路网建模及标识站映射

高速公路路网拓扑中包含很多元素，包括立交、出入口等，部分位置还可以进行车辆掉头，如收费站站前位置。高速公路拓扑模型已经在GIS等应用领域进行了很多研究^[12-13]，在这些研究中，将路网中平面交叉口、立交及其出入口简化成一个节点，同时每一个节点可以有许多路段与其相连接，建立一个图结构。陈雨人等^[14]进一步考虑了立交匝道信息，并在节点上增加方向性信息，但建立的依然是无向图模型，将道路的上下行方向作为图的同一条边。

为了准确描述车辆的行驶路径，必须针对车辆路径进行建模，包括区分道路的上下行方向，描述高速公路立交、出入口处匝道关系，以及道路上的掉头位置等。本研究采用一个有向图对路网进行建模。为了描述方便，进行如下定义:

定义1：基本路段a

基本路段时道路上方向确定且无任何分叉的一条路段，每个基本路段仅有一个唯一的入口点和一个唯一的出口点，分别记为v_start(a)和v_end(a)，车辆在基本路段上行驶路径和行驶方向是完全确定的。每个基本路段的长度值记为Length(a)。道路的上下行路段为两个基本路段。匝道也是一个基本路段。

定义2：道路节点v

道路节点指的是高速公路的入口、出口及分叉口，分叉口包括匝道口和掉头口。基本路段的入口点和出口点均为道路节点。将高速公路路网的所有入口道路节点集合记为V_Entry，所有出口道路节点集合记为V_Exit。

按照上述定义，高速公路网可用有向图=(V, A)表示，V为道路节点的集合，A为基本路段的集合。

以高速公路立交枢纽和出入口(带掉头口)道路结构为例，所建立的有向图如图 1和图 2所示：

其中，图 2中a₇，a₈，a₁₀，a₁₁的长度均为0。

车辆经过一个基本路段时，按路径顺序，可能会被零个或多个标识点标记，如被一个5.8G多路径标识天线标记，或者被高清车牌识别标识点标记。文献[15-19]研究了标识站的优化选址方法，在路网中采用较少的标识站就可以分析车辆的路径。由于每种标识技术都存在一定的漏标可能性，因此车辆经过一个基本路段，产生的标记结果也会有各种可能性。另外，5.8G DSRC标识技术和433M标识技术由于天线信号一般会同时覆盖上下行车道，所以，不仅对本路段经过的车辆进行标识，还会对反方向基本路段也进行标识。433M标识技术辐射距离比较远，甚至对附近的其他基本路段上的车辆进行标识。

对每一个基本路段a, 记它顺序所有可能的标识点为m₁，m₂，…，m_k。记m_i被标记上的概率为p(a, i), i=1，…，k。p(a, i)可以基于标识点m_i的技术类型取一个经验值，如对5.8G标识技术，可以取值为99.5%，视频车牌识别技术，可以取值为90%，也可基于对该标识点的试验结果，还可以基于历史记录进行学习取值。

这样，当车辆经过一个基本路段a时，产生一个标识串s=m_i1m_i2，…，m_in，其中1≤i₁ < i₂ < ，…，< i_n≤k。车辆经过该基本路段a产生标识串s的概率为：

(1)

1.2 针对每个出口建立路径生成树

定义3：车辆路径P

车辆路径是指车辆由一个高速公路入口点开始，经过一个或多个顺序连接的基本路段和道路节点，终止于一个高速公路出口点的路径，路径P的入口点与出口点分别记为v_start(P)和v_end(P)，其中v_start(P)∈V_Entry，v_end(P)∈V_Exit。记车辆路径P所经过的道路节点依次为v₀(P)=v_start(P)=v₁(P)，v₂(P)，…，v_n(P)=v_end(P)，所经过的基本路段依次为a₁(P)，a₂(P)，…，a_n(P)，其中∀i=1，…，n，v_i－1(P)=v_start(a_i(P))，v_i(P)=v_end(a_i(P))。

为了获得每个高速公路出口对应的所有车辆路径，在道路的拓扑结构建立之后，需要针对每个出口点，沿着路段方向，建立一个路径生成树。可以采用深度优先算法或者广度优先算法。由于高速路网中存在环状结构，而且部分车辆由于迷路等种种原因，有可能经过了环状路径。因此在形成路径生成树时，需要考虑环状路径。可以设置一个最大环数N_MaxLoop，在路径搜索时同一环上最多不超过该最大环数。

具体的路径生成树算法步骤如下：

(1) 针对每一个出口节点v₀∈V_Exit，以该节点为根节点，建议一个树Tree(v₀)。

(2) 针对树Tree(v₀)的每个叶子节点v₁，执行步骤3。

(3) 如果v₁不是高速公路的入口v₁∉V_Entry，在有向图=(V, A)找到所有以该节点为出口点的基本路段a，v_end(a)=v₁。针对每个基本路段a，执行步骤(4)~(6)。

(4) 针对每个基本路段a，查找v_start(a)。

(5) 在Tree(v₀)中查找v₁到根节点v₀的路径中v_start(a)出现的次数N(v_start(a))。

(6) 如果N(v_start(a)) < N_MaxLoop，则记录v_start(a)为v₁的1个子节点，并记录基本路段a为v_start(a)与v₁之间的连接关系。

(7) 返回步骤2，直到Tree(v₀)的所有叶子节点均为高速公路的入口点。

Tree(v₀)中每个叶子节点到根节点均形成一条车辆路径。从同一个入口点到出口点之间一般会有多条车辆路径。图 3为1个路径生成树的样例，从入口点v₇有3条路径到达出口点v₀。

记同一个入口v₁和同一个出口v₀的所有车辆路径集合为：

(2)

车辆从入口v₁到出口v₀选择PathSet(v₁, v₀)中的1条路径P，存在一定概率p(P)。这个概率可以根据不同路径之间的距离对比、收费比较、拥堵程度等情况根据经验估计，也可以根据车辆历史路径数据统计获得。

1.3 采用贝叶斯方法建立标识串的概率模型

当车辆经过路径P时，会顺序经过车辆路径P所包含的每个基本路段为a₁(P)，a₂(P)，…，a_n(P)，在每个基本路段上，会产生相应的标识串s₁，s₂，…，s_n。形成一个总标识串S=s₁s₂，…，s_n。

车辆经过路径P时，产生标识串S的概率可以通过路径上每个基本路段产生对应的子标识串的概率计算获得，概率为：(P))。

车辆在同一个入口和出口条件下，经过不同车辆路径时，可能会产生相同的标识串。如在2.2节实例拓扑中，若在基本路段a₃，a₄，a₈中没有架设标识站，或者被漏标，则路径P₁：v₅→v₃→v₁→v₀与路径P₂：v₅→v₁→v₀将会产生相同的标识串。

因此，对车辆产生的标识串结果，采用贝叶斯方法，获得车辆经过某条路径P的概率为：

(3)

当车辆到达出入口时，出口管理系统从车载单元或者路网信息中心读取入口、以及记录的沿途标识站信息。基于标识串，可以获得最大概率的车辆路径P_max(S), ∀P∈PathSet(v₁, v₀), p(P|S)≤p(P_max|S)。

可以将该路径作为车辆最终路径。在计算判断出最终路径信息基础上，按照分段计算费额，最后合并的方式，根据车型、轴数、重量，以及每一段的里程计算出最终计费额。

2 算法实现

在高速公路中，算法需要考虑出口处的快速计算，尤其对ETC车辆，一般要求在500 ms内完成费用分析。本算法在实际应用中可以分为省中心预处理过程和车道出口处快速计算过程两个部分。

省中心预处理过程：

(1) 建立路网有向图=(V, A)。

(2) 针对每个出口节点v₀，建立Tree(v₀)。

(3) 针对每个入口v₁，构建所有v₁到v₀的路径集合PathSet(v₁, v₀)。

(4) 分析所有v₁到v₀的路径标识串集合。

(5) 建立对每个标识串S，建立该标识串与最大似然车辆路径P_max(S)的对应关系。

(6) 将该对应关系(v₁, S)→P_max(S)下发给车道出口。

车道出口快速处理过程：

(1) 获取车辆入口节点，和标识串。

(2) 根据对应关系表，直接获得车辆的最大似然路径。

(3) 根据最大似然路径，计算车辆费用。

出口处由于只是一个简单的查表过程，计算复杂度非常低。

3 试验结果

为检验当前算法效果，在江西用89辆试验车(营运车辆)进行了一个月的数据试验，共计10 683次的路径信息，分别利用本研究算法以及最短路径算法对路径信息进行了处理，并与实际路径进行对比。采用的计算平台为至强E5-2637 3.0 GHz CPU×2, 16 RAM，实验结果如表 1所示：

通过表 1试验结果分析可知，基于有向图的多义性路径模糊识别算法在路径识别正确性较最短路径法有较大改善，而且无路径无法识别情况，其路径查询时间较长，算法仍有提升空间。

4 结论

本研究采用有向图对高速公路路网进行模型化，并将标识站映射到有向图上，然后采用贝叶斯方法分析车辆运行路径。通过联网中心和收费站两级处理方式，提高算法的计算速度，保证车辆的快速通行。该算法在江西省高速公路路网进行了实际的应用，对漏标和误标有较好的适应性，处理时间也能完全满足高速公路出口快速通行的需求。

下一步需要进一步扩充算法，支持高速公路分时段差异化费率等新的业务。另外，引入车辆经过标识站的时间及路径距离信息，进一步减少车辆路径识别的错误。算法还可以将异常匹配进行告警处理，帮助高速公路管理方防范车辆倒卡等逃费行为。