基于HICS算法的电力物资配送中心选址研究

王喜平， 郄少媛， 赵 齐

(1. 华北电力大学 经济管理学院，河北 保定 071003； 2. 中国邮政研究院技术应用研究中心，北京 100096)

0 引言

物流系统作为国民经济发展的动脉和基石，被誉为现代经济发展的加速器。配送中心在整个物流系统中起着承上启下的枢纽作用。配送中心的选址直接决定着整个物流系统的成本和效率。电力物资配送中心选址则是电力物流系统规划的基础和核心。目前我国电力系统中普遍存在物资配送点多、配送责任不明确等问题，致使配送成本高、效率低。因此，对电力物资配送中心选址问题进行研究，不仅有助于提高电力物资的利用效率，而且对提高电力企业的整体物流水平、降低配送成本均具有重要的现实意义。

目前关于配送中心选址的研究可以分为两类，一类基于传统的决策理论，如交叉中值法[1]、重心法[2]、熵权法[3]、模糊综合评价法[4]、灰色关联度分析[5]等，通过对指标权重与选址方案的排序得到最佳配送中心；第二类基于人工智能技术对选址规划模型进行人工仿真模拟得到选址的最优解，一般采用的人工智能技术主要有BP人工神经网络算法[6]、改进遗传算法[7]、改进模拟退火算法[8]、改进鱼群算法[9]等。以上研究共同的缺陷在于寻优结果不够理想，探索更为有效的优化算法成为学者努力的方向。

布谷鸟算法(Cuckoo Search Algorithm，CS)作为一种新颖的仿生进化群算法，最早是Yang(2009)提出的，主要依据布谷鸟的巢寄生繁殖机理和lévy分形搜索原理，因其具有参数少、操作性强等优点，自提出后便被广泛用于各种研究领域[10～13]。但原始的布谷鸟算法只能用于求解连续性优化问题，尽管一些学者尝试对此算法进行改进，如李志平等(2016)提出用云模型对布谷鸟算法进行优化[14]；Ouyang(2016)采取离散的CS算法来处理TSP问题[15]；Fateen(2014)使用基于梯度的布谷鸟搜索算法[16]；陈明和张靠社(2016)对布谷鸟搜索算法进行了自适应改进[17]。但就布谷鸟算法搜寻精度方面还需进行系统全面的研究。基于此，本文拟对布谷鸟算法做进一步改进，并以此求解电力物资配送中心选址问题。

1 问题描述与理论假设

配送中心是对物资进行出库作业并负责送货至终端客户，以达到流通周转的物流中心。电力物资配送中心是服务于电力企业，使得电力企业运行所需的生产资料以及维持生产所需的维修物资得到有效周转的物流中心。

目前，我国电力企业物流发展相对不完善，实现既满足库存量最小，又能保证客户需求的目标仍然有很大困难。电力物资配送中心表现出以下特点：(1)各配送中心独立存在，未形成资源共享；(2)配送中心组织结构混乱；(3)配送中心数量多，责任不明确。以上问题表明，电力物资配送中心的设计及选址方面存在着严重的问题。按照当前提倡的物资集约化管理的要求，重新规划物资配送中心是十分必要的。

电力物资配送中心选址问题可以描述为：在n个物资需求点中选择m个物资配送中心，使得选取到的m个配送中心与其他n个物资需求点的运输及存储等的总成本最低。并同时满足以下约束条件：配送中心的物资供应量可以满足物资需求点的需求；一个物资需求点所需要的物资只能由一个配送中心提供；不考虑物资供应上到配送中心的运输费用。据此，电力物资配送中心选址的数学模型可描述如下：

min(cost)=T+S+P=

ρ·(disti,j-D)·δi,j·ui,j)

(1)

s.t.

∀j

(2)

ui,j≤hj,i∈M,j∈N

(3)

(4)

hi∈{0, 1},i∈M

(5)

ui,j∈{0,1},i∈M,j∈N

(6)

M={i|i=1,2,…,m},N={j|j=1,2,…,n}

(7)

式(2)～(7)是约束条件式：式(2)表示j需求点的物资需求仅由唯一物资配送中心供应：式(3)表明每个物资需求点必定有一个物资配送中心为其配送物资；式(4)表示某个物资配送中心选择的物资需求点数量；式(5)～(7)为相关的定义及整数约束。

2 电力物资配送中心选址模型的算法设计

2.1 基本布谷鸟算法(CS)

CS算法是一种模仿布谷鸟寻觅窝巢产蛋行为的启发式智能优化算法，算法的具体步骤如下：

(1)种群的初始化：随机选取n个鸟巢的初始位置，计算n个鸟巢的适应度值，确定初始位置中的最优鸟巢位置，对最优位置保留为寄生巢；

(2)搜寻：搜索每个鸟巢的子代位置，并计算其所在位置的适应度值，进一步比较两代的适应度值，对最优的位置进行保留；该方法在搜寻的过程中采用Lévy飞行模式，飞行运动的每一步包含两个因素控制：首先是飞行的方向，运算中一般选取均匀分布函数；其次是步长，其步长服从Lévy分布，布谷鸟算法中使用了Mantegna进行步长的选择。具体表示为：

(8)

其中，β=k-θ，1<θ<3，α和β都服从正态分布，即

(9)

式中：

(10)

σv=1

(11)

其中，ζ是标准Gamma函数，ζ取1.5，此概率分布的方差和均值都是无界限的。

(12)

(13)

其中，L(θ)：β=k-θ，1<θ<3，步长大小是通过固定的算法实现。

(14)

式中：rand表示随机数。本文的选址问题区别于一般的莱维飞行中的连续飞行，本文引进离散背包问题的计算公式。

(3)决策：通过比较随机数r与发现外来鸟蛋的可能性pa进行决策。若r>pa，则表示鸟蛋会被发现并破坏，应随机改变寄生巢的位置，回到步骤(1)；若r>pa，则表示不会被发现，因此不需要做出改变。若r>pa的情况发生，需要循环进行前面的步骤，挑选出最优的鸟巢位置，做出决策。

(4)比较：若f满足约束条件或满足运算的结束条件，则决策即为全局最优解，反之，返回步骤(2)。

基本布谷鸟算法利用 Lévy飞行机制进行寻优，搜寻过程中局部信息运用不充分，致使该算法在每个鸟巢周围无法细致寻优。该算法表现为高度随机跳跃性，对收敛性无法确定，收敛性差的情况下，运算时间变长，同时搜索能力较差。

2.2 改进布谷鸟算法

针对基本布谷鸟算法中局部信息运用不充分、收敛性差的问题，提出了对放弃概率、步长因子的改进，同时随机数的产生部分增添了Halton序列，实现随机数选取的密集性及科学化。

(1)Halton序列选取随机数

Halton序列是一种低偏差随机序列。其构造相对较为简单，因此得到了广泛的应用。Halton序列的定义如下：

xn=(φb1(n),…，φbj(n),…，φbd(n))

(15)

Halton序列常常被用来产生空间点，Halton序列的产生，即选取一个质数作为基数，然后不断地切分，从而形成一些不重复并且均匀的点，每个点的坐标都在0～1之间。以一维数轴生成Halton序列为例：取2作为基数，那么首先对(0,1)进行切分，得到1/2；最终得到的数列为：1/2,1/4,3/4,1/8,5/8,3/8,7/8,1/16,9/16，…。由此可以看出，Halton序列得到的数列分布均匀且密集。将Halton序列运用于布谷鸟算法中随机数的产生，可以使产生的随机点分布更为均匀，从而使得布谷鸟搜索的搜索结果更优。

(2)步长及发现概率的改进

在基于Halton序列的改进布谷鸟(HICS)算法基础上，进一步对鸟巢的放弃概率pa与步长因子∂0进行改进。在初始的计算流程中，放弃概率及步长因子需要保证足够大，增加初始的可行解。随着计算次数的增加，二者的取值应减小，加快收敛速度。具体pa与∂0的公式见(16)。

(16)

式中：t表示当前迭代次数；tmax表示最大迭代次数。pa,max、pa,min表示放弃概率pa的最大值与最小值，同理∂max、∂min表示∂0的最大与最小值。假定取pa,max=0.5，pa,min=0.1，∂max=0.015，∂min=0.005，tmax=1 000。m1、m2为次幂，控制两个因子的变化程度。为了保证该算法在整体搜寻能力与局部搜索能力之间的平衡，借鉴相关研究成果，假定m1=0.5，m2=3，pa与∂0随迭代次数变化曲线如图1所示。

图1 pa与∂0随迭代次数变化图

从图1可以看出，pa在t<750的情况下下降较慢，在t达到750步时，pa仍大于布谷鸟算法中的默认值0.25，在t>750的情况下较快地降至最小值；而在t<200的情况下，随着t的增大，下降趋势明显，当t超过200后，小于布谷鸟算法中默认值0.01，且在迭代后期取值保持在最小值范围。

以上对于发现概率及搜索步长的改进，能够避免陷入局部最优解的困境且兼顾算法的收敛性。在迭代后期，加强局部的精细搜寻，使得到的结果相对最优。

3 算例分析

3.1 基础数据

以A省电力公司作为研究对象，对其电力物资配送中心选址进行研究。该算例中包含22个物资需求点(n=22)。根据A省的宏观建设规划，建设3个物资配送中心(n=3)，通过求得配送总成本最优，对其进行科学的物资配送中心选址，以期优化电力物资配送。

根据物资需求点的地理分布，用MATLAB绘制22个物资需求点的相对位置图，具体见图2。

图2 物资需求点相对位置图

本文涉及的22个物资需求点的needj(需求量)与位置坐标见表1。

关于布谷鸟算法中的相关的参数设置如表2。

3.2 物资配送中心选址结果分析

将以上设置的参数取值代入基于Halton序列的改进布谷鸟算法中，对A省电力物资配送中心进行选址研究。用MATLAB进行程序的运行，得到A省电力物资配送中心选址的优化结果，见表3，收敛性见图3。

根据表3可以得到，A省物资的总配送费用为14 045元。配送中心 11负责向物资需求点1,8,10,15,19,20,21进行电力物资配送，配送中心7负责向物资需求点2,3,4,5,6,9,17进行电力物资配送，配送中心14负责向物资需求点12,13,16,18,22进行电力物资配送。由图3可以得出，该算法在迭代300次后趋于稳定。根据历史经验，其收敛性相对较好。基于Halton序列的改进布谷鸟算法得到的配送中心选址方案具体如图4所示。

表1 物资需求点坐标及需求量

表2 参数设定

表3 基于Halton序列的改进布谷鸟算法求解A省配送中心选址的结果

图3 HICS算法选址优化图

图4 HICS算法A省物资配送中心选址及配送图

为了进一步验证基于Halton序列的改进布谷鸟算法的有效性与优越性，进一步对比了传统布谷鸟算法及遗传算法对A省电力物资配送中心选址的运行结果，具体见表4和图5。

由表4可得，CS算法得到的 A省物资的总配送费用为14 520元。GA算法得到的 A省物资的总配送费用为14 700元。相比遗传算法，布谷鸟算法总配送费用较低。这说明布谷鸟算法的寻优能力较好。相比传统布谷鸟算法和遗传算法，基于Halton序列的改进布谷鸟算法在收敛速度、计算时间和经济性上均有显著提高。

表4 CS及ICS求解A省物资配送中心选址的结果

图5 对比收敛图

图3与图5的3个收敛图对比可以发现，HICS算法迭代次数为300次时，迭代结果最优，而CS算法迭代次数为355次左右时，迭代结果收敛；GA算法在迭代400次后，获得全局的最优解。这说明，布谷鸟算法的收敛速度明显优于遗传算法。而基于Halton序列的改进布谷鸟算法，对步长及发现概率作出改进，使得其收敛性优于布谷鸟算法。

上述的运算结果表明，本文将改进的布谷鸟算法用于电力物资配送中心选址问题具有科学性。HICS算法的结果优于CS、GA，说明改进布谷鸟算法的寻优结果更好，且收敛速度、计算精度都有所提高，验证了改进布谷鸟算法的优越性，改进布谷鸟算法在求解物流配送中心选址问题上是一种有效的算法。改进的布谷鸟算法能够有效解决多目标离散点的选址问题，选址的结果能够提高电力物资的利用效率，降低企业配送总费用，指导现实的选址及配送问题。

4 结论

本文提出了一种基于Halton序列的改进布谷鸟算法，求解电力物资配送中心的选址问题。针对CS算法在求解物资配送中心选址问题时存在的搜索精度低，收敛速度慢易陷入局部最优的缺陷，HICS算法对CS算法莱维飞行中的步长及发现概率进行了改进，这一改进可以使算法平衡局部最优与整体最优，同时可以保证算法的收敛速度较快；另外采用低偏差的Halton序列产生随机数，可以使产生的随机点分布更为均匀，保证了算法的搜索精度。以A省供电公司电力物资配送中心选址问题为例，进行模型的实证分析，对比分析了GA、CS及HICS的选址结果。结果表明HICS算法能够有效解决多目标离散点的选址问题，选址的结果能够提高配送效率，有利于电力企业的物流发展，指导现实的选址及配送问题。