基于混合遗传算法的应急物资配送路径优化

韩孟宜, 丁俊武， 陈梦覃, 霍珂珣

(扬州大学信息工程学院， 扬州 225127)

近年来，突发事件频繁发生，对国家安定和人民幸福生活都造成了一定的威胁。例如，2003年非典事件，累计病例5 327例，死亡349人，当时造成了社会的高度恐慌；2008年汶川大地震造成69 227人遇难，374 643人受伤，17 923人失踪，经济损失高达8 451亿元；2010年玉树地震遇难约 2 700 人，失踪 280 人，经济损失8 000 多亿元。突发事件发生后，需要采取及时有效的措施进行应急救援，否则将会造成更为严重的后果。应急物资配送作为应急救援中的重要环节之一，优化其配送路径对实现应急物资的高效调配来说至关重要。因此，对应急物资的配送路径进行优化研究具有十分重要的意义。

目前，对应急物资配送路径优化的研究如下：刘娜等[1]研究了疫情期间社区商超的物资配送路径问题，利用自组织映射(self-organizing map, SOM)算法与遗传算法对车辆路径规划模型进行求解，最后得出的结论是遗传算法的结果更优；Li等[2]构建了以配送时间最短、受灾点满意度最大为目标的应急物资配送路径优化模型，采用快速非支配排序遗传算法求解模型；康斌等[3]以最小化最晚车辆服务结束时间、最小化需求未满足率为目标建立了多目标应急救援物资配送路径优化模型，设计优先邻点交叉算子改进遗传算法对模型进行求解；艾云平[4]考虑了各需求客户的硬时间窗要求,以所有配送车辆的路径总距离最短作为优化目标建立了数学模型，设计了基于改进的智能蚁群算法进行求解；张洪福等[5]研究的是行蓄洪区的物资配送路径，建立了以车辆运输时间最短、受灾点时间满意度最大为目标的优化模型，利用改进节约算法进行模型求解；Jiang等[6]建立了以配送时间最短、配送成本最低、物资短缺最少为目标的应急物资调度模型，采用鲁棒优化的方法进行求解。

众多学者对应急物资配送路径优化做了相关研究，但当前研究大多是以路程最短、时间最短、成本最低、需求点满意度最大等为目标建立的数学模型，研究时间窗限制下的应急物资配送路径优化不多；且在求解车辆路径优化模型时用到的大多数启发式算法为节约算法[5,7]、遗传算法[1,3,8-10]、蚁群算法[4,11-12]、粒子群算法[13]等。就遗传算法来说，虽然它具有全局搜索能力强、收敛速度快的优点，但是由于它是随机生成初始解，在一定程度上增加了它的搜索难度，并且它的局部搜索能力不足，在优化较为复杂的问题时容易陷入局部最优。为弥补这些不足，在时间窗约束下，以配送车辆的固定成本、运输成本、违反最大载重量以及受灾点右时间窗的惩罚成本之和最小为目标建立了优化模型，设计混合遗传算法求解，最后借助算例说明模型及算法的有效性。

1 应急物资配送路径优化模型构建

1.1 问题描述

本文研究要解决的应急物资配送路径优化问题有：单个调配中心，多个受灾点，已知调配中心和各受灾点的位置，以及各受灾点的需求量、时间窗、卸货时间等，要求每个受灾点只能由一辆车进行配送，且完成配送任务后需重返配送中心。其目标是优化配送车辆的路径，使得在时间窗约束下总成本最低，应急物资配送路线示意图如图1所示。

图1 应急物资配送路线示意图

受灾点的时间窗为硬时间窗[e,l]，即配送车辆须在各受灾点要求的时间窗内进行卸货[14-16]。若配送车辆提前到达不会产生惩罚成本，不过要等到左时间窗e才能开始卸货，但是不允许超过右时间窗l，一旦超过就会产生相应的惩罚成本Pt。硬时间窗下的惩罚函数图像如图2所示。

图2 硬时间窗下的惩罚函数图像

1.2 模型假设

(1)假设每个受灾点的应急物资需求量不超过运输车辆的最大载重量，且每个受灾点仅能被一辆车服务。

(2)假设运输车辆的初始位置为各调配中心，且完成配送任务后需重返调配中心。

(3)假设调配中心的应急生活物资数量足以满足各受灾点的需求。

(4)假设运输车辆为同一类车型，具有相同的载重量。

1.3 符号说明

gi：受灾点i的应急物资需求量；

dij：受灾点i到受灾点j的距离；

tij：车辆从受灾点i到受灾点j的运输时间；

si：受灾点i卸货所用的时间；

v：车辆运输的速度；

c1：车辆的固定使用费用；

c2：车辆每公里的运输费用；

ti：车辆到达受灾点i的时间；

ei：受灾点i的左时间窗；

li：受灾点i的右时间窗；

P1：配送车辆在路径中超载的单位惩罚成本；

P2：配送车辆违反受灾点右时间窗限制的单位惩罚成本；

f：应急物资配送过程中产生的总成本，由f1、f2、f3、f4四部分组成；

Q：车辆的最大载重量。

决策变量：

1.4 模型建立

配送车辆的固定成本：

(1)

配送车辆的运输成本：

(2)

违反配送车辆最大载重量的惩罚成本：

(3)

违反受灾点右时间窗的惩罚成本：

(4)

目标函数：

minf=f1+f2+f3+f4

(5)

约束条件：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

ti≤li

(13)

(14)

(15)

xijk、yik∈{0,1}

(16)

式(5)是目标函数，表示配送车辆的固定成本、运输成本以及违反最大载重量和受灾点右时间窗的惩罚成本之和最少。

式(6)～(16)是约束条件，式(6)表示每辆车运输的应急物资数量不能超过车的最大载重量；式(7)表示每个受灾点i的应急物资只能由一辆车完成配送任务；式(8)、式(9)表示每个受灾点i都只能在一条配送路径中；式(10)表示所有受灾点的应急物资都有车辆配送；式(11)表示每辆车从配送中心发出且完成任务返回配送中心；式(12)表示每一个受灾点上下均只与一个节点相连；式(13)表示到达受灾点i的时间不能超过受灾点i的右时间窗；式(14)表示到达受灾点j的时间；式(15)表示配送车辆从受灾点i到受灾点j的运输时间；式(16)表示xijk、yik是0-1变量。

2 基于混合遗传算法的模型求解

2.1 算法介绍

2.1.1 节约算法

节约算法(saving algorithm)，又称C-W算法，其核心思想是将运输问题中的两个回路合并成一个回路，使得合并后的运输距离有较大幅度的减小[7]。它的基本思想就是用节约运输距离的方法去寻找最佳的配送路线，使得配送时间和配送成本有所降低，从而实现高效率的配送。利用节约算法求解应急物资配送路径的初始解，在满足各受灾点需求量、时间窗以及车辆最大载重量的约束下，将距离最短的路径作为问题的初始解。

2.1.2 遗传算法

遗传算法(genetic algorithm，GA)是由美国的John Holland教授在1975年首先提出来的，它是通过借鉴生物界的进化规律“适者生存，优胜劣汰”演化而来的一种基于种群的随机化搜索方法[16]。它的基本思想是先将问题的初始解编码到染色体中，然后根据适应度函数计算每个个体的适应度值，接着通过选择操作将适应度高的个体保留到下一代中，通过交叉、变异操作得到多样性的解，不断进行迭代，达到终止条件后输出所求问题的最优解。

2.1.3 大规模邻域搜索算法

大规模领域搜索算法(large neighborhood search)是Shaw[17]提出来的，其算法主要包含破坏操作和修复操作两部分。它的算法原理为：先使用破坏算子从当前解中移除若干点，然后再用修复算子对移除的解进行修复，重新安插到被破坏的解中。

2.2 混合遗传算法设计

为能在一定程度上降低遗传算法的搜索维度，用节约算法生成种群的初始解；针对遗传算法局部搜索能力不足的情况，引入大规模邻域搜索算法中的破坏算子和修复算子，以此增强算法的局部搜索能力。通过将节约算法、遗传算法、大规模邻域搜索算法3种算法的优点相结合，从而构造出了用于解决应急物资配送路径优化的混合遗传算法。混合遗传算法的流程图如图3所示。

图3 混合遗传算法流程图

(1)编码。对染色体进行整数编码，当受灾点数目为N且调配中心最大车辆数为K时，可将染色体的长度记为N+K-1，染色体表示为(1,2,…，N+K-1)。

(2)种群初始化。首先构造问题的初始解。为能在一定程度上降低遗传算法的搜索维度，采用节约算法构造问题的初始解，假设n是标记第几大距离节约值的位置，具体步骤如下。

step1将每个受灾点分配给一辆车，即每个受灾点的应急物资都由单独分配的车辆进行配送。

step2计算把两条路径融合后的距离节约值，将距离节约值由大到小降序排列。

step3按顺序依次判断要融合的两条路径是否满足受灾点的时间窗约束，若满足则将第n大距离节约值的两条路径融合，进行step4；否则令n=n+1，重复step3。

step4更新距离节约值，将距离节约值最大的两条路径融合，判断融合路径上配送车辆运输的应急物资数量是否超过最大载重量，若超过，令n=n+1，进行step5；否则重复step4。

step5将第n大距离节约值的两条路径融合，判断在某条路径上是否还存在只有一个受灾点的情况，若存在则重复step4，否则输出每辆车所经过的受灾点序号。

通过节约算法得到初始配送方案后，开始进行种群的初始化。先将初始解按照编码方式转换为个体，然后再将种群内的所有个体全部赋值为初始解转换的个体。

(3)适应度函数。本文所建模型中的目标函数f是由运输车辆的固定成本、运输成本以及违反最大载重量和受灾点右时间窗的惩罚成本组成，根据题意可知目标函数越小则所得结果越好，为了能够在选择操作中把好的结果保留下来，故在此将适应度函数设置为目标函数的倒数，即令f(x)=1/f。

(4)选择操作。采用轮盘赌选择法进行选择，其基本思想是各个体被选中的概率与适应度值的大小成正比，即将适应度值大的个体选择出来[15]。具体操作过程为：先将群体中每个个体带入适应度函数中，计算得到它们的适应度值f(xi)；然后根据式(17)计算每个个体被遗传到下一代群体中的概率。

(17)

(5)交叉操作。选用顺序交叉(order crossover，OX)的方式进行交叉操作，此交叉方法在面对两个相同父代的情况下仍能产生一定变异效果，对维持群体多样性有一定的作用[18]。先在两个父代个体上随机选择两个交叉位置；然后将交叉位置中间的两个交叉片段提取出来，交叉放在不同父代个体的前面；最后将每个个体中第2 个重复的基因位删掉，便可形成两个子代个体。具体操作流程如图4所示。

图4 OX交叉操作流程

(6)变异操作。在父代个体的染色体上随机选择两个变异位置，然后将两个位置上的基因进行交换，得到子代个体，具体操作流程如图5所示。

图5 变异操作流程

(7)局部搜索操作。使用大规模邻域搜索算法中的破坏算子根据相似性计算公式从当前解中移除一部分受灾点，然后再使用修复算子在满足车辆载重量和受灾点右时间窗约束的情况下，尽可能地将移除的受灾点安插到使目标函数值增加最少的位置。

Remove过程：用σ表示当前解，c表示将被移除的受灾点，s表示被移除的受灾点组成的集合，p表示移除的受灾点数量，σ′表示从σ中移除p个受灾点后剩余的解。先从σ中随机移走一个受灾点到s中，剩下的p-1个受灾点按照下面方法选择：从s中随机选择一个受灾点z，将σ中剩下的受灾点按照与z的相关性由小到大排序，选择出相关性最大的受灾点c，将其从σ中移到s中，重复p-1次，直至剩下的p-1个受灾点都选好了。相关性公式[9]可表示为

(18)

(19)

式中：d′ij为dij标准化后的值，位于区间[0,1]；dij为i、j两个受灾点间的距离；vij表示i、j个受灾点是否在同一条路径中，若是则为0，否则为1。该相关性公式表明：两个受灾点若距离越近，则相关性越大；两个受灾点若在同一条路径上，则相关性越大。

为防止因过度依赖相关性函数致使移出去的受灾点存在不合理的情况，借鉴Shaw[17]的方法，加入随机元素，即在由大到小排好的相关性序列中随机选择受灾点。

index=[Random([0,1])]D×(σ中剩余的受灾点)。

当D=1时，说明受灾点是完全随机选择移除的；当D=+∞时，说明受灾点是完全根据相关性大小选择移除的。

Re-inserting过程：首先根据载重量约束和时间窗约束找到集合s中每个受灾点在σ′中的最佳插入位置，最佳位置即插入后使目标函数值增加最小的那个位置。然后计算s中每个受灾点插到最佳位置后的目标增加值，选择目标增加值最大的受灾点作为第一个插入的点，重复此操作，直至集合s中的元素被全部插入到σ′中。

(8)终止条件。将事先确定的进化代数作为终止条件，即达到最大进化迭代次数N时，停止进化，输出问题的最优解。

3 算例仿真

3.1 算例说明

假设某地有一个调配中心(编号为0)，突发事件发生后，有15个地区(编号为1,2,…,15)受灾情况比较严重，当地应急物资严重不足，急需得到合理的配送。调配中心和受灾点的位置、受灾点的需求量、时间窗以及卸货时间已知，具体的数据如表1所示，混合遗传算法中的参数设置如表2所示。

表1 数据集

表2 混合遗传算法中的参数设置

3.2 算法比较

借助MATLAB R2014a编程软件，结合算例数据，分别用遗传算法和本文混合遗传算法对所建的模型进行求解，求解结果如下所述。

用遗传算法优化配送路径时，优化过程如图6所示，最优的配送方案路线如图7所示。

图6 遗传算法的优化过程

图7 基于遗传算法的最优配送路线

用设计的混合遗传算法优化配送路径时，首先由节约算法求解得到的初始配送方案路线如图8所示；随后的优化过程如图9所示；最终得到的最优配送方案路线如图10所示。

图8 基于节约算法的初始配送路线

图9 混合遗传算法的优化过程

图10 基于混合遗传算法的最优配送路线

遗传算法和混合遗传算法仿真结果对比如表3所示。

表3 仿真结果对比

3.3 结果分析

通过对比遗传算法和混合遗传算法优化的过程可知，用节约算法、遗传算法、大规模邻域搜索算法结合设计出的混合遗传算法在进化到11代时即可达到最优解，而遗传算法在进化到85代才达到最优解。通过对比遗传算法与混合遗传算法优化的结果可知，混合遗传算法无论是在用车数量上、运输距离上，还是耗费成本上都比遗传算法优化的结果好。由此可见，本文中设计的混合遗传算法在优化过程和优化结果上都具有一定的优越性。

4 结论

针对突发事件下应急物资配送路径规划问题进行研究，在满足各受灾点需求的前提下，以配送车辆的固定成本、运输成本、违反最大载重量以及受灾点右时间窗的惩罚成本之和最小为优化目标，构建了时间窗约束下的应急物资配送路径规划模型，并设计了混合遗传算法对模型进行求解，最后进行了算例仿真。借助MATLAB软件分别用遗传算法和本文混合遗传算法对模型进行求解，并对两者的结果进行了对比。

(1)用节约算法、遗传算法 、大规模邻域搜索算法设计出来的混合遗传算法不仅求解结果更优，而且在进化过程中能更早地达到最优解。

(2)构建的应急物资配送路径规划模型具有通用性且本文中设计的混合遗传算法在求解模型时具有高效性，可为解决应急物资配送路径规划问题提供科学的决策依据。

在对应急物资的配送路径进行规划时，是在各受灾点需求确定的情况下得出的配送路线。而在现实生活中，受灾点的需求受突发事件种类的影响可能是不确定的、动态变化的，以及配送车辆在运输过程中的交通条件也可能存在极大的不确定性，这些因素都将会影响应急物资配送路径优化的结果。因此，考虑更多、更复杂影响因素的应急物资配送路径优化问题将是一个拓展研究方向。