基于离散鲸鱼群算法的物资应急调度研究

蒋华伟 郭 陶 杨 震 赵丽科

(粮食信息处理与控制教育部重点实验室(河南工业大学) 郑州 450001)

(河南工业大学信息科学与工程学院 郑州 450001)

1 引言

自然灾害及重大公共卫生事件的发生会严重威胁人们的生命财产安全，并对社会生产造成不利影响[1]。为最大限度降低灾害带来的损失，就需要研究和构建科学合理的物资(如粮食)应急调度模型，来获取最优路径，减少物资配送时间，以保证灾区救援物资的充足供应，从而为开展及时高效的救援工作提供物资保障。

灾后物资应急调度的本质是多种约束条件下的车辆路径问题(Vehicle Routing Problem, VRP)[2]，即具有多配送中心带时间窗的VRP。作为经典的组合优化问题，VRP已被证明为NP-hard问题[3]，其求解方法主要有精确算法[4,5]和启发式算法[6,7]两类。精确算法针对具体问题建立相应的数学模型，利用数学方法求出问题的最优解，但其计算时间随问题规模的增大呈爆炸式增长，因此只能解决规模相对较小的问题。启发式算法是相对于精确算法提出的，在可接受范围内给出问题的解，相比于精确算法，在处理大规模VRP时，具有更高的鲁棒性、可行性。因此国内外学者主要采用启发式算法对VRP及其变体问题进行研究，如在求解带时间窗VRP时，Marinakis等人[8]采用3种不同的自适应策略优化粒子群算法，分别用于初始解的生成、解的移动以及算法参数的自适应调整，以提高算法的求解性能；此外，Ramachandranpillai等人[9]将改进萤火虫算法与脉冲神经系统结合，使其可以快速地搜索解空间，从而提高算法求解的收敛速度。为求解具有多配送中心VRP，Lahyani等人[10]提出了基于混合自适应大邻域搜索算法，算法结合3种插入、5种移除启发式算法和4个后优化局部搜索过程，来灵活解决多配送中心VRP；另外，胡蓉等人[11]提出结合聚类分解策略的增强蚁群算法，将多配送中心问题分解为多个单配送中心问题，以控制问题的求解规模。求解多目标VRP时，Zhang等人[12]设计了两个多目标局部搜索算法，结合两个算法并采用附加技术增强局部搜索算法，提高算法的求解性能；此外，Long等人[13]结合遗传算法与局部搜索策略，提出一种基于帕累托的进化算法，用于求解多目标规划问题。在求解其他变体问题时，骆剑平等人[14]将改进幂律极值动力学优化引入混合蛙跳算法，以提高算法求解容量约束VRP的性能；李国明等人[15]将禁忌搜索与最近邻算法相结合，并对禁忌长度等进行自适应调整，引入自适应惩罚系数，以提高禁忌搜索算法在求解随机VRP时的寻优能力和鲁棒性；Xiang等人[16]提出基于成对邻近学习的蚁群算法，用于求解动态VRP，采用成对邻近学习方法研究变化前的最优路径，并预测变化后最优路径中客户的局部访问顺序。上述算法在求解VRP及其变体问题时，针对不同问题的特点设计相应的算法进行求解。在解决算法易陷入局部最优这一问题时，主要借助变异操作跳出局部极值，具有很强的随机性，无法保证变异后个体的优劣，并且未充分考虑种群多样性与算法陷入局部极值间的密切关系，仅使用适应度函数选择个体，因而无法在算法迭代周期内维持高种群多样性以最大限度发挥启发式算法的优势。

针对启发式算法存在的缺点，以及实际物资应急调度问题庞大的解空间和整体编解码的复杂性，本文提出一种改进离散鲸鱼群算法(Improved Discrete Whale Swarm Algorithm, IDWSA)，对具有多配送中心带时间窗的物资应急调度问题(Material Emergency Scheduling Problem with Mul- tiple Distribution Centers and Time Windows, MESPMDCTW)进行求解。首先分析问题中各种复杂的约束条件，为其建立严谨的数学模型；其次，为获得高质量的初始种群，提出混合初始化策略生成初始解，即动态模糊聚类(Dynamic Fuzzy Clustering, DFC)与随机生成相结合；然后设计分别以相似配送顺序和相同配送中心为比较项的个体移动规则，采用自适应柯西变异算子对个体进行变异，并提出路径选择策略；此外，构造全局评价函数，用于评价子代个体对种群的贡献度，以避免仅使用适应度函数对个体进行评价时的局限性，使得算法在迭代后期仍可保持高种群多样性；最后在Solomon标准测试集[17]上进行仿真实验，并与其他算法进行对比分析，验证IDWSA的有效性。

2 数学模型

2.1 问题描述

实际物资应急调度中存在多种复杂并相互制约的因素，为了简化模型本文给出以下约束条件：(1)每个受灾点仅能由一个配送中心的一辆车完成配送任务；(2)每辆车所访问的各受灾点的总需求量不可超过该车辆的最大载重；(3)每辆车的行驶距离不可超出车辆最大行驶里程；(4)所有车辆在完成配送任务后需返回其始发配送中心；(5)车辆对其配送受灾点的访问时间不可超过该受灾点的最晚送达时间。

2.2 数学模型

MESPMDCTW问题可由有向图描述，在有向图中顶点表示配送中心及受灾点，有向边表示车辆的可行驶路径，如图1所示。

图1 MESPMDCTW问题的有向图表示

假设该问题的配送中心集合D= {d1,d2,···,dm}；每个配送中心拥有vi辆车，其中i表示第i个配送中心，每辆车的最大载重为Q；受灾点集合R={r1,r2,··,rn}，每个受灾点的物资需求量为qj(j=1,2,···,n)。

根据所述，本文构建MESPMDCTW问题的数学模型如下：

(1)目标函数

MESPMDCTW问题的目标是使总运输成本最低和使用的车辆数目最少，其中总运输成本最低可以表示为总运输路径最短、总服务时间最小等，车辆数目最少可使用车辆费用最小化表示。该目标函数用于衡量所生成车辆路径的优劣程度，目标函数值越大表明采用该路径对各受灾点进行物资配送时所耗费的代价越大。

由于各受灾点对物资配送时间具有一定限制，当车辆提前或者延时到达时，要对该车辆进行惩罚，即增加其成本。其中ti表示车辆到达受灾点i的实际时间，ETi，LTi分别表示受灾点i的最早和最晚访问时间；a，b分别表示车辆提前到达和延时到达的惩罚系数，由于不允许延时到达，所以b为一个很大的正数。

式(4)表示每个受灾点只能由一个配送中心的一辆车访问，式(5)表示第t个配送中心服务的受灾点的物资总需求量，式(6)表示访问受灾点j的车辆k流入流出的平衡条件。

3 基本WSA

鲸鱼群算法(Whale Swarm Algorithm, WSA)是2017年由Zeng等人[18]基于群体智能提出的一种新元启发式算法，经大量实验证明，与遗传算法(Genetic Algorithm, GA)、差分进化算法(Differential Evolution Algorithm, DEA)等综合对比，WSA的求解性能更优。其基本思想如下：首先在定义域内随机生成一组解作为初始种群，种群中每条鲸鱼代表解空间中的一个候选解；然后根据种群中鲸鱼的适应度值和位置，依次为每条鲸鱼搜索其“更优且最近”目标鲸鱼，即周围适应度更优的鲸鱼中距离其最近的鲸鱼；最后每条鲸鱼均以其目标鲸鱼为导向以某种方式进行移动，从而产生新一代种群，其向目标鲸鱼移动的方式如式(7)。

由式(7)可知，当鲸鱼X与其“更优且最近”鲸鱼Y之间的距离很近时，鲸鱼X会积极地向鲸鱼Y随机移动；反之，鲸鱼X会消极地向鲸鱼Y随机移动。

4 IDWSA算法

WSA主要适用于求解连续性问题，而MESPMDCTW属于离散问题，无法直接使用它对问题进行求解，因此本文对基本WSA进行优化，主要改进包括：(1)设计新的鲸鱼个体编解码方式，并提出相应的个体间距离计算方式；(2)为提高初始种群的质量及其多样性提出混合初始化策略；(3)提出自适应柯西变异算子，用于更新种群中无引导个体的个体；(4)设计路径选择策略用于个体中各受灾点的重新规划；(5)提出以相似配送顺序和相同配送中心为比较项的两种个体移动规则；(6)构造全局评价函数衡量个体对种群的贡献度用于选择个体组成子代种群。

IDWSA算法的完整步骤如下：

(1)采用混合初始化策略对种群进行初始化得到大小为n的初始种群pop；

(2)采用式(14)计算种群中个体的适应度值，并从中选择适应度值最大的个体作为当前种群的最优个体，记为best。

(3)寻找种群中每个个体的“更优且最近”个体Y，对于个体X，若Y存在，则分别根据以相似配送顺序和相同配送中心为比较项的移动规则对X进行移动，获得两个子代个体；若Y不存在，则对X分别进行两次自适应柯西变异，获得两个子代个体；对种群中所有个体操作后，获得大小为2n的子代种群new_pop；

(4)分别采用式(14)和式(16)计算子代种群new_pop中每个个体的适应度值和贡献度，从中选择适应度值最大的个体记为new_best并与种群pop中的best作比较，保留适应度值大的个体记为best，然后根据个体的贡献度，从new_pop中选择贡献度最大的前n–1个个体与个体best组成子代种群pop。

(5)判断是否满足终止条件，若不满足则返回步骤(2)，反之则进行步骤(6)。

(6)获得最终种群pop，从中选择适应度值最大的个体作为问题的最终解。

4.1 个体编解码及距离计算方式

MESPMDCTW问题中每个受灾点可以由任意配送中心的任意车辆配送，且其在车辆中的配送顺序是随机的，因此该问题具有庞大的解空间，为了减小搜索空间，提高算法的搜索效率，本文提出3层编码方式，包括配送中心编码(Distribution Coding, DC)、车辆编码(Vehicle Coding, VC)和顺序编码(Sequential Coding, SC)，如图2所示。其中，DC值为对应受灾点所属配送中心，VC值为与DC对应的受灾点的车辆号，SC为与VC段对应的该受灾点在车辆中的配送顺序。

解码时，首先由DC确定受灾点所属配送中心，然后由VC确定同一配送中心下各受灾点的配送车辆，最后根据SC确定车辆访问各受灾点的顺序。图2中该示例表示受灾点1，2，4，6，7由配送中心1的两辆车配送，第1辆车访问顺序为1，6，7，第2辆车访问顺序为4，2；受灾点3，5，8，9由配送中心2的两辆车配送，第1辆车访问顺序为3，8，第2辆车访问顺序为9，5。

图2 3层编码示例

由于基本WSA中的距离公式仅适用于求解连续性问题，而不能直接用于求解离散问题，因此根据MESPMDCTW问题的特点及本文设计的3层编码方式，提出一种计算鲸鱼个体间相对距离的方法，如式(8)。

4.2 混合初始化策略

高质量的初始种群不仅能加快算法的收敛速度，而且可产生质量更优的最终解。目前，对种群进行初始化的方法有全局最小化处理时间规则[19]、MinEnd启发式规则[20]、全局搜索和局部搜索方法[21]等。但这些种群初始化方法均是基于车间调度问题提出的，并不适用于本文问题。因此为提高初始种群的质量并保持其多样性，防止种群在迭代中过早丧失多样性而陷入局部极值，根据MESPMDCTW问题的特点，本文提出混合初始化策略，即结合DFC和随机生成方法，按照一定比例生成初始种群，如图3所示。

图3中，初始种群中35%的个体由DFC算法生成，65%的个体随机生成。在随机生成个体时，首先生成一个两倍大的临时种群，然后根据适应度函数计算临时种群中个体的适应度值，选择适应度值最大的前12.5%的个体组成随机生成部分25%的个体，最后从剩余87.5%的个体中随机选择个体作为随机生成部分40%的个体。

图3 混合初始化策略

DFC主要根据各受灾点位置、访问时间窗及服务时间，进行相似性分析，使同一类别的受灾点距离最近且各受灾点访问时间重叠最小，以此将所有受灾点划分为与配送中心数相同的几类。此外，为防止各配送中心所分配受灾点数极度不均匀导致整体配送效率降低，本文在对各受灾点进行聚类后，对形成的受灾点集合进行均衡化处理，使得每类受灾点数大致相同，即当某一类受灾点数较多时，根据式(9)选择部分受灾点将其移向数目相对较少的受灾点集合，循环移动直至达到各受灾点集合大小均衡。

4.3 自适应柯西变异算子

WSA中个体的优化是以其“更优且最近”个体为引导的，但种群中存在某些不具有引导个体的个体，为了对它们进行更新，根据式(12)的柯西变异算子，本文改进提出了式(13)所示的自适应柯西变异算子。

其中，xij为个体i的第j维位置，n为种群大小，C是由t=1的柯西分布函数产生的随机数，[xmin,xmax]是各受灾点的编号区间。

WSA中个体的运动以其“更优且最近”个体为引导，随着个体的不断移动，种群中个体不断收敛。在算法迭代前期，个体位置分散，种群平均位置较大，随着个体不断地向最优解方向移动，种群平均位置逐渐变小，算法逐渐收敛，因此种群平均位置变化与算法收敛特性是一致的，采用种群平均位置作为控制变异步长的参数有利于提高算法在迭代前期的搜索能力，并能在后期加快算法的收敛速度。

4.4 路径选择策略

鲸鱼个体向其“更优且最近”个体移动时，为了在其引导个体周围进行细致的搜索，以最大概率寻找区域内最优个体，本文提出路径选择策略，使个体根据该策略向其引导个体移动，其基本思想如表1。首先根据引导个体即“更优且最近”个体确定配送中心及各受灾点之间的路径权值矩阵W，若节点相邻则将两节点之间的路径权值置为1，反之则置0；根据当前已生成路径的最后一个节点，从未被访问的受灾点集合S中选择与最后一个节点相连权值最大的受灾点，作为下一个要访问的受灾点，以此循环直至未被访问的受灾点集合S为空。

表1 路径选择策略

4.5 个体移动策略

IDWSA中，鲸鱼个体向其“更优且最近”个体移动，采用适应度函数式(14)衡量其质量。该适应度函数是基于MESPMD CTW的目标函数式(1)构建的，主要有3个影响因素，分别为个体X所表示的路径总距离、X所使用的总车辆数以及X中车辆访问所有受灾点的总延迟时间，用于从每代种群中选择质量最优即适应度值最大的个体。

由于MESPMDCTW属于离散问题，基本WSA中的个体移动方式无法使用，因此本文提出以相似配送顺序和相同配送中心为比较项的两种个体移动规则，具体的移动规则如图4所示。

图4 个体移动规则

为了说明个体移动规则，图5给出了基于相似配送顺序的个体移动示例。图5中，个体Y为个体X的引导个体，在个体X和Y中，受灾点3，9都位于对应车辆的第1个访问顺序，受灾点5，6都位于对应车辆的第2个访问顺序，它们具有相同的配送顺序，因此将受灾点3，5，6，9根据其在引导个体Y中的位置复制到新个体Z中；然后随机生成两个整数P1=2和P2=5，将引导个体Y中索引P1和P2之间(不包括P2)的受灾点复制到Z中相应位置；最后将X中剩余受灾点依次复制到Z中。

图5 基于相似配送顺序的个体移动示例

4.6 全局评价函数

对于种群中的个体X，在对其进行1次移动后会产生2个子代个体，则完成1轮搜索后，种群规模将变成原来的两倍。由于个体是向其“更优且最近”个体移动的，当采用适应度函数选择个体时，随着迭代次数增加，个体之间距离逐渐缩小，使个体逐渐聚集在某一区域，种群多样性降低，从而使算法陷入局部极值，难以求出问题最优解。因此为了维持种群多样性，使算法在进行迭代求解时可以在问题的较大解空间上进行搜索，本文基于个体的适应度值构造了如式(16)所示的全局评价函数，用于衡量个体对整个种群的贡献程度，从而在算法迭代期间对个体进行选择以组成新的子代种群。

全局评价函数涉及子代个体、父代个体及整个种群的适应度值，在计算个体x对种群的贡献度时，综合考虑其父代个体在父代种群中的影响程度、个体x在子代种群中的优劣程度以及父代个体向其引导个体移动生成个体x时的优化程度。根据贡献度选择个体时，由于不仅考虑当前个体x的适应度值，同时考虑其父代个体所产生的影响，使得适应度值大的个体其贡献度不一定大，因此对于适应度值较小但可能位于最优解区域的个体x仍有机会被选择，从而扩大算法的搜索空间。采用全局评价函数选择个体，根据个体的贡献度在每次迭代时对个体进行选择，使生成的子代种群中个体间具有较大的差异性，即种群个体分布在问题解空间的较大区域，从而不会使算法过早陷入局部最优，且每次迭代中都会保留当前种群中适应度值最大的个体，因此可以在最大限度维持种群多样性的情况下求得问题的最好解。

5 实验结果与分析

为验证IDWSA求解MESPMDCTW的有效性，本文在Solomon标准数据集上进行仿真实验，该数据集主要分为6类：C1，C2，R1，R2，RC1和RC2，共56个测试集。其中C类是聚类数据，R类数据是随机分布的，RC类数据则是C类和R类的混合数据。由于本文问题涉及多配送中心这一约束条件，因此本文选取随机分布的R类测试集中的R101进行仿真实验，并在上述数据集中添加3个配送中心，其余数据保持不变，添加的配送中心位置信息如表2。

表2 数据集配送中心信息

本文所有实验均使用python 3.7语言编写，在pyCharm上编译，并在Intel(R) Core(TM) i5-8500T CPU @ 2.10GHz 2.11 GHz Windows 10操作系统上运行。为了衡量算法的性能，文中使用了多个评价指标，其含义如表3所示。

表3 评价指标及含义

5.1 参数选取

采用IDWSA对问题求解时，参数的选取对算法性能具有一定影响，本文所提出的IDWSA的参数主要有：种群大小和算法迭代次数。为最大限度发挥IDWSA的优势，需要对算法参数进行分析，以选取最优参数。为此本文分别在种群大小为20，30，40和迭代次数为10，15，20，25，30，35时进行仿真实验，每组实验分别进行20次，其结果如表4，图6，7所示。

理论上，算法所求问题最好解的质量应该与种群规模和迭代次数呈严格正相关，但由于WSA具有不稳定性，在同一实验条件下对问题进行多次求解时，其所求解的质量具有一定差别，这一问题从表4也可看出。此外由图6可以看出，随着种群规模增加，IDWSA所求最好解的距离逐渐减小，但其降低的幅度较小；同时随着迭代次数增加，算法所求最好解的质量有所增加，但两者之间不具有严格的正相关性。

表4 不同参数下算法所求解的质量

此外，从图7可以看出，随着迭代次数增加，不同种群大小下算法的运算时间都呈明显递增趋势。结合图6和图7可知，不同种群大小下所求解的质量差异较小，但在相同迭代次数下，其运算时间相差较大，且随着迭代次数增加，算法的运算时间大幅度增长。在种群大小为20和迭代次数为30时，算法平均运算时间处于46.79 s左右，在可接受范围内可求出问题最好解，因而在进行后续实验时，本文选择种群大小20、迭代次数30作为最优参数。

图6 不同种群规模和不同迭代次数下所求最好解

图7 不同迭代次数和不同种群规模下的求解时间

5.2 混合初始化策略有效性分析

初始解的质量对后续问题的求解至关重要，为验证本文所提混合初始化策略的有效性，本文构建了式(17)用于衡量算法迭代过程中种群的多样性。

其中，i，j表示种群中第i和第j个个体，dij表示个体i与j之间的距离，D表示种群多样性，其值越大表示种群多样性越好。

分别采用混合初始化策略、DFC与随机生成方式生成初始解，结果如表5所示。

由表5可知，采用混合初始化策略生成初始种群，其种群多样性位于仅采用动态模糊聚类和随机生成的初始种群之间，且其初始种群的平均最好解、平均最差解及平均解均优于动态模糊聚类和随机生成；此外，采用混合初始化策略所求问题最终解的平均最好解、平均最差解及平均解也均优于动态模糊聚类和随机生成，由此可表明混合初始化策略有助于算法求得质量更优的可行解。

表5 3种种群初始化方式结果对比

5.3 全局评价函数的有效性

为验证全局评价函数在IDWSA中的有效性，分别使用适应度函数和全局评价函数选择个体并对其种群多样性进行计算分析，结果如图8，表6所示。

从图8可以看出，采用适应度函数选择个体，在迭代5次时，种群多样性就已大幅度降低，表明种群中个体在迭代初期便快速聚集在某一较小区域，且在迭代过程中种群多样性一直降低，由此可知采用适应度函数选择个体时算法易过早陷入局部最优，从而难以求出全局最优解。采用全局评价函数选择个体，与适应度函数相比，在迭代5次时，其种群多样性降低幅度较小，且在迭代后期种群多样性逐渐趋于稳定即算法逐渐收敛时，其种群多样性仍远高于适应度函数，由此可知采用全局评价函数选择个体时，算法在问题解空间的较大区域内寻找可行解，使算法求得全局最优解的可能性大幅度增加。

图8 不同迭代次数下种群多样性

同时，由表6可知，在运算时间大致相同的情况下，采用全局评价函数所求问题最好解优于采用适应度函数所求的最好解，且其最大偏差和平均偏差均大于适应度函数，表明全局评价函数在维持高种群多样性的同时可搜索到高质量的可行解，由此验证了本文所提全局评价函数的有效性。

表6 两种函数求得可行解

5.4 算法对比分析

为验证IDWSA求解MESPMDCTW的有效性，本文采用IDWSA进行仿真计算，同时使用文献[8]中的多自适应粒子群优化(Multi Adaptive Particle Swarm Optimi- zation, MAPSO)算法、文献[22]中的遗传算法(Genetic Algorithm, GA)、文献[23]中的混合蚁群(Hybrid Ant Colony Optimi- zation, HACO)算法以及文献[24]中的人工蜂群(Artificial Bee Colony, ABC)算法对本文问题进行求解，并将5种算法的计算结果进行对比分析，结果如图9所示。

由图9可知，在20次实验中，IDWSA所求最好解的质量与MAPSO, GA, HACO和ABC相比，具有明显提升，其最好解距离与MAPSO, GA,HACO, ABC相比分别减少了2.25%, 13.4%, 6%,1.46%，且所求平均最好解、平均最差解以及平均解均优于MAPSO, GA, HACO和ABC，由此可以看出IDWSA在求解物资应急调度问题时可以缩短车辆行驶的总距离，从而减少运输成本和配送时间。此外，从图9还可以看出，IDWSA所求解的平均偏差与最大偏差均大于MAPSO, GA, HACO和ABC，这表明IDWSA所求最好解与平均解以及最差解之间的差距较大，种群在迭代后期仍保持较高的个体间差异性，从而提高算法求得全局最优解的概率。

图9 5种算法实验结果对比

在相同实验条件下，IDWSA, MAPSO, GA,HACO和ABC的平均运算时间分别为46.16 s,22.6 s, 3.8 s, 5.43 s和7.7 s。IDWSA的平均运算时间远大于MAPSO, GA, HACO和ABC，其中种群移动更新所用时间为43.52 s，占总运算时间的94.3%，由此可知，父代个体在向其引导个体移动时，为获得高质量的子代个体，在引导个体周围进行细致的搜索，因此耗费了大量时间，这也是后续研究中需要解决的问题。

6 结论

本文针对物资应急调度背景下的MESPMDCTW问题，提出了一种改进离散鲸鱼群算法(IDWSA)。综合考虑了影响算法性能的可能因素，分别从种群初始化方式、鲸鱼子代个体生成方式及个体选择方式3个方面改进鲸鱼群算法，结果表明，本文研究的IDWSA可以对车辆行驶路径进行合理规划，缩短车辆行驶总距离，减少物资配送时间，从而有效解决物资应急调度问题。

通过在Solomon标准测试集上进行仿真计算，结论如下：(1)根据不同种群规模和迭代次数下所求解的质量与运算时间，选取种群大小20、迭代次数30作为算法的最优参数。(2)混合初始化策略所生成初始种群的多样性介于动态模糊聚类和随机生成之间，且初始种群和其所求问题最终解的平均最好解、平均最差解及平均解均优于二者，验证了混合初始化策略的有效性。(3)采用全局评价函数选择个体，所生成子代种群的多样性降低幅度较小，且在迭代后期其种群多样性仍高于适应度函数，表明全局评价函数可有效维持种群多样性。(4)与MAPSO, GA, HACO和ABC相比，IDWSA所求问题最好解的距离分别减少了2.25%, 13.4%, 6%,1.46%，并且可在一定程度上降低所求解为局部最优解的概率。