基于改进蚁群算法的高速公路协同救援路径规划

张健 范晓武

摘  要： 针对高速公路多点协同救援路径规划问题，文章综合考虑路段行驶时间和路径安全性两个优化目标，设计路径评价函数。根据高速公路救援的特点，引入“助手结点”的概念来设置信息素初始浓度;引入搜索角、结点直线距离和安全因素设计了启发函数;使用随机选择机制来优化状态转移规则;最后引入奖励机制设计了信息素更新规则，通过这四个方面改进了蚁群算法。在此基础上，建立多点协同救援模型，采用表上作业法确定救援车辆派遣方案。仿真实验结果表明，改进的蚁群算法和原始的蚁群算法相比，不但收敛速度更快，而且优化了全局最优解。改进的蚁群算法与表上作业法的结合，实现了多救援点协同救援的路径规划功能。

关键词： 路径规划; 多点协同救援; 蚁群算法; 表上作业法

中图分类号：TP391.1          文献标识码：A   文章编号：1006-8228（2021）03-01-05

Path planning of expressway cooperative rescue using improved ant colony algorithm

Zhang Jian， Fan Xiaowu

（Zhejiang Comprehensive Transportation Big Data Center Co.， Ltd.， Hangzhou， Zhejiang 310018， China）

Abstract： Aiming at the multi-point collaborative rescue path planning for expressway， this paper designs a path evaluation function considering the two optimization objectives of road travel time and path safety. According to the characteristics of expressway rescue， the concept of "assistant node" is introduced to set the initial concentration of pheromone; heuristic function is designed by introducing search angle， linear distance between nodes and safety factor; state transition rule is optimized by using random selection mechanism; pheromone update rule is designed by introducing reward mechanism， thereby the ant colony algorithm is improved. On this basis， the multi-point cooperative rescue model is established， and the dispatching scheme of rescue vehicles is determined by the method of operation on table. The simulation results show that the improved ant colony algorithm not only converges faster than the original one， but also optimizes the global optimal solution. The combination of the improved ant colony algorithm with the method of operation on table realizes the function of multi-point cooperative rescue path planning.

Key words： path planning; multi-point cooperative rescue; ant colony algorithm; operation on table

0 引言

我国高速公路建设规模不断扩大，交通量持续增加，诸如高危化工品泄露、车辆追尾、碰撞等交通事故的发生频率也随之升高。事故发生后，交通指挥部门应及时制定救援方案，实施救援工作，这对于缓解道路拥堵、减少人员伤亡和财产损失具有重要意义。其中，合理地规划救援路径，使救援人员和车辆尽可能快的到达事故点是保障救援工作及时开展的关键。

救援路径规划的优化目标包括出行时间最短、拥堵程度最小、路径最短、路线安全系数最高等。李紫瑶[1]以出行时间最短和路线长度最短为目标建立了应急车辆路径寻优模型。何勇[2]建立了救援车辆运输成本最小、运输时间最短的优化模型，設计了应急资源配送路径。Duan等人[3]首先以最短出行时间为目标，在此基础之上考虑最小拥挤程度，建立了两阶段应急车辆路径规划模型。然而，这些研究工作在解决救援路径规划问题时大多将时间、拥堵程度和成本等作为优化目标，路径的可靠性没有得到研究者的广泛关注。由于高速公路具有封闭性的特点，若在救援过程中出现二次事故，将会使车流波传播到更大的路网，导致交通状况陷入更糟糕的状态。所以高速公路应急救援需考虑路段行驶时间和道路安全性。王晓刚[4]使用加权求和法考虑路线的行程时间、时间可靠性和安全性，构建多目标路径选择模型。肖博[5]从次生危害的角度出发，建立了行驶总时间最小和危险性最小的路径优化模型。

传统的路径规划方法包括混合蛙跳算法[6]，遗传算法[7-9]以及蚁群算法。其中蚁群算法具有正反馈、良好的并行搜索能力和全局搜索能力，它可以从复杂解空间的多点同时开始搜索，在解决多目标优化问题方面具有良好的性能，被广泛应用于求解多目标路径规划问题。谈晓勇等人[10]提出一种混沌干扰的蚁群系统优化算法来解决以最短距离、最小成本和最小风险为优化目标的应急车辆调度问题。韦晓[11]使用改进的蚁群算法解决了以最短时间和最小成本的多目标救护车路径规划问题。

当高速公路同一时间段内发生多起交通事故时，多救援点协同救援将会大大提升总体救援效率，而先前的研究很少考虑多救援点多事故点的情形。针对以上问题，本文综合考虑路段行驶时间和路径安全性两个因素，设计路径多目标优化评价函数，利用改进的蚁群算法求解救援点到事故点的最佳路径，根据救援点和事故点的供需关系建立协同派遣模型，采用表上作业法求解模型得到多救援点到多事故点的最优派遣方案。改进的蚁群算法具有更快的收敛速度，并且能获得更优的目标函数值。

1 问题描述与模型建立

本文将高速公路路网抽象为有向图[G（V，E）]其中[V]表示顶点集合，[E]表示顶点与顶点之间的连接边，即路段。假设救援点数量为[N]，事故点数量为[M]，[du]表示事故点u需要的救援车辆数，[rl]表示救援点l所储备的救援车辆數，[Zlu]表示从救援点[l]到事故点[u]的最优救援路径的路径评价函数值，[xlu]为决策变量，表示从救援点[l]派遣到事故点[u]的救援车辆数。每个救援点可以将救援车辆派遣到各个事故点，每个事故点可以接受由多个救援点派遣出的救援车辆的救援，从而达到多救援点协同救援的目的。以总体路径评价函数值之和最小为目标，建立多救援点协同救援派遣的数学模型，具体如下：

[minZ=ω1Z1+ω2Z2] ⑴

[tij=t01+α1QCβ1] ⑵

[Z1=i=1Nj=1Ntijxij] ⑶

[Z2=i=1Nj=1Neijxij] ⑷

约束条件包括：

[l=1nxlu=du，u∈1，2，…，m] ⑸

[u=1mxlu≤rl，l∈1，2，…，n] ⑹

[u=1mdu≤l=1nrl] ⑺

[xlu≥0，l∈1，2，…，n，u∈1，2，…，m] ⑻

式⑴表示多目标优化评价函数的数值，[Z1]表示该路径通行所花费的时间，[Z2]表示道路安全因素。[ω1]，[ω2]分别表示[Z1]，[Z2]所占比重。式⑵为BPR函数，[t0]为该路段自由流行驶时间，[Q]为该路段的实际交通流量，[C]为该路段的通行能力，[α1和β1]为待定参数。式⑶中，[xij]为决策变量，表示是否选择路段（i，j）。式⑷中，[eij]表示路段（i，j）的风险系数。式⑸表示派遣到事故点的救援车辆数要等于事故点所需要的救援车辆数;式⑹表示救援点所储备的救援车辆数应大于等于该救援点派遣出去的救援车辆数;式⑺表示假设救援点的救援车辆总数能满足事故点的救援车辆总需求数;式⑻表示决策变量取值范围。

2 基于改进蚁群算法的多点协同救援

经典蚁群算法全局搜索能力较差，当算法运行一段时间后，由于正反馈的累积作用，蚁群的搜索能力会停滞不前，且收敛速度也会降低。为了提升最佳路径的搜寻速度，在其已有优势的基础上进行改进，来获得性能更好的蚁群算法，本文采用改进的蚁群算法规划各救援点到达各事故点的最优救援路径，建立多救援点协同救援模型，最后采用表上作业法确定目标函数值最小的救援车辆派遣方案。

2.1 改进蚁群算法的设计

2.1.1 初始信息素浓度设置

本文引入“助手结点”的概念，根据目标结点的位置将信息素初始浓度设置为：

[τij0=ε+ε0若j与事故点e相邻接ε否则] ⑼

其中，[ε]表示一般路段上的信息素初始浓度，[ε+ε0]表示与事故点e相邻接节点的相邻路段的信息素初始浓度。

“助手结点”是指与目标事故点e相邻的结点。式⑼描述的信息素初始浓度设置方式提升了“助手结点”与其周围节点间路段的信息素浓度，从而路径的重要程度一开始便得以区分，蚂蚁能更快地找到最优路径。

2.1.2 启发函数改进

本文综合多个要求，设计启发函数为：

[ηij=1μ1dij+μ2dja+μ3Δθπeij] ⑽

其中，[dij]表示路段（i，j）的实际距离，[dja]为节点j与事故点a之间的直线距离，[Δθ]表示直线（i，j）与直线（j，a）之间的夹角。[μ1， μ2， μ3]为待定参数。

从启发函数计算式可以看出，搜索将优先考虑距离长度短、与终点距离小且指向终点并且路段安全性高的路段。启发函数的改进加强了搜索的方向性，即优先选择偏向终点角度小的邻接节点，缩小了搜索范围并且加快了搜索速度。

2.1.3 使用随机选择机制改进状态转移规则

[pkij=τijαηijβwijrjτijαηijβwijrk，j∈allowedk0others] ⑾

[j=arg maxτijαηijβwijr，r∈（0，q1）pkij，r∈（q1，q2）argmaxwij，r∈（q2，1）] ⑿

其中，式⑾为传统蚁群算法的状态转移公式，[τij]表示路段（i，j）上的信息素浓度;[ηij]表示路段（i，j）之间的启发式信息;[wij]为路段（i，j）之间路阻通行时间的倒数;[α]为信息素权重因子;[β]为启发式信息权重因子;[r]为路阻通行时间权重因子。式⑿为使用随机选择机制改进的状态转移规则，[q1，q2]为分类选择参数，[r]为随机因子。

本文使用随机选择机制改进的状态转移规则用[q1，q2]分类选择参数将下一个要访问的节点分类为三种选择。这样既保证了搜索的收敛性好，又增强了搜索策略的多样性。同时结合应用场景，将路阻通行时间最小路段的相应节点作为概率转移中的一项选择。

2.1.4 改进信息素更新策略

当蚂蚁k经过某个路段（i，j）时，路段（i，j）上的信息素浓度被更新。

[τijt+Δt=1-ρτijt+log1+k=1mΔτkijt] ⒀

[Δτkijt=ψkQZk，螞蚁k经过路段i，j0，否则] ⒁

[ψk=1+Zavg-ZkZavg-Zbest，Zk

其中，式⒀中[τijt]表示第t轮迭代时路段（i，j）上的信息素浓度，[ρ]表示信息素的挥发程度，[Δτkij（t）]表示蚂蚁k经过路段（i，j）留下的信息素增量，m表示蚂蚁数量。式⒁中[Zk]表示第k只蚂蚁的路径评价函数值。式⒂为“激励度”系数[ψk]。

改进后的信息素更新规则通过引入奖励机制，对于走得比平均水平更好的蚂蚁给予奖励。可在短时间内通过信息素的增量上的差别来增大优秀路径和其他路径之间的信息素浓度的差距，最终能引导算法收敛到的结果为全局最优路径，同时加快算法的收敛速度。

2.2 改进蚁群算法的流程

改进蚁群算法流程图如图1所示。

本文提出的改进蚁群算法的实现步骤如下。

Step 1：根据高速公路路网结构信息和交通流数据，用路网矩阵表示相关信息。

Step 2：初始化参数，根据式⑼设置各路段初始信息素浓度，在救援点节点放置m只蚂蚁，将事故点作为目标终点。

Step 3：蚂蚁k根据式⑽计算可选节点的启发函数，随后根据式⑿选择下一个路径节点j。

Step 4：判断蚂蚁当前访问的路径节点是否为目标事故点，若不是则转step 3;若为目标事故点则结束该蚂蚁的路径寻找。

Step 5：根据式⑴计算路径的路径评价函数值，更新最优救援路径和相应的路径评价函数值。

Step 6：根据式⒀更新每条路径上的信息素含量。

Step 7：判断是否满足终止条件，如果迭代次数[Nc≥Nmax]则迭代结束，否则清空禁忌表进行新的迭代。

2.3 采用表上作业法确定协同救援方案

当同一时段内有多个应急事件发生时，如何从各个救援点调度资源是决定救援是否高效的重要举措。假设救援点所储备的救援车辆数量大于等于该救援点派遣出去的救援车辆数量，故协同救援本质上是产销不平衡的运输问题，已有学者针对产销不平衡的运输问题进行了研究[12]。

在采用改进蚁群算法得到各救援点到各事故点的最优救援路径和相应的路径评价函数值的基础上，设置一个假想事故点[M+1]来接收多余的救援车辆，从而将供需不平衡问题转换为供需平衡问题。假想事故点[M+1]需要的救援车辆数为多余的救援车辆数[dM+1=l=1nrl-u=1mdu]，并将这些救援车辆从救援点到假想事故点[M+1]的路径评价函数值Z设置为0，由此可以得到供需平衡问题下的各救援点到各事故点的路径评价函数值表。最后采用表上作业法确定救援车辆派遣方案，实现多救援点协同救援。具体步骤如下。

Step1：采用伏格尔法获得初始基变量可行解。

Step2：利用位势法验证初始基变量可行解是否为最优解。

Step 3：利用闭回路调整法改进可行解，直到可行解为最优解，即最优派遣方案。

表上作业法求解流程图如图2所示。

3 实验与结果分析

3.1 模型参数设置

以杭州市周边高速公路路网为例，验证本文算法的有效性。路网中共有45个结点，其中交通枢纽有14个，高速互通有31个，如图3所示。本文改进的蚁群算法的各项基本参数分别为：迭代次数[Nmax]=100，蚂蚁数量m=10，启发因子α=0.3，β=1，信息素因子Q=1，权重因子γ=0.6，经过反复实验，取分类选择参数q1=0.1，q2=0.9。

3.2 实验结果

将蚁群算法的起点设置为结点6，终点设置为结点34，两个算法最终的运行结果如图4所示。

由图4可以发现，虽然两个算法最后都收敛到了同一个目标函数值，但是改进的蚁群算法收敛速度比传统的蚁群算法更快。由于改进的蚁群算法在计算启发函数时考虑了多种因素，并在信息素更新策略中引入了奖励机制，从而使改进的蚁群算法和传统蚁群算法相比，收敛速度更快。

以结点6为起点结点34为终点，两种算法各运行10次，得到的平均目标函数值如表1所示。

由表1可以发现，改进的蚁群算法和传统的蚁群算法相比，收敛到的平均目标函数值更小。这是因为改进的蚁群算法在启发函数中考虑了路段发生二次事故的概率，而传统蚁群算法只考虑下一结点与当前结点的距离大小，在应急救援路径规划中考虑的因素过于单一，从而导致其目标函数值偏高。

为验证多地协同救援派遣方案的正确性，假设各救援点的救援车辆储备数和各事故点的救援车辆需求数如表2所示。

利用改进的蚁群算法对表2中各个救援点到各个事故点进行路径规划，得到各条路径的目标函数值，如表3所示，并结合表上作业法进行车辆派遣，实验结果如表4所示。

表4中，第一行表示勾庄互通救援点派出1辆救援车到半山互通，派出1辆救援车到五常互通，其余依此类推。可以看到表上作业法较好地解决了多点协同救援问题。

4 结束语

本文在经典蚁群算法的基础上，提出改进的蚁群算法来解决高速公路多点协同救援问题，从初始信息素浓度设置、启发函数、状态转移规则、信息素更新规则等方面进行改进，解决了蚁群算法在路径寻优过程中出现的停滞现象、收敛过慢的问题。本文将改进的蚁群算法与表上作业法相结合，实现了多救援点协同救援的路径规划功能，为高速公路救援工作争取了宝贵的时间，具有很大的实用价值。

参考文献（References）：

[1] 李紫瑶.应急救援车辆路径寻优——基于多目标改进蚁群算法[J].技术经济与管理研究，2011.9：7-10

[2] 何勇.應急救援物资配送模型及算法研究[D].广东工业大学，2016.

[3] Duan P， Xiong S， Jiang H. Multi-objective optimization

model based on heuristic ant colony algorithm for emergency evacua-tion[C]//International IEEE Conference on Intelligent Transportation Systems. IEEE，2012.

[4] 王晓刚，韩印.救援车辆多目标实时路径规划模型[J].物流科技，2019.42（9）：15-17，31

[5] 肖博.基于多目标优化的震后应急物流路径规划研究[D].长安大学，2019.

[6] Jiandong Z， Yujie G， Xiaohong D. Dy-namic Path

Planning of Emergency Vehi-cles Based on Travel Time Prediction[J]. Journal of Advanced Transportation，2017.2017：1-14

[7] Roberge V， Tarbouchi M， Labonte G. Comparison of

Parallel Genetic Algorithm and Particle Swarm Optimization for Re-al-Time UAV Path Planning[J].IEEE Transactions on Industrial Informatics，2013.9（1）：132-141

[8] 陈晓燕，姚高伟，张鲲等.基于遗传算法的无线传感器节点定

位在农业的应用[J].软件，2015.36（4）：1-5

[9] 聂敬云，李春青，李威威等.关于遗传算法优化的最小二乘支持向量机在MBR仿真预测中的研究[J].软件，2015.36（5）：40-44

[10] 谈晓勇，林鹰.基于混沌蚁群算法的应急救援车辆调度优化[J].计算机应用研究，2014.31（009）：2640-2643

[11] 韦晓.基于改进蚁群算法的应急物流车辆路径问题研究[D].济南大学硕士学位论文，2015.

[12] 张孟飞，王铁旦，李建楠.基于表上作业法的产销不平衡运输问题应用[J].价值工程，2018.037（023）：24-27