布谷鸟搜索算法在超市配送中心选址问题中的应用

刘佳 冯震 徐越群 刘丽娜

摘 要：以节省企业各项运营成本和最小投资费用为目标，建立了连锁超市配送中心选址问题的数学模型。为解决优化选址问题，对基本的布谷鸟搜索算法（Cuckoo Search，CS）进行了研究，鉴于CS算法局部搜索能力差、进化后期收敛速度慢等缺陷，考虑到二次插值法是一种局部搜索能力较强的搜索方法，提出了一种基于二次插值法的布谷鸟搜索算法（QI_CS）。仿真实验结果表明，提出的QI_CS算法不但降低了计算的复杂度，大幅提高了算法的收敛能力和求解精度，更优化了选址模型，而且为解决物流选址问题提供了新的有效途径。

关键词：布谷鸟搜索算法；二次插值法；配送中心；选址

引言

文章以连锁超市物流配送中心选址模型为研究对象，以构建行之有效的最优选址方法为研究目标，考虑运输成本、管理成本、建设成本等约束条件的基础上，建立物流配送中心选址问题的绿色数学模型。为了提高求解该数学模型算法的收敛速度和求解精度，获得最佳选址方案，借鉴智能仿生算法——布谷鸟搜索算法对初值、参数选择不敏感、鲁棒性强、参数少、易实现等诸多优点，将该算法用于求解连锁超市物流配送中心绿色选址模型，并采用二次插值法对基本的布谷鸟搜索算法的局部搜索能力进行改进。整合后的新算法求解的选址方案将改善配送中心的服务方式，提高服务质量和服务效率，降低服务成本等，从而影响企业的利润和市场竞争力，实现经济的可持续发展。

1 模型构建

本模型要研究的问题是：在模型中设置几个配送中心，确定配送中心应选在哪里，供货点如何向现有的备选配送中心送货，每个配送中心配送哪些需求点（超市）等。物流配送中心的选址问题属于最小费用问题，即求解运输费用、运营费用、固定建设费用等之和为最小的优化问题。

首先，为建立模型做以下假设：备选点为离散的点，货源点、备选点和需求点都是已知，需求点的需求量为己知；从货源到配送中心和从配送中心到需求点的距离及单位运价为己知；所有的货物都经由配送中心到需求点；每个需求点由一个配送中心配送货物；货源点的生产能力能满足用户需求；所配送产品或者商品能一次运输完成；物运输成本费用是运输数量和运输距离等的函数，与运输数量呈正比例关系；新的配送中心位置只在符合一定条件的地点范围内考虑。

配送中心选址模型的建立主要考虑四个方面的费用：一是配送中心的建设费用；二是从供货点到配送中心的运输费用；三是从配送中心到需求点（各个超市）的运输费用；第四是货物在配送中心的流转和管理费用之和。

2 基于二次插值法的CS算法

2.1 CS算法简介

为了模拟布谷鸟寻窝的方式，需要设定以下三个理想的状态[4]：

（1）布谷鸟一次只产一个卵，并随机选择鸟窝位置来孵化它；（2）在随机选择的一组鸟窝中，最好的鸟窝将会被保留到下一代；（3）可利用的鸟窝数量n是固定的，一个鸟窝的主人能发现一个外来鸟蛋的概率pa∈[0，1]。为方便起见，最后这个假设可以近似理解为被新巢替换（新的随机解决方案） 的概率为pa。在算法中，每个巢里的一个布谷鸟蛋代表一个解决方案，以及一个布谷鸟蛋代表了一种新的解决方案。目的是利用新的以及潜在的更好的解决方案，来取代一个在巢里的不那么好的解决方案。

在这三个理想状态的基础上，布谷鸟寻窝的路径和位置更新公式如下：

式中Xit表示第i个鸟窝在第t代的鸟窝位置，？茌为点对点乘法；？坠表示步长的控制量；L（？姿）为Levy随机搜索路径，并且L～u=t-？姿，（1<？姿？燮3）。通过位置更新后，用随机数r∈[0，1]与pa对比，若r>pa，则对Xit+1进行随机改变，反之不变。最后保留测试值较好的一组鸟窝位置Yit+1，此时仍记为Xit+1。

2.2 基于二次插值法的CS算法

二次插值法（Quadratic Interpolation）是一种局部搜索能力较强的搜索方法，不需要目标函数的导数信息，计算量小。可以利用二次插值法的优势对基本的CS算法进行改进。

针对多维问题的优化解，可以把二次插值法应用于求解空间中的每

一个维度。假设存在给定的三个点 ，

分别计算这三点的适应度值或者函数值得到fa、fb、fc，并且，其中最小的是fb。对每个维度分别使用二次插值法，则可得到下面的结果。假设近似极小值点是：

式中A和B计算如下：

在算法的每一次迭代中，xa为当代鸟窝个体当前位置，xb为当代的最优鸟窝个体位置、xc为当代的最差鸟窝个体位置，并且xa？埸{xb，xc}，xb的适应度值最小。

文章以后将基于二次插值的布谷鸟搜索算法简称为QI_CS算法。

3 实验仿真与结果分析

利用文章提出的QI_CS算法对文献[4]中的数据进行验证，提供数据如下：某超市有两个货源供应点K1和K2，现有连锁超市即需求点A1、A2、A3、…、A8，共8个，有6个物流配送中心地址可供选择，分别为P1、P2、…、P6，其他数据参可看相关文献。

4 结束语

文章提出了一种改进的布谷鸟搜索算法-QI_CS算法，用于求解物流配送中心选址模型，新算法针对基本CS算法的不足，将二次插值法引入到布谷鸟搜索算法中，增强了算法本身的局部搜索能力，充分利用了更多局部区域的优化信息，从而得到了精度更高的全局最优解，克服了传统CS的不足。

参考文献

[1]申慧，丁北，宋治飞.基于免疫优化算法的选址问题研究[J].才智，2013（20）：274.

[2]王凡，贺兴时，王燕，等.基于CS算法的Markov模型及收敛性分析[J].计算机工程，2012，38（11）：180-182.

[3]李煜，马良.新型元启发式布谷鸟搜索算法[J].系统工程，2012，30（8）：64-68.

[4]武建娜，崔志华，刘静.基于二次插值法的社会情感优化算法[J].计算机应用，2011，31（9）：2522-2525.

[5]隋崴崴，宋现允，付蕾.物流配送中心选址数学模型和算法问题研究[J].物流技术，2013，32（6）：158-159.