基于改进鱼群算法的应急车辆最优路径选择

张 涛，谢金宝

（兰州交通大学 交通运输学院，甘肃 兰州730070）

突发事件会造成人民生命和财产的巨大损失，对应急车辆路径问题的研究就是在尽可能短的时间内，更合理、科学地选择最优的车辆路径，最大限度降低应急成本，是救援工作中极为重要的研究内容。

我国学者更多是从理论方面出发，定性研究应急物流的特点、保障机制和组织形式等问题；在定量方面，研究相对较少。我国是一个突发灾害频发的国家，目前系统地、定量地对我国灾害救援应急车辆路径优化模型和应对迟缓、缺少科学依据的决策问题的研究，具有重要的现实意义。针对人工智能算法在求解优化问题方面的优势，本文通过建立应急车辆最优路径选择模型，且在基本鱼群算法的理论基础上，提出一种改进的人工鱼群算法并将其应用到应急车辆路径选择问题上。

1 建立模型

1.1 问题描述

对应急车辆路径选择问题的描述:选择应急总时间最短为目标，在只有一个物资储备中心，车载容量一定情况下，选择车辆数尽可能少的为n个受灾点提供应急物资，在完成对各受灾点的物资配送后，车辆又回到物资储备中心。

假设条件:

1）物资储备中心与受灾点的坐标已知；

2）救援完成后车辆应回到起始地点重新装载货物；

3）每个受灾点只被一辆车救援一次；

4）每辆车所运输救援物资不能超过车辆的负载能力。

1.2 模型建立

根据图论方面的知识，设G＝（V，E）为应急救援的路网，且该路网是一个完备图。其中V为顶点集合，E为边集合，顶点之间的距离权值为lij（lij＞0）。

定义变量:

建立应急救援车辆路径优化模型:

式中:di为各受灾点物资需求数量；D为车辆的负载数量；lij为路网中任意两点之间的距离；¯v为车辆的平均速度；vmax为车辆的最大速度；qij为（i，j）弧的畅通度；pij为（i，j）弧上最大容量；vij为车辆经过（i，j）路径的实际速度，若pijqij¯v≤vmax时，vij＝pijqij¯v，否则vij＝vmax；tij为经过（i，j）弧的时间，即tij＝lij／vij。

式（2）～式（6）是该模型的约束条件。

2 基本鱼群算法

人工鱼群算法的主要算子有鱼群的觅食、聚群、追尾等行为。算法中涉及的参数定义为

N:鱼群个体大小；

｛Xi｝:鱼个体的状态位置；

Yi＝f（Xi）:第i条鱼当前所在位置的食物浓度，Yi为目标函数；

Visual:鱼的视野范围；

delta:鱼群的拥挤度；

step:鱼的移动最大步长；

n:当前鱼群觅食行为次数；

try＿number:觅食行为尝试的最大次数；

MAXGEN:最大迭代次数。

鱼群算法是一种高效的智能优化算法，主要有鱼群初始化、迷失行为、聚群行为、追尾行为、随机行为和更新公告板。

1）鱼群初始化。鱼群中的每一个个体均为一组实数，是在给定范围内产生的随机数组，即为原问题的初始解。

2）觅食行为。设人工鱼当前状态为Xi，在其视野范围内随机选择一个状态Xj，在求极大值问题中，Yi＜Yj（极小值问题可与极大值问题互换），则向该方向前进一步；反之，重新随机选择状态Xj，判断是否满足前进条件。反复try＿number次后，若仍不满足前进条件，则随机移动一步。

3）聚群行为。设人工鱼当前状态为Xi，探索当前领域内（即dij＜Visual）的伙伴数目nf及中心位置Xc，如果有Yc／nf＞deltaYi，表明伙伴中心有较多的食物并且不太拥挤，则朝着伙伴的中心位置方向前进一步；否则执行觅食行为。

4）追尾行为。设人工鱼当前状态为Xi，探索当前领域内（即dij＜Visual）的伙伴数目nf及伙伴中Yj为最大的伙伴Xj，如果Yj／nf＞deltaYi，表明伙伴Xj的状态具有较高的食物浓度并且其周围不太拥挤，则朝着伙伴Xj的方向前进一步；否则执行觅食行为。

5）随机行为。在视野中随机选择一个状态，然后向该方向移动，即Xi的下一个位置Xi／next为Xi／next＝Xi＋r·Visual，其中，r是［－1，1］区间的随机数；Visual是人工鱼的视野范围。

6）更新公告板。设置一个公告板，用于记录鱼群内历史最佳鱼的状态Xgbest。各人工鱼每迭代一次都检查自身状态，如果f（Xi）＜f（Xgbest）成立，将Xgbest变为Xi。

3 改进的鱼群算法

基本鱼群算法在解决实际问题时还存在不足，如视野范围的选择是随机的，移动步长也是随机的，虽然能在一定程度上扩大寻优的范围，但会使得算法的收敛速度减慢。

3.1 改进策略

1）改变尺度步长。变步长策略有两种方法:指数式衰减变化策略和分段变化策略。指数式衰减变化策略为step＝step·α，α∈（0，1）为衰减因子，随迭代进程增加减小步长；分段变化策略是依据迭代过程，在不同阶段设置不同的步长，即在算法运行初期，设置较大步长进行计算，增强全局搜索能力，减少计算时间，在算法运行后期，设置较小步长，增强局部搜索能力和提高解的精度，寻找全局最优解。

2）视野范围的自适应变化。采用Visual＝Visual0·n／MAXGEN，其中，n为迭代次数，MAXGEN为迭代总次数，该式是视野随着迭代次数的增加而逐渐变小。在算法运行前期，增大视野范围，增强算法的全局搜索能力，减少计算时间；在算法运行后期，视野范围随公式计算减小，觅食行为和随机行为增强，则更有利于局部搜索，且提高了解的搜索精度，寻找到全局最优解。

3.2 算法步骤

根据上述模型，文中给出改进后的鱼群算法流程如图1所示。

图1 改进鱼群算法流程

具体算法如下:

Step 1:初始化。初始化鱼群数目、步长、视野范围、拥挤度和试探次数；

Step 2:计算目标函数值，找出最小值及其对应的人工鱼个体，并赋给公告板；

Step 3:执行鱼群的追尾行为和聚群行为算子，得到两个不同的解，比较二者的大小，选择较小者；

Step 4:将追尾行为和聚群行为得到的解与公告板比较，若优于公告板的解，则用当前的状态取代公告板的状态；否则转step5；

Step 5:判断是否达到最大的迭代次数:是，则输出最优解；否，则进行视野范围、步长的自适应变化操作，转step3。

4 算例分析

假设某地发生突发事件，现要求从物资储备中心向16个受灾地点紧急运送救援物资，已知物资储备中心有200个单位的应急救援物资，每辆车的装载负荷为40个单位，车载速度为50km／h，物资储备中心和16个受灾地点的坐标以及各受灾点的物资需求量数据见表1，其中，0代表物资储备中心，1～16代表16个受灾点。

表1 储备中心和受灾点坐标及物资需求量

根据模型和算法，设定鱼群最大循环次数Cnumber＝200，可视范围visual＝3，鱼群种群数量为20，拥护因子为5。利用Matlab软件，对算法编程计算，经过200代迭代计算，得最优结果为:车辆数为4，总的配送时间最短且为1.728h以及最优选择路径如表2所示。

表2 最优结果

最优选择路径如图2所示。从图2可看出，4辆应急车辆在应急物资储备中心0点满载应急物资，分别从0点出发，选择四条最优路径0－7－11－16－6－0、0－3－4－5－0、0－14－13－2－12－0和0－10－9－8－15－1－0将应急救援物资配送到受灾点，最后4辆车都再次回到0点；并且利用改进的人工鱼群算法得到总的配送时间最短且为1.728h，这无疑对应急救援工作能否顺利展开具有重大的实际意义。

图2 应急车辆路径选择

5 结束语

由于应急救援过程中的不确定性因素很多，基于传统方法的应急车辆路径选择已不能得到令人满意的结果。因此，文中提出一种改进的鱼群算法来求解应急车辆路径，其结果能达到优化的目的，并为决策者提供选择。由于应急救援环境的复杂性，如何建立更加符合真实环境下的应急车辆最优路径选择模型将是下一步研究的内容。

［1］范玉军，王冬冬，孙明明.改进的人工鱼群算法［J］.重庆师范大学学报:自然科学版，2007，24（3）:23－26.

［2］李妍峰，高自友，李军.基于实时交通信息的城市动态网络车辆路径优化问题［J］.系统工程理论与实践，2013（7）:1813－1819.

［3］肖力.物流配送车辆路径优化问题的仿真研究［J］.鄂州大学学报，2012（2）:5－8.

［4］柳毅，余福茂，俞武扬.同时取送货车辆路径问题的改进人工鱼群算法［J］.杭州电子科技大学学报，2014（3）:34－37.

［5］Dethloff J.Vehicle routing and reverse logistics:the vehicle routing problem with simultaneous delivery and pick up［J］.OR－Spektrum，2001，23（1）:79－96.

［6］Tien J H，Levin S A，Rubenstein D I.Dynamics of fish shoals:identifying key decision rules［J］.Evolutionary E－cology Research，2004，6（4）:555－565.

［7］陈刚，彭永涛.灾难救援应急物资配送问题的研究现状及发展方向［J］.铁道运输与经济，2012（4）:62－66.

［8］马继红，陈浩如.基于改进鱼群算法在管道最优抢修路径的研究［J］.管道技术与设备，2014（1）:4－6.

［9］王培崇，雷凤君，钱旭.改进人工鱼群算法及其收敛性分析［J］.科学技术与工程，2013（3）:616－620.

［10］Yazdani D，Toosi A N，MEYVODJ M R.Fuzzy adaptive artificial fish swarm algorithm.Proc of the 23rd Australasian Joint conference on Artificial Intelligence，2010:334－343.