基于免疫遗传优化的实时交通路径诱导方法

刘智萍，周清华，彭吉琼，杨 真

(1.江西科技学院信息工程学院，江西 南昌 330098；2.江西科技学院，江西 南昌 330098；3.华东交通大学网络信息中心，江西 南昌 330098)

1 引言

如今，汽车数量的迅速增多导致道路承载量受到威胁，交通事故、交通堵塞等问题较为严重[1]。为降低城市交通路网压力，降低各类资源损耗，智能交通孕育而生。智能交通将计算机、通信、控制等高新技术有机融合并应用在交通指挥中，构建一种多角度、规模庞大且实时性强的交通运输管理系统。其中交通路径诱导为智能交通系统中的核心部分[2]，可按照不断改变的交通现状，快速准确地给出行者提供诱导数据，并以最快速度抵达目的地，完成网络优化控制。

为实现交通路径的有效诱导，陈业华[3]等人通过构建紧急函数，利用行驶时间感知方法，给突发事件距离内的用户搭配行驶路线，并推算最短路径信息。但该方法极易产生局部最优解，计算精确性有待加强。邓辉[4]等人通过明确车辆行驶数据，融合交通信号配时和路径转向信息，获得现阶段路段路阻，按照每个路段的路阻信息与路网拓扑，挑选行程时间最短的路线为诱导路径。但该方法冗余参变量较多，计算时间较长。

为进一步改善城市交通拥堵现象，为驾驶员提供合理、高效行驶路线，提出一种基于免疫遗传优化的实时交通路径诱导方法。组建实时交通局部路网模型展现整个交通道路拓扑结构，计算最短路径的同时，使用免疫遗传优化方法中的评估、选择、交叉等过程完成高效率车辆交通路径诱导，并利用仿真证明了本文方法的可靠性。

2 实时交通局部路网模型构建

(1)

在途行驶车辆一般会受到道路交通流的直接影响，道路交通状态指数就是道路的交通流形态[5]。在局部路网模型内，路阻越高，交通情况越糟糕，这也会影响模型节点之间的流通情况。

代入一个出行预期速率临界值λ，该临界值定义了出行者期望实现的行驶速度均值。若某个路段的路阻高于临界值，证明行车过程中无法处在顺畅状态，路阻接近无穷大，路段内众多节点之间互不相通；反之，节点之间为相通状态。

路阻矩阵D(λ)处于出行预期速率临界值情况下，路网内邻近的两个节点间的真实通行代价，将其描述成

D(λ)=[dij(λ)]m×n

(2)

其中

(3)

其中，aij表示两个节点的空间相邻关联。λ为路阻系数。

明确出行预期速率临界值后，得到局部路网的空间动态临界矩阵是

A(λ)=[aij(λ)]

(4)

其中

(5)

城市交通路网内局部交通流数量较多，更易发生交通事故，导致车辆没有经过的诱导路径产生堵塞，因此要及时更新诱导路径[6]。

为保障驾驶路径的较强连通性，使用动态连通性指标推算并判断车辆目前方位周边的局部路网，同时实现诱导路径更新目标。局部路网将诱导路网内驾驶的车辆方位作为标准，包含周边某些范围，并伴随车辆行驶过程动态变换位置，一直维持从目前节点至终点的动态连通性能。

局部路网最少包括诱导路径内的两个节点，将其定义成有向图GLocal(PLocal，ELocal，D(λ)，pO，pD，λ)。PLocal代表局部路网节点集合，ELocal表示局部路网边集合，pO为路径初始点，pD为路径结束点。

节点pO、pD均位于诱导路径内，两者之间符合〈pO，pD〉的关联，即行驶过程中首先通过节点pO，然后路过节点pD。为便于理解，把局部诱导路径内的节点依照车辆行驶路过的先后顺序实施编码，也就是局部诱导路径内的节点〈pO，…，pi，…，pD〉当作整数1，…，i，…，q。同理，节点pO、pD间的关联也可记作pO

图1 初始点和其余节点之间的关联

推算初始点po可为出行者更新路径供应较为充分的时间完成决策反应，对局部路网计算、路径更新等因素也具备较大影响[7]。

(6)

若车辆抵达节点pGet并得到当前交通数据，则

(7)

因此节点pO要符合如下收敛公式

(8)

终点与局部路网范围对出行者在局部路网内挑选可能的备用路径拥有重要作用。恰当的终点路径规划可以确保在不同水准的交通堵塞状态下，和初始点之间始终具备一条可靠的连通路径[8]。设定一个可达临界值U，则终点要符合式(9)的约束条件。

Φ(L，M，pD，λ)≥U

(9)

局部路网范围可直接决定了出行者挑选备用路径的面积。若范围较广，备用路径通常个数很多，在备用路径满足固定个数情况下，出行者就能找到最适合自己的连通路径。但局部路网范围广带来的直接问题为路径冗余率过高，增加了人们的出行成本，给交通行驶带来一定压力[9]。

此外，通常拥有若干个符合式(9)需求的局部路网，但不同路径的路阻各不相等，可达路阻越低的路网连通性能越优秀。所以最优局部路网的范围要满足下列约束公式

(10)

总结以上内容，按照交通堵塞临界值与路阻函数，推算D(λ)值，并计算出起点pO，按照式(9)获得终点pD，然后通过式(10)明确集合P与E的值，求出最优的局部路网，保证后续算法中能获得更加完整的备用路径，增强交通路径诱导可靠性。

3 实时交通最短路径确定

利用上述过程在掌握整体交通路况状态下，提取出拥堵时可以缓解交通压力的最短路径。实时动态交通诱导使用滚动循环策略完成交通疏导任务，其最短路径Q的数学表达形式为

(11)

其中

(12)

符合式(11)和收敛条件式(12)的解即为从出行初始点至终点的最短路径。在实时交通路径诱导的有向图模型内，前K条最短路径问题可以定义成：假设vi、vj是有向图G中固定的两个顶点，r是vi、vj间的一条路径，长度是z(r)。通过vi、vj间的全部互不相等的路径构成的集合R(G，vi，vj)为G内vi与vj之间的路径集合，得到

R(G，vi，vj)={r}

(13)

根据路径长短进行排序[10-11]，将会获得如下结果

r1，r2，…，rQ|z(r1)≤z(r2)≤…≤z(rQ)

(14)

至此将r1当作有向图内vi与vj之间的第一最短路径，z(r1)表示长度，以此类推，rQ是有向图内vi与vj之间的第Q个最短路径，z(rQ)表示路径长度。

4 免疫遗传优化下交通路径诱导

免疫遗传算法是在生物免疫前提下的改进遗传算法，将求解问题设置成抗原，解是免疫系统抗体。在局部路网规模庞大的情况下，应用传统遗传算法探寻最短路径难度很高，计算时间也随之增多[12]。代入一个单点交叉算子完成优化控制，从全局角度操控交叉过程，拓展解的搜寻空间，防止产生早熟收敛并呈现出陷入局部最优解的现象。基于免疫遗传优化的实时交通路径诱导方法的运算过程如下：

步骤1：从抗原种群内任意调选一个抗原个体，同时设置有关的参变量。待优化目标函数与各类收敛条件是免疫遗传算法中的抗原，设定群体模式、交叉概率、变异概率三个目标项，群体模式M的值越高，搜寻区域面积越大，但各代的遗传流程耗时就会变多，反之M越低遗传操作时间越少，搜寻空间面积越小。

步骤2：在抗体种群内任意生成抗体样本，在初次操作中，抗体个数随机产生，但在二次操作时，需应用免疫机制记忆功能。抗体拥有优秀的适应度，因此能有效提升收敛速率。

步骤3：运算出抗体、抗原的亲密度及浓度。依次算出抗原与抗体、抗体和抗体之间的亲密度，抗原与抗体之间的亲密度拥有Euclidean距离、Manhattan距离、Hamming距离等多个表达模式。

步骤4：更新记忆细胞。把和抗原亲密度水平较高的抗体引入记忆细胞，记忆细胞个数拥有一定局限性，在记忆细胞内使用全新引入的抗体替代与自身亲密度最高的原始抗体。

步骤5：抗体的促进与约束。免疫系统功能是利用遍布于身体各个部分的免疫细胞共同工作完成的。免疫细胞内含吞噬和淋巴两种细胞类型。淋巴细胞内包含B、T不同作用的细胞。B细胞可以生成抗体，进行特异体液免疫，T细胞能完成特异细胞免疫及免疫调整。把抗原、B细胞与抗体看作优化问题的函数、解xi和求解适应度函数f(xi)。

N个抗体组成一个非空免疫系统集合X，将抗体f(xi)在集合X中的距离描述成

(15)

由此推导出抗体浓度计算方程

(16)

在式(16)基础上，设计一个抗体浓度概率选择解析式

(17)

步骤6：更新群体规模。变异操作与交叉操作的过程与遗传算法大致相等，任意择取两个抗体。依照预先安排的变异概率实施变异，然后两两之间互相交叉，和更新之后的记忆细胞抗体变成全新的种群。

整体来说，步骤3～6是一个评估、选择、交叉与变异的循环流程，所以要反复执行以上步骤，直到最优个体适应度函数低于某个预期值或实现期望的加速循环次数，然后终止算法，实现高精度实时交通路径诱导，缓解车辆高峰期出行不便的困扰，让车辆可以更快抵达目的地。

5 仿真研究

利用仿真评估所提方法实用性，实验平台为VISSIM软件。实验方法为本文方法及文献[3]、[4]方法，将某市堵塞区域路网为例，路网内共11个节点，如图2所示。

图2 路网拓扑图

以路段标号1-10为例，预测时间是晚高峰17：00～19：00，以7天为一个周期，计算三种路径诱导方法下所经路线的车辆个数情况，遇到的车辆个数越少，证明实时交通路径诱导可靠性越高，行驶更加畅通。实验选用文献[3]方法和文献[4]方法作为实验对照组，与所提方法的实验结果进行对比。三种方法对比结果如图3所示。

图3 三种方法路径诱导所遇车辆的对比情况

由图3可知，两个文献方法诱导路径策略下的道路车辆个数远远大于本文方法，而本文方法诱导路径道路上的车辆个数最少，最贴合日常驾车出行的交通诱导需求。这是因为本文方法通过构建实时交通局部路网模型，并利用节点间的动态连通性得到交通路径全局状况，由此获得高精度的交通量诱导路线。

对比三种方法在不更改出行时间状况下，计算诱导路径的最佳路径分配结果，将预测交通量当作数据输入，对路网采取仿真。三种方法下的实时交通路径诱导情况如表1所示。

表1 实时交通路径诱导对比

根据表1所得实验结果可知，相比于两个文献方法，本文方法下的停车次数、通行时间均值、排队延迟及排队长度均有大幅度缩减，诱导后的路网车辆通行速率得到改善，拥堵情况也得到不同程度的缓解。本文方法在路径择取方面更加符合出行者的心理需求，并维持优秀的路网均衡，在全局上呈现出更优质的诱导成效，可以起到不同路面驾驶情况下的交通疏导作用。

6 结论

针对日益严峻的交通道路拥挤问题，提出基于免疫遗传优化的实时交通路径诱导方法。本文方法计算方便快捷，路径规划精度较高，通过与传统方法的仿真对比，证明了所提方法的适用性与可靠性，给驾驶员提供实时交通数据的最短路径，降低车辆停留时间，完善城市交通安全。