基于群智能混合算法的应急物流路径优化研究

吴新胜, 姜婷, 赵梦超, 张萍, 孔令成

(1.安徽经济管理干部学院信息工程系, 合肥230051;2.常州大学信息科学与工程学院, 常州213164；3.中科院合肥物质科学研究院先进制造技术研究所, 合肥230051)

引言

随着经济的发展，自然灾害、突发事故等事件频频发生。我国逐渐建立并健全突发事件应急处理机制，当事件发生后立即采取一系列措施来开展紧急救援工作。应急物流即为针对各种严重突发事件所产生的人员、物资等需求进行的一种特殊的物流活动[1]。但是，由于应急物流规划仍不成熟，物资配送起到的效果还有待改进，如何科学地选择合适的配送路径、合理规划物资储备，确保人民能够及时收到应急物资，保障人民群众的生命财产安全，具有非常重要的研究意义和应用价值[2]。应急物流是在多限制条件、多影响因素的复杂环境中进行决策的系统工程，利用群智能(Swarm Intelligence，简称SI)算法在解决此类问题上能起到传统优化方法所不可比拟的优势。群智能算法可以解决那些因为难以建立有效的形式化模型而用传统优化方法难以有效解决甚至无法解决的问题[3-4]。

应急物流是一种典型的车辆路径问题(VRP问题)[5]。近年来，许多研究人员针对此问题进行了研究，经典人工智能算法(粒子群算法、蚁群算法等)均被应用到解决此类问题中去。例如昝良等人[6]通过设置夸张系数，以及定义“虚拟边”，对蚁群算法进行改进，解决应急路径规划问题中当前位置的邻接访问点有多个目标的问题。周生伟等人[7]提出了一种对遗传算法邻域搜索能力的改进，结合贪婪随机自适应算法，更好地求解物流路径问题，有效降低运输成本。周艳聪等[8]提出改进遗传算法来求解不带时间窗约束的物流车辆路径问题。陈通利等人[9]引入自适应双态进化机制，以及提出随机递归进化方式，解决了粒子群算法容易陷入局部最优的问题，为应急物流问题优化提供有效的技术支撑。Suganthan P N[10]提出了带邻域操作的PSO 模型，克服了PSO 模型在优化搜索后期，随迭代次数增加搜索结果却无明显改进的缺点。黄凯明等[11]将量子进化算法与遗传算法相结合，研究了三层级设施选址及路径规划问题。王道平等[12]利用双层规划法建立了配送中心选址与车辆路径安排的多目标整数规划模型，采用改进的蚁群算法进行了求解。叶勇等[13]采用惩罚函数构建了带时间窗车辆路径问题数学模型，并采用改进的狼群算法进行了求解。刘钊[14]结合已有学者对应急物流系统问题优化的研究，引入人工蜂群算法和粒子群算法对萤火虫位置进行更新优化，调整萤火虫移动机制，提高算法的寻优效率以及准确率。

1群智能算法优化应急物流系统模型

1.1应急物流数学模型建立

建立应急物流模型有助于国家、政府针对突发事件进行高效有序的物流运作[15]，参考文献[16]制定应急物流响应模型如图1所示。应急物流系统运行初期根据人数预估物资总需求，保证需求总量充足，之后结合物流中心现有资源、当前GIS系统以及交通路况，在充分考虑各方面因素的情况下制定合理的配送方案，最后及时进行物流配送，对次配送方案进行应急评估，总结配送方案实施效率并适当调整，得到最佳应急方案。

图1应急物流响应模型

应急物流优化路径问题可以描述为以下数学模型：在某次物资配送过程中，需要在规定的时间内从物流中心将物资配送到各个配送点，在不超过车辆最大限容量以及时间限制等约束条件的情况下，合理规划车辆运输路径方案，达到应急系统配送效果的最优状态[13-14]。应急物流优化模型约束和假设条件如下：

(1) 运输车辆必须从应急物流中心出发，并最后返回应急物流中心。

(2) 整个系统有且仅有一个应急物流中心。

(3) 每个配送点的物资有且仅有一辆车一次配送完成。

(4) 每条配送路线的总需求量必须不超过车载的最大限容量。

满足以上约束条件后，令A={a1,a2,…,an}代表所有配送点集合，a0为应急物流中心，Aij表示ai到aj之间的距离；假设物流中心一共有K辆运输车，每辆车的极限载重均相同为Q，每个配送点的需求量为gi(i=0,1,…,n)；yik为1时表示第k辆车经过i，否则不经过；当车辆从配送点i到j时，记逻辑变量xijk为1，反之记为0；每辆车均由物流中心a0出发，用定值y0k=1表示。通过以上叙述建立应急物流模型。

目标函数为：

(1)

约束条件为：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

由构建的数学模型可知，式(1)目标函数可求得最短的配送路径，约束条件公式(3)和公式(4)表示每个配送点必须有车辆进行配送，且仅有一辆配送车；公式(5)和公式(6)表示任意一辆车经过的地方必须是该车安排的配送点，且不能经过其他车辆的配送点；公式(7)表示每辆运输车从物流中心出发最后又返回到物流中心；公式(8)意在说明每辆车配送路线上的总需求量不能超过该辆车的极限载重。

1.2普通萤火虫算法

萤火虫算法(GSO)是通过模拟萤火虫发光吸引同伴求偶或觅食的一种新型群智能优化算法[17]。该算法能够同时获取多模态函数的多个最优解。在GSO算法求解问题时，萤火虫个体i在搜索空间中随机分布，且初始化均携带相同数量的荧光素，萤火虫发光越亮，说明其所处位置越优，所处位置的目标函数值也越好，在每只萤火虫视域视线范围内即决策域范围[18]，寻找邻域中更亮的萤火虫并向其靠拢，伴随着萤火虫位置以及荧光素的变化，每一次移动都是朝着最亮的位置移动，最后形成多个聚集点，即达到最优。萤火虫优化算法基本流程如下：

(1) 计算第i只萤火虫在t时刻的荧光素值li(t)，该萤火虫所在位置xi(t)对应的目标函数值为J(xi(t))。

li(t)=(1-ρ)li(t-1)+γJ(xi(t))

(9)

(10)

(3) 计算萤火虫i向邻域j移动的概率pij(t)。

(11)

(4) 依据公式(12)更新萤火虫的移动位置。

(12)

(5) 萤火虫感知范围半径根据式(13)进行更新。

β(nt-Ni(t))}}

(13)

式中：参数ρ表示荧光素挥发因子，γ表示荧光素增强因子，ρ,γ∈[0,1]；x表示x的范数；s为萤火虫移动步长；β为感知范围半径更新率；rs为萤火虫最大的感知半径。

1.3混合群智能算法优化

传统的GSO算法在寻找各种全局最优解上虽然具有一些优点，但由于萤火虫的移动过程是整体移动，导致部分萤火虫再移动到新位置后具有了更好的位置，同时另一部分萤火虫从较优的位置移动到了位置较差的地方。当算法处于全局搜索状态，会产生寻优精度低、收敛速度慢、以及陷入局部最优等缺陷，根据传统的GSO算法的这一缺点，本文提出了用人工蜂群和粒子群对萤火虫算法进行混合优化、改进[19]。

(1) 将萤火虫算法中的萤火虫整体向最优点移动改为分散移动，即萤火虫逐维移动[20]。原来移动的流程如图2所示，逐维移动流程图如图3所示。

图2原萤火虫移动流程图

图3萤火虫逐维移动流程图

(2) 优化萤火虫的移动方法。人工蜂群算法是根据蜜蜂飞行模式得到的一种人工智能算法，也是一个启发算法[21]。该算法并不需要提前获取特别的信息，只需以观察形式掌握问题的优劣，通过对每只蜜蜂进行局部寻优，最终在蜂群中找到最优值，作为算法的最优解。蜂群算法的位置更新方法为：

xid(t+1)=xid(t)+γ(xid(t)-xkd(t))

(14)

式中：γ为区间[-1,1]之间的随机数，k≠i。

粒子群算法是由J. Kennedy和R. C. Eberhart等开发的一种新的进化算法，也是一种进化算法，它是从随机解的角度出发，通过迭代寻找最优解，最后通过适应度来评价解的好坏。粒子群算法中粒子位置更新方法为：

vid(t+1)=w*vid(t)+c1*r1[pbestid(t)-xid(t)]+

c2*r2[pbestid(t)-xid(t)]

(15)

xid(t+1)=xid(t)+vid(t+1)

(16)

式中：vid(t)表示粒子i在第d维上的速度；xid(t)表示时间t时粒子的位置；w为惯性系数；c1、c2为加速因子；r1和r2都是相互独立的随机数。

根据人工蜂群算法和粒子群算法与萤火虫算法的对比可知，人工蜂群算法的位置更新公式与萤火虫算法位置更新公式类似，不同的是它不是采用贪婪算法而是忽略萤火虫的发光强度随机选择。该方法其实是基于局部移动的算法，随机性的逐维搜索，这样可以改善GSO本身的算法精度低、收敛速度慢、易陷入局部极值点的缺点。所以本文采用逐维搜索的方式更新萤火虫的位置，具体的算法步骤如下：

(1) 初始化萤火虫算法的基本参数，设置萤火虫初始位置；

(2) 根据公式(9)计算t时刻萤火虫的荧光度，根据公式(11)计算萤火虫选择移动的邻居萤火虫的概率，根据公式(13)计算萤火虫感知半径，并根据公式(14)或(16)更新萤火虫的新位置；

(3) 测试迭代次数有没有达到设置的最大值。若没有达到则继续更新萤火虫的位置，若已经达到最大的迭代次数则停止所有萤火虫的位置更新；

(4) 令t=t+1，重复步骤(3)；

(5) 算法结束。

实验结果表明，该算法可更好地优化全局搜索能力与局部搜索能力，克服基本萤火虫算法的缺点。

2实验结果

实验前设置距离参数和平均交通复杂度参数，具体设置数据见表1和表2。

表1应急物资的出发点Si与应急物资目的地Di的距离(单位:km)

表2应急物资的出发点与应急物资目的地之间的平均交通复杂度(单位:km/h)

根据表1和表2，利用公式(17)可以计算出在没有智能群算法前将应急物资从出发点运输到目的地的时间，结果见表3。

(17)

表3利用常规方法将应急物资从出发点运行至目的地所用时间为(单位:h)

将传统萤火虫算法加入物流运输中在计算应急物资的配送时间，结果见表4。

表4加入传统萤火虫算法后应急物资的运输时间(单位:h)

通过对比传统萤火虫算法与改进后的萤火虫算法来验证后者是否具有更好的缩短物流的时间效果，这里每只萤火虫的更新位置为式(14)和式(16)的平均值，实验结果见表5。

表5采用改进萤火虫算法后应急物资的运输时间(单位:h)

从表5可知，相较于传统萤火虫算法，改进的萤火虫算法显著缩短了物流时间，部分节点降低的幅度超过了50%，特别是对于交通复杂性参数较高的节点效果较为明显，表明本文提出的算法具有较强有效性。

3结束语

通过对应急物流路径优化模型的研究，引入混合智能算法进行路径优化，充分利用人工蜂群和粒子群各自的优势，对萤火虫算法移动更新机制进行改进，避免算法陷入局部最优，大大提高了原萤火虫优化算法的寻优精度以及搜索效率。实验结果表明混合群智能算法在解决应急物流路径规划问题上具有高效性，且比普通单个群智能算法优化有更好的鲁棒性。