求解铁路物流配送中心选址问题的改进灰狼优化算法

郝芃斐，池 瑞，屈志坚，涂宏斌，池学鑫，张地友

（华东交通大学电气与自动化工程学院，南昌 330013）

0 引言

近年来，市场各种类型的物流形式都在不断地扩大着其服务的范围，争取实现物流中心的最大辐射范围和最佳利用率。铁路物流配送中心作为物流体系的重要基础设施，它具有速度快、费用低、运量大、连续性好的优点，在交通和物流业中发挥重要作用。铁路物流中心的建设对提升铁路货物运输服务品质、提供铁路物流可持续发展的基础设施具有重要意义［1］。

国内学者对于物流选址的问题进行了大量的研究分析。传统的求解方法主要有三种，分别是分支定界法、重心法与拉格朗日松弛法［2］，其中，分支定界法常用来解决小规模选址问题；重心法主要用于求解单一物流配送中心选址问题；拉格朗日松弛法则是可以求取中等规模问题的次优解。由于铁路物流配送中心选址模型是带有复杂约束的非线性模型，属于典型的NP-hard 问题［3］，而传统的群智能算法，像基本灰狼优化算法（Grey Wolf Optimizer，GWO）在迭代后期易陷于局部最优并且收敛精度不高［4］，无法很好地解决铁路物流中心选址的问题。目前，很多研究者通过运用一些智能算法与实际选址问题相结合来研究这个问题，如：袁群等［5］通过遗传算法（Genetic Algorithm，GA）和禁忌搜索算法相结合，并用贪婪算法改进基本遗传算法来有效避免早熟及局部最优现象，提高了求解物流选址最优解的效率；李茂林［6］为了解决传统猴群算法全局收敛度低的问题，通过非线性调节因子和lateral 变异策略对算法进行改进，最后将改进后的猴群优化算法用于物流配送中心选址的实际问题中；生力军［7］针对经典粒子群算法在解决物流选址问题时易早熟收敛并且只能得到局部最优解的问题，提出了量子粒子群算法来求取物流配送中心选址的最优解；李小川等［8］将人群搜索算法中的行为意识引入烟花算法，来避免基本烟花算法鲁棒性差的缺陷。尽管上述优化算法可以求得所需解，但单一机制的群智能优化算法无法满足求解具有多个配送点与需求点的铁路物流配送中心位置的需要，因此本文提出一种改进的灰狼优化算法。

基本灰狼优化算法（GWO）是Mirjalili 等［9］提出的一种新调整参数少的群体智能算法，原理简单且易于实现，但容易在迭代后期陷于局部最优，影响收敛速度及精度［10］。因此本文从寻找最佳的铁路物流配送中心位置出发，以求解31 个需求点、6 个配送中心的中等规模铁路物流中心选址为模型，提出一种带有佳点集和差值剔除策略的改进灰狼优化算法（Improved Grey Wolf Optimization，IGWO），最后将改进的灰狼优化算法用于求解中等规模的铁路物流配送中心选址问题上。

1 铁路物流中心选址模型

在铁路物流中心选址问题中，由于铁路物流中心自身的特殊性，一般情况下铁路物流中心为中大规模，运输主要以大宗货物为主，适宜远距离运输，所以铁路物流中心的选择很大程度上决定了铁路物流运输的发展［11］。

1.1 铁路物流中心选址问题模型假设

为了构建适当的模型，提出以下假设：

1）在已有的铁路物流中心所辐射到的服务及配送区域的需求总量上，物流中心自身的负荷工作能力恒满足其配送及服务区域的总需求量。

2）在物流中心所限区域范围内，满足一一对应的服务。3）将铁路物流中心与其配送和服务区域的需求点之间的距离以及产生的费用作为主要考虑因素。

4）在费用计算中加入一个惩罚值，当物流中心与配送点距离大于3 000 km时需要考虑到这个惩罚值。

5）以降低距离产生的费用为目标，通过限定规范营运费用，可有效控制运营成本。

1.2 铁路物流中心选址问题模型构建

基于以上5 点假设，通过具有普遍性和代表性的物流选址模型问题影响因素分析，从M个备用铁路物流配送中心中找出m个物流配送中心向n个需求点进行配送服务，选取并建立了如下物流选址模型［12］。

目标函数：

约束条件：

其中：目标函数W是各铁路物流配送中心到需求点的运费与配送中心所需建设费用之和；N为所有需求点的序号集合；Mi是所有备用配送中心与需求点i之间的距离小于s的集合；s为距离上限；v为运费率；wi为需求点i的需求量；dij为需求点i与其最近铁路物流配送中心j的距离；Cj为铁路物流配送中心的固定成本；p为从备选铁路物流中心选出的物流中心总和数；Yij、hj为0-1变量。

式（1）代表所有铁路物流中心运营成本总和，构成模型的目标函数；式（2）可保证每个配送点与物流中心之间的一一对应关系；式（3）表示只有当备选的物流配送中心被选中才可以提供相应服务；式（4）表示从物流配送中心到需求点距离不超过s；式（5）表示铁路物流配送中心数为p；式（6）表示当决策变量为1 时，表示备选物流配送中心被选中，并由其供应需求点i的需求量，否则为0。

2 标准灰狼优化算法

灰狼是一种以群居生活为主的顶级食肉动物，它们有着严格的社会等级制度［13］。通常每个群体中有5～12 只狼，其中第1 层称为α，是灰狼种群中的最高领导者，负责决策各项事务；第2 层称为β，在整个种群中协助头狼α；第3 层称为δ，主要负责侦察以及狩猎等事务，严格遵守α和β的指令；第4层称为ω，它听从于其他所有阶层的指令。当灰狼在包围猎物的过程中，它们的行为可以表达为：

其中：式（7）表示灰狼自身与猎物的距离；式（8）表示灰狼X在算法第t+1 代时的位置；式（9）、（10）用于计算系数向量A与C；收敛因子a按照式（18）从2～0 线性减少，r1和r2是在0～1 随机产生的向量。

当灰狼发现猎物的位置时，狼群会逐渐包围猎物，第4 层的ω狼会根据α、β、δ灰狼的位置更新位置，数学模型如下：

其中：式（12）、（13）和（14）中的A1、A2、A3由式（9）计算得出；Dα、Dβ、Dδ的定义如式（15）、（16）和（17）所示；C1、C2、C3由式（10）计算得出。

当灰狼终止移动的时候准备开始攻击猎物。随着迭代次数的增加，a的值在2～0线性减小，更新如式（18）所示：

其中Tmax表示最大迭代次数。

3 改进的灰狼算法

在基本的灰狼算法中，初始种群是随机产生的，并且根据式（11）～（14）来进行位置更新，但是每次迭代前后并未进行信息交换。针对以上基本灰狼算法的不足，提出如下改进的灰狼优化算法（IGWO）。

3.1 基于佳点集的种群初始化方法

初始种群在搜索空间内均分布能够使得种群具有更强的多样性，进而有助于提高算法的全局搜索能力。用佳点集（Good Point Set，GPS）理论的取点法代替随机法可以使个体在空间中更加可靠地均匀分布，提高算法稳定性［14］。比起最初灰狼算法随机产生的办法，佳点集初始种群更具有稳定性和遍历性。

佳点集的基本定义与性质为：

1）设Gs是s维欧氏空间中的单位立方体，即x∈Gs，，1 ≤k≤n}。

2）当r=，则说明p就是满足s≤(p-3)2的最小素数，此时对应的r为所求佳点。

3）若Pn的偏差含量满足ϕ(n)=C(r，ε)nε-1，其中r为佳点，Pn(k)称为佳点集，ε是随机产生的任意正数，C(r，ε)是有且只和r、ε有关的常量。

3.2 差值剔除策略

基本GWO在处理一些高维数问题时，在迭代后期收敛速度慢、易陷入局部最优［15］。本文受到布谷鸟搜索（Cuckoo Search）算法的启发，可以通过概率删除方式，根据一定概率Pa剔除GWO中的差解，并产生对应规模的新解的方法。通过在标准灰狼算法完成位置更新后加入差值剔除策略（D-value Elimination Strategy，DES）这一方法来提高算法的寻优能力。

差值以概率Pa剔除后，按如下计算式产生对应规模的新解：

根据式（19）～（20）生成一个新的解替换更新X。差值剔除策略增强了算法的局部寻优能力，有效避免了处理问题时陷于局部最优的情况，增加算法找到最优解的概率。

3.3 IGWO算法步骤

本文提出的IGWO算法步骤如下：

步骤1 设定算法参数。包括种群规模、最大迭代次数、上下界以及维数，令迭代次数的初始值l=0，根据式（9）～（10）在搜索空间中随机生成控制参数。

步骤2 种群初始化。在搜索空间中利用佳点集初始化种群的方法生成最初的初始种群以及对应位置。

步骤3 根据适应度函数对灰狼位置进行更新，计算出每个灰狼个体此时位置的适应值。若灰狼当前的位置优于自身记忆的最优位置，则用当前位置替代它；若目前全局搜索的最优位置优于到当前为止搜寻到的最优位置，就用全局最优的位置替代。

步骤4 将适应度值排列前三位置的灰狼个体记为α、β、δ，它们对应的位置记为Xα、Xβ、Xδ，Xα作为主导的位置。

步骤5 按照式（12）～（14）计算其余灰狼个体与α、β、δ灰狼之间的位置，并且根据式（15）～（17）更新当前其余灰狼个体的位置。

步骤6 对当前最优的灰狼个体α的位置进行式（19）～（20）操作，增加最优位置Xα的局部寻优能力。

步骤7 更新步骤1 中随机产生的参数r、A、C的值，再令l=l+1，返回步骤3循环，直到迭代次数达到最大限制值。

4 数值仿真

为测试本文提出的改进灰狼优化算法（IGWO）的优化效果进行大量的Matlab数值仿真实验，并且与基本GWO进行了比较。选取了10 个测试函数（如表1 所示），两种算法种群规模均取30，最大迭代次数取500。

表1 十个测试函数Tab.1 Ten test functions

4.1 佳点集初始化种群的仿真分析

采用佳点集来改进基本GWO初始种群的方法，有效提高了算法的全局收敛性以及搜索效率。为了更加直观看出利用佳点集初始种群带来的优化性与可行性，选取了在6 个具有代表性的测试函数下，单独加入佳点集初始化种群（GWOGPS），来验证算法的有效性。当测试函数在30 维的情况下，将6 个测试函数Schwefel’s 2.22 函数、Sphere 函数、Zakharov函数、Sum Square 函数、Ackley 函数以及Rastrigin 函数针对适应度值的结果进行实验比对，如图1所示。

通过图1 可以看出，在算法中单独加入佳点集可以有效提高基本GWO的寻优结果，通过在实验中单独加入佳点集来初始化种群，使GWO-GPS 可以很快找到最优结果，但依旧存在对于某些函数的寻优结果并不是特别理想，只在部分迭代次数阶段有效。总之，单独加入佳点集初始化种群可以提高大部分基本GWO 的寻优结果，只对有部分测试函数具有局限性。

图1 GWO与GWO-GPS的寻优结果比较Fig.1 Optimization results comparison of GWO and GWO-GPS

4.2 差值剔除策略的仿真分析

通过典型测试函数寻优实验，发现加入差值剔除策略可以增加局部寻优能力，而且在基本GWO 中，它充分考虑到的是局部寻优，寻找每一次的最优解，通过差值剔除策略的加入形成的GWO-DE 则是在全局寻优能力上有所提升。为了更加直观显示改进算法的有效性，将GWO-DE 在函数30维的情况下，分别对10 个测试函数进行寻优，如图2 选取了其中6 个测试函数的寻优结果。从图2 中可以看出，加入差值剔除策略的GWO-DE 寻优速度更快，求解精度更高，但对于Rastrigin函数寻优效果不明显。

图2 GWO与GWO-DE的寻优结果比较Fig.2 Comparison of optimization results of GWO and GWO-DE

4.3 IGWO仿真分析

为了比较的公平一致性，在实验中基本GWO 和IGWO 采用相同的实验参数和测试环境，可以从表2 的数据看出：IGWO 产生适应值的最优结果（Best）、最差结果（Worst）、平均结果（Mean）和方差结果（St.dev）都优于基本GWO 产生的结果，平均结果相比较说明在一定的迭代次数下IGWO 具有更快的收敛速度；10个函数的方差对比表明，IGWO 产生的方差更小，说明IGWO在每次的优化过程中稳定性和鲁棒性更好。

为了更加直观地反映算法的寻优效果，将基本GWO 与IGWO对6个测试函数的收敛曲线结果进行比对，如图3所示。从图3可以清晰地看出：对6个函数的测试中，无论是从收敛快 慢还是收敛精度上比较，IGWO都比基本GWO有所提高。

图3 GWO和IGWO对6个函数的收敛性能比较Fig.3 Convergence performance comparison of GWO and IGWO for six functions

为了更加直观看出IGWO的寻优性能，图4选取了在单峰函数Sphere 与多峰函数Rastrigin 下，GWO、GWO-GPS、GWODE、IGWO 算法的寻优性能进行对比。通过仿真实验可以看出，加入佳点集的初始化种群算法可以增强种群的遍历性，在迭代前期可能效果不是特别明显，但随着迭代次数增加，GWO-GPS 的寻优性能就显现出来了。再加入差值剔除策略来生成对等规模的新解，GWO-DE提高了收敛速度，可以帮助算法跳出局部最优。可见，IGWO 相比较GWO 更具有优越性，可以考虑把IGWO 运用到解决实际问题中，比如求解铁路物流中心选址的问题上。

图4 函数测试下GWO、GWO-GPS、GWO-DE、IGWO寻优性能对比Fig.4 Optimization performance comparison of GWO，GWO-GPS，GWO-DE，IGWO under function test

5 铁路物流中心物流选址比对

为了验证本文所提IGWO的优化可行性，本文获取31个需要铁路物流配送的城市地理位置信息，选取式（6）为目标函数，建立物流配送中心选址数学模型，并将IGWO与基本粒子群优化（Particle Swarm Optimization，PSO）算法、灰狼优化算法（Grey Wolf Optimizer，GWO）、差分进化（Differential Evolution，DE）算法与遗传算法（GA）的迭代效果进行比对。假设31城市分别需要一个需求点，并从31个需求点中选出6个作为铁路物流配送中心，其中地址的空间位置及需求量如表3所示。

表3 用户的位置与空间需求量Tab.3 Users’locations and space requirement amounts

图5 分别展示了算法GWO 和IGWO 的铁路物流中心选址，图中所显示的物流配送中心即为算法求得的最优解。

图5 两种算法选址结果对比Fig.5 Comparison of location selection results of two algorithms

以图5（a）为例进行说明，配送中心31负责需求点26、27、28、30 的配送任务，配送中心24 负责需求点13、20、25 的配送任务，配送中心18 负责为需求点3、17、21、22 提供服务，配送中心12负责需求点1、11、13、14、15、29的配送服务，配送中心5 为需求点2、4、6、7、16、23 提供配送服务，配送中心10 为需求点8、9 提供配送服务。以此类推，图5（b）展示IGWO 算法的选址方案，其中方框表示配送中心，圆点表示需求点，方框与圆点之间的连线表示某需求点的物资由物流配送中心负责配送。用本文所提改进灰狼优化算法对铁路物流配送中心选址模型进行优化，得出的选址方案为［27，24，18，12，5，9］。

为了验证IGWO在铁路物流选址中的有效性，通过图6对IGWO与其他四种基本智能算法适应度值进行对比。

图6 五种算法迭代效果对比Fig.6 Comparison of iterative effects of five algorithms

从图6 可以看出，在迭代前期IGWO 适应度值高于算法PSO、DE 与GA，随着迭代次数的增加，IGWO 的全局寻优能力进一步增强，搜索与开发能力提高，IGWO 寻得的适应度值优于GWO 与GA。在整个迭代过程中，PSO 与DE 的稳定性更强，最终的寻优结果也略优于IGWO，但PSO 在迭代初期易陷于局部最优。还可以看出，在代数迭代的初期，GWO 最优值更稳定，但随着迭代次数的增加，GWO 陷入了局部最优解，而IGWO 解决了这个问题，它从局部最优中跳出，增强了局部寻优能力，使得数据质量优于GWO。

从表4 可以看出，IGWO 寻优结果相较于GWO 提高了3.2%，IGWO 相较于PSO、DE、GA 运行速度分别提高了39.6%、46.5%、65.9%；IGWO 相较GWO 时间增加了5.6%，因为在GWO 中加入了差值剔除策略会导致再次生成与筛选种群的过程，消耗一定的时间，但寻优结果更加理想。虽然PSO 与DE 的适应度值更小，但它们的运行速度更慢。综上所述，结合适应度值与运行速度整体综合考虑，IGWO 优于大部分经典智能算法，有效减少了选址时间，全局搜索能力强，不易陷于局部最优，因此IGWO 求解铁路物流配送中心选址问题求解得到的选址方案可以为实际的铁路物流选址规划提供一定程度的参考。

表4 5种算法的性能比较Tab.4 Performance comparison of five algorithms

6 结语

针对基本灰狼算法（GWO）求解铁路物流配送中心的问题的局限性，本文提出了一种改进的灰狼优化算法（IGWO）。在GWO基础上引入了佳点集来优化初始种群，使初始种群更加具有遍历性，搜索能力加强。在基本灰狼算法位置更新中加入了差值剔除策略增加扰动因素，加快了收敛速度，有效避免了陷入局部最优，提高了局部寻优能力。

在对10 个标准测试函数的实验仿真表明，本文提出的IGWO 有效提高了优化效率、收敛速度和鲁棒性；然而，IGWO也有自身的局限性，对于某些测试函数实验结果并不理想，可见IGWO 对于部分函数不适合。通过加入IGWO 优化铁路物流选址模型，是对于求解铁路物流中心选址的一种有效补充，可以有效降低运营成本。下一步研究可在模型的选取上进行优化，使IGWO 在物流选址问题或更多工业工程问题中有更深层次的优化性。