遗传-蚁群算法在灾后应急物资路径规划问题中的应用研究

王 帅 蒋华伟

1(中国地震局地球物理勘探中心综合地球物理研究室 河南 郑州 450002)2(河南工业大学信息科学与工程学院 河南 郑州 450001)

0 引 言

干旱、洪涝、地震、台风等重大自然灾害的发生严重影响社会经济发展和人民生命财产安全，开展灾后应急物资运输的路径优化工作是值得研究的重要课题。如国家在应对青海玉树地震和汶川大地震等应急物资调度工作上做到了及时供应，但在应急物资路径规划方面仍显薄弱。因此依靠现代化信息科学技术提升应急物资调拨效率，创建合理、高效的应急粮食调拨车辆路径优化系统已刻不容缓。

对于车辆路径规划问题，国内外专家学者做了很多研究。对应急物资车辆路径规划的研究主要体现在如下几个方面：Rathi等[1]提出了LP模型，主要用于解决应急车辆参加救援时的指派问题；Equi等[2]对在应急物流运送中货物的组合运输与应急车辆的调度问题进行了研究。文献[3-4]借助网络可靠性方法同蚁群算法相结合的思想，对带有时间窗限制的物流车辆路径问题进行了研究。通过算法的结合与改进，他们的研究方法可以规划出满足供应需求的最佳行驶路径。但综合分析，尚存在所得结果易陷入局部最优；目前仅对多个救援点组合优化支援单个受灾点做了大量研究；没有将受灾点的具体位置、需求紧急程度、实时路况等考虑进去。研究所涉及的内容仍有局限性。

本文对应急物资调拨问题的研究多集中在如下方面：(1) 应急物资调拨多救援点组合优化研究。对多个物资需求点的应急调度问题进行分析，结合实际情况给出了相应的约束条件，建立了“应急开始最早，救援点最少”的多目标应急物资调度数学模型，初步解决了应急物资调度中的路径规划问题。(2) 应急物资调拨路径优化研究。围绕应急物资调拨车辆路径优化问题开展研究，考虑实时路况参数的情况下，把蚁群算法和遗传算法结合起来，构建包含时间与成本等要素在内的多目标数学规划模型。

1 路径优化模型建立

1.1 假设条件

(1) 每一个受灾点只能被访问一次，每一辆车只能走一条路线。

(2) 每一个受灾点均有最晚到达时间限制，物资需在约定的时间点前送到。

(3) 各个节点之间假设都能连通，各个路段根据路径的好坏有一个估计值，估计值越低，路越难走车速越慢。

(4) 假设应急物资配送点和受灾点间的距离以及受灾点相互之间的距离为已知量。

(5) 每辆车的载重量大于或等于此辆车所遍历的所有受灾点所需要的物资总量。

1.2 模型建立

已知1.1节假设条件，定义下面的变量：

M为物资运输车辆集合，M={k,k=1,2,…,m}。

V为应急物资配送点和各个受灾点的集合，V={i,i=0,1,…,n},当i=0时在物资配送中心位置。

依据上述相应条件，建立以下模型：

目标函数：

minZ=(Z1,Z2)

(1)

(2)

式中：tij为运输车从受灾点i运送到点j所需花费的时间。

(3)

式中：fij为运输车从受灾点i运送到点j所需的费用。

约束条件：

(4)

式中：qi为受灾点i所需物资总量，i∈V;Qk为运输车所载物资量，Qk≥max{qi,i∈V}。

RTi≤LTii=1,2,…,n

(5)

式中：RTi为运送车抵达受灾点i的时间；LTi为运送车辆最晚到达点i的时间。

tij=dij/αijv

(6)

式中：dij为受灾点i和j间的距离；v为车的平均速度；αij为路况参数，0≤αij≤1，值越小路况越差。

fij=dijαij/c

(7)

式中：c为运输车每行驶单位距离所需的费用。

(8)

(9)

(10)

式中：|S|为包括物资配送中心和受灾点的所有点的数量。

上述模型所引出的数学表达式含义如下：

式(1)是总目标函数，也就是在满足应急时间最短的情况下兼顾运送成本；

式(2)是主要目标函数，即是在整个应急过程中所花费的时间最少；

式(3)是次要目标函数，即是在整个应急过程中所需费用最低；

式(4)是每辆车所遍历的受灾点所需的物资总量不大于该车的承重量；

式(5)运输车抵达受灾点的时间不得超过所允许的最晚时间限制；

式(6)在考虑路况系数的影响下，运输车从受灾点i到点j所需时间；

式(7)在考虑路况系数的影响下，运输车从受灾点i到点j所需费用；

式(8)确保每个受灾节点被每辆运输车遍历一次；

式(9)、式(10)为了保证每辆运输车从物资配送中心把物资配发到该辆车被安排的受灾点后，返回到物资配送中心。

在应急物资调拨路径规划问题上，“应急”即时间观念非常重要，只有所需物资在第一时间送达到灾区，才能真正体现出车辆路径优化的意义。若把各个受灾点和物资物流配送中点均看成应急车辆遍历的节点，假定运输路线上任意一个节点i是邻近节点j的上一个物资运达点，运输车抵达节点i的时间是RTi，抵达受灾点j的时间是RTj，有关于时间的限制函数：

(11)

式中：UTi为运送车在受灾点i卸车所花费的时间。

在诸多转化问题上，最常用的一种办法即是线性加权法。把上述用于应急物资调拨车辆路径优化方案的多目标问题转化为单目标问题的函数如下所示：

(12)

假设每个受灾点对物资的紧急需求程度一样，则把式(6)、式(7)代入式(12)，目标函数为：

(13)

式中：W1和W2是权值系数，指每个目标函数在数学模型中的权衡比重，它的具体参数设置可以依据实时应急物资车辆路径调拨过程状况来确定。

2 求解遗传-蚁群算法路径优化模型

由于蚁群算法具有容易陷进局部最优、初期的信息素匮乏和求解速度较慢的缺点，而遗传算法具有全局快速搜索能力，缺点是无法对系统的反馈信息充分利用，求解效率偏低[5-6]。把蚁群算法和遗传算法相联合，在求解的初始时刻信息素分布由GA生成，然后采用ACA求得最优解。基本思想[7]是：充分利用各个算法的优点，扬长避短，优势互补，从而达到时间、经济和安全性等效率上的多重提高。

把遗传算法和蚁群算法相融合来求解应急物资调拨车辆路径规划问题的方法是：先利用遗传算法的搜索速度快、搜索的随机性以及全局收敛性生成模型的可行解；然后把它转化成搜寻最优路径的初始时刻的信息素分布；再采用蚁群算法在现有信息素布局的情况下，改进蚁群算法，设计蚂蚁群体的信息素更新策略和转移策略；接着，为了使算法的求解能力提高，引入Lin-Kernighan(LK)[8]局部搜索优化算法。通过建立合适的局部搜索优化算法优化边集，使得求解效率得到提高，从而提高了蚁群算法的寻优能力和收敛速率。

2.1 遗传-蚁群算法中参数的设置

(1) 遗传算法参数的设置 目前遗传算法已非常成熟，在此不作详细陈述。下面列出模型求解当中需要的相关设置与模型求解流程：染色体由编码构造而成，在求解应急车辆路径规划问题时，一般采用相对直观的自然数编码的方式，每条染色体即对应一组可行解；在构造一条新的路径时，在当前的路径当中按顺序插入染色体总基因值(受灾点)，若某个基因插入后导致这条路径上出现车辆到达受灾点的时间无法满足条件，则重新构造路径，重新回到初始状态，直至全部受灾点规划到此路径中。

适应度函数的设计：由于所建立的模型是最小化的组合优化问题，其终极目标为所有车辆所需总费用最少，也即是目标函数取最小值。若某辆车在行驶过程中所花费的总代价最大，则此路径的适应度最小，设每条路径上的花费为f，那么适应度F=1/f。

遗传操作：① 在选择算子上采取对每一个子群体利用顺序选择法,其基本策略是：基于目标函数值大小把群体中的每个个体排序，根据这个排列顺序来进行选择运算，使得排前边的优异个体会有更加多的机会遗传给下一代。确定个体的选择概率，引入赌轮选择法。如此循环几代后，就可以求出模型问题的几种可行解。② 交叉就是将两个父个体里边的部分基因替换，从而形成新个体的过程。③ 针对变异算子采用顺序均匀变异的操作。

(2) 蚁群算法参数的设置 蚁群算法易表现出停滞、早熟的征象，可以引进局部最优搜寻方法，也就是通过弧、边互换，在可行解的多个邻域内适当调整，当进行到无法在邻域内调整时结束。以此逐个调整的方法有效避免绝对的局部最优解，这些经过局部调整的解是为了在以后的信息素初始分布的蚁群算法中使用。目前常用的局部最优搜索策略包括遗传算法、贪心算法、二阶段法以及三阶段法等。经大量研究后表明链式LK算法对旅行商的车辆路径优化问题有更好的实际效果和效率。本文选用LK链式算法，采用以下算法创建CLK(Chained Lin-Kernighan)的参考优化边集COV:

输入：遗传算法建立的初始解，初始化各个弧边的信息素浓度；

输出：CLK的COV。

开始

第一步，初始化

① 首先创建一个弧边集合COV；

② 弧边r→1；

③ 类型Lecjk→LecjkType；

④ 构建模型的近邻边5条弧边集Dn；

(注：以上是在实验中构造的原始初始弧边集)

第二步，循环N次，进行如下操作:

1) 从所有优化的环路中随机选择一条s；

2) 计算CLK(r,LeckType,Dn,s)从而得出s′(s′是一条优化之后的路径)；

3) 把s′里面全部弧边并入到COV；

第三步，返回COV；

结束

2.2 遗传-蚁群算法的实现过程

遗传-蚁群算法的实现流程如图1所示。

图1 求解模型的遗传-蚁群算法流程图

3 遗传、蚁群及遗传-蚁群算法中路径优化对比分析

3.1 路径优化结果对比分析

把文中提到的蚁群算法跟遗传算法结合起来求解由Solomon构建的一些带硬时间窗问题的测试数据模型[9]。针对不同数量的受灾需求点P1问题，把运输车辆的限载量设置为30，单位时间长度为1，响应时间为95。实验参数设置如下：蚁群算法中ρ=0.2，β=1，α=1，NC=4 000;遗传算法中pm=0.1,pc=0.9,N=100,MAXGEN=200。每一种状况下测10次，选择这10次中的最好解。分别选用遗传-蚁群算法、基本ACA、GA对标准数据集来测试，表1中约定全部运输车载重量相同，表2中约定更改运输车的载重量。

表1 三种算法的最好结果对照

表2 更改载重量后三种算法的最好成效对照

通过以上实验表明，基本蚁群算法和遗传算法所得出的最佳路径没有本文所采用的遗传-蚁群算法的最佳路径短，说明遗传-蚁群算法能更好地解决VRPTW问题。

3.2 LK优化算法和信息素更新策略对遗传-蚁群算法性能的影响分析

针对P1中的20个物资需求点，分开用三种方式来测试，其中参数的设置同3.1节一样，三种算法各运行100次，不同的测试方法对三种算法的性能的变动影响如表3所示。表3中方法A不使用信息更新策略且不用LK链式算法优化处理；方法B不用LK链式算法优化处理但使用信息素更新策略；方法C是既使用信息更新策略，又使用LK链式算法优化处理。

表3 不同处理方式对相应算法的变化影响

从表3得出，采用遗传-蚁群算法的同时，对可行解和蚁群遍历的路径进行LK链式算法优化处理得到的结果性能最好，而只使用蚁群算法或者是单单使用信息素更新策略均无法让算法得出最好的解。

4 仿真实验

把遗传-蚁群算法用来求解应急物资调拨路径规划中的数学模型，依据模型所需的条件，从众多数据中选择出一组比较贴近实际情况的来分析。假定某个地点出现突发事件急需物资支援，包含1个应急物资分发站点与8个受灾点，且假设应急物资分发站点表示为0节点。表4指应急物资分发站点和8个受灾点以及各个受灾点之间的真实距离；表5指各个受灾点i(i=1,2,…,8)所需物资数量为qi，UTi为卸物资用时，LTi为允许车辆抵达受灾点的最迟时间；表6指应急物资分发站点和8个受灾点以及各个受灾点之间的路况参数。应急车的匀速行驶速率是60 km/h,所有车辆的承载量均为10 t，单位距离的运输价格c=1.5元/km。途中规定物资必须在规定的时间内送到物资需求点且不得超载，应急物资调拨过程中要求适当合理地安排好整个配送路线，满足车辆行驶的总时间最短且运输产生的费用最少。

表4 实际距离对应表 km

表5 受灾点物资需求情况

表6 路况参数

为了验证遗传-蚁群算法的有效性，采用MATLAB 2012软件进行实验仿真。由于在应急物资运送中时间的紧迫性，把目标函数里的时间、花费的比重系数设置为ω1=0.8,ω2=0.2。蚁群算法设置参数为：ρ=0.5，β=3，α=1，NC=2 000,Q=100;遗传算法参数设置为：pm=0.1,pc=0.9,N=50,MAXGEN=400。当目标函数值取得minZ=679.5时，运输车的最终道路行驶路径规划如表7所示。

表7 运输车辆配送路径

5 结 语

本文依据应急物资调拨路径规划的实际问题，构建了一个考虑应急成本的同时兼顾应急时间等多个目标的数学模型。并且根据当今路径规划算法在应急物资调拨路径规划问题中存在的不足，首先运用遗传算法依据模型需要满足的条件求解出一些优化解，然后再转为蚁群算法中的信息素初始分布，计算得出各个可行解并做优化处理，最终求得问题模型的最优解。通过比较验证了该方法的优越性，同时该方法也可解决单应急点的应急物资路径优化问题。由于遗传-蚁群算法在程序执行中会产生代码冗余，求解速度慢，因此改进算法，使其更加适应应急物资路径规划模型的特点，是下一步的研究方向。