基于改进烟花算法的物流配送中心选址研究

李小川+刘媛华

摘要：利用烟花算法求解物流配送中心选址问题，但存在早熟收敛、搜索精度低、鲁棒性较差的缺陷，为此提出一种改进烟花算法SOFWA用于求解该问题。将人群搜索算法中的利己行为、利他行为和预动行为引入烟花算法，以加强各烟花与最优烟花之间的信息交互，从而增大最优烟花的搜索领域；对烟花爆炸和变异过程中产生的无效烟花进行剔除操作，提升算法运行效率。仿真实验证明，改进烟花算法在求解物流配送中心选址问题时有效避免了以上缺陷，相对于其它算法具有一定的优越性。

关键词关键词：物流配送中心选址；烟花算法；预动行为；无效火花剔除

DOIDOI：10.11907/rjdk.171772

中图分类号：TP319

文献标识码：A文章编号文章编号：16727800（2017）011015304

0引言

随着科技的迅速发展，物流业已经成为促进国家经济发展和提高国民幸福指数的重要基础产业[1]。对于许多公司而言，物流配送中心选址都是物流环节至关重要的一环，合理的物流配送中心选址方案可以节约物流成本并提高公司整体运行效率。物流配送中心选址问题具有非线性、非凸性、复杂性和约束条件多且相互之间难以协调的特点，是典型的非线性规划模型，也被证明为NP-hard问题。物流配送中心的建设规模一般较大，一旦确定就很难改变。因此，对物流配送中心选址问题进行研究具有重要的理论和现实意义。

物流中心选址问题由Weber和Friedrich[2]于1929年首次提出，其求解难度随着问题规模的增大而急剧增加。智能优化方法在求解大规模物流配送中心选址问题时具有明显优势。文献[35]分别采用遗传算法（Genetic Algorithm，GA）、粒子群算法（Particle Swarm Optimization，PSO）和蚁群算法（Ant Colony Optimization，ACO）求解物流配送中心选址问题，但是这3种方法求解物流配送中心选址问题易陷入早熟收敛，鲁棒性较差。Wang Y[6] 等将遗传算法中的交叉变异思想引入粒子群算法求解物流配送中心选址问题；马毓咛[7]等将免疫算法中“抗体记忆能力”的思想引入粒子群算法，提出了免疫粒子群算法，提高了求解的有效性；费腾[8]等将细菌觅食的“趋化思想”概念加入人工鱼群算法，提出了BFOAFSA算法，在求解物流配送中心选址问题时比鱼群算法更加稳定可靠。

烟花算法（Fireworks Algorithm，FWA）是由北京大学学者Tan和Zhu[9]于2010年受到烟花爆炸过程中产生不同爆炸半径和火花个数的启发而提出的一种新型智能优化算法。该算法原理简单明确、参数少、搜索效率高且较易实现，受到许多学者关注。Pei等[10]基于烟花产生的火花和高斯火花的坐标信息评估解空间形状，将形状凸点作为当前最优位，从而加快了种群的收敛速度。Ding 等[11]提出了GPUFWA算法，对烟花爆炸半径进行改进，在间隔一定迭代次数后对爆炸半径进行交互计算，加快了收敛速度。朱启兵等[12]利用适应值计算各烟花质量，提出了引力搜索机制，并通过Benchmark 函数测试求解效能。目前尚无可用烟花算法求解物流配送中心选址问题相关研究，本文尝试用烟花算法求解物流配送中心选址问题，并根据前期实验结果对烟花算法进行改进，引入SOA变异策略，即用人群搜索算法（Seeker Optimization Algorithm，SOA）中的利己行为、利他行为和预动行为对除最优值之外的烟花（以下简称烟花*）进行扰动，以改善烟花算法求解物流配送中心选址问题时易陷入局部最优的问题，并对烟花爆炸和变异产生的无效火花进行剔除，加快收敛速度。通过实验仿真及与其它算法对比，证明了改进烟花算法的有效性和优越性。

3.3无效烟花剔除

烟花算法相对其它智能算法具有爆发性的特点，通常具有较快的收敛速度。然而采用随机键编码时烟花爆炸也极易产生无效火花，从而降低收敛速度。比如某烟花爆炸产生的两个火花为X1=[8，2，12，4，7，19]和X2=[8，4，12，2，7，19]，两个火花粒子排序不同，但实际选址相同，其中一个火花对算法收敛没有作出任何贡献，为无效烟花，在实际运算中往往会产生更多无效烟花。本文将无效烟花直接剔除以降低单次迭代运行时间，在有限时间内给予了更多烟花爆炸机会，从而加快收敛速度。

3.4改进算法步骤

算法步驟如下：

Step1：初始化各参数，设置烟花个数N，基本爆炸半径A，基本火花个数S，火花个数约束常数a和b，高斯变异烟花数l，最大迭代次数G，当前迭代t=1。

Step2：初始化N个烟花。

Step3：由式（9）-（11）计算烟花爆炸半径和火花个数，由式（7）计算爆炸火花，对超出边界的维度根据式（8）有效映射。

Step4：由式（12）计算高斯变异火花，根据式（8）将超出边界的维度映射到可行域。

Step5：由式（15）-（18）对烟花*进行SOA变异，根据式（8）将超出边界的维度映射到可行域。

Step6：剔除以上火花中的无效火花。

Step7：计算火花粒子的适应度值，将所有烟花和火花粒子按适应度值进行升序排列，第一个粒子直接保留至下一代，根据式（13）、（14）选择剩余的N-1个粒子，更新下一代烟花。

Step8：若t

4仿真实验结果及分析

4.1实验仿真

为了验证本文所提改进烟花算法求解物流配送中心选址问题的效能，本文利用MatLab R2012a软件，以文献[7]中的全国31个城市的位置坐标和货物需求量（见表1）为例进行仿真实验，以运输距离和需求量的乘积作为适应度函数，并对烟花算法、改进烟花算法和文献[7]中所提的免疫粒子群算法IMPSO求得的结果进行对比。算法参数为：SOFWA，烟花个数为5，基本爆炸半径A=2，基本爆炸火花数S=50，高斯变异烟花数l=5，a=0.04，b=0.6；免疫粒子群算法IMPSO参数参考文献[7]。3种算法最大迭代次数均为100，每种算法独立运行20次。

4.2实验结果分析

3种算法求解物流配送中心选址问题的统计结果如表2所示，FWA、IMPSO和SOFWA求得的最优物流配送中心选址方案如图1、图2所示，FWA和SOFWA分别运行20次所得最优选址结果对比如图3所示。FWA求得的最优值为555 333.30，收敛代数为34，SOFWA求得的最优值为549 125.23，收敛代数为21，可见SOFWA在求解物流配送中心选址问题的寻优精度及运行效率方面都明显优于FWA。在平均最优值、平均收敛次数方面，SOFWA的结果也明显优于FWA；在方差方面，SOFWA的结果则比FWA低一个数量级，说明SOFWA的稳定性较FWA明显提高。总体而言，改进烟花算法较烟花算法在求解物流中心选址问题时的性能有较大提升。

IMPSO和SOFWA分别运行20次所得最优选址结果对比如图4所示，两种算法求得最优值均为549 125.23，但是在20次运行中，SOFWA击中最优值17次，而IMPSO仅击中12次。在平均最优值和方差方面，IMPSO求得结果分别为554 125.22和93.25，SOFWA求得结果分别为550 993.26和17.40，均小于IMPSO所得结果。说明SOFWA在求解物流中心选址问题时比IMPSO具有更好的鲁棒性。另外，SOFWA的平均收敛代数要比IMPSO少5.6。在平均收敛时间方面，SOFWA比IMPSO节省了11.14s，说明SOFWA的求解效率更高。以上分析表明，SOFWA可以作为一种求解物流配送中心选址问题的有效方法。

5结语

本文首次尝试用烟花算法求解物流配送中心选址问题，并在烟花算法中引入人群搜索算法中的利己行为、利他行为和预动行为，以改进基本烟花算法求解物流中心选址问题时存在的早熟收敛、搜索精度低、鲁棒性差的不足。对无效火花进行剔除以提升烟花算法运行效率，节省单代运行时间，从而节省收敛时间。通过实验仿真验证了改进烟花算法求解物流配送中心选址问题的有效性，进一步与相关文献中的其它算法进行比较，表明改进烟花算法具有更好的稳定性。下一步的研究目标是，更合理地设置改进烟花算法的参数，并且尝试将其应用于物流配送车辆路径优化问题求解中。

参考文献参考文献：

[1]马祥丽，张惠珍，马良.带时间窗物流配送车辆路径问题的蝙蝠算法[J].计算机工程与应用，2016（11）：254258，264.

[2]WEBER A，FRIEDRICH C J.Alfred weber′s theory of the location of industries[M].University of Chicago Press，1929.

[3]禤文怡，汪波，袁建强.基于遗传算法和指标满意度求解的第三方物流企业物流配送中心选址方法[J].运筹与管理，2004，13（2）：139144.

[4]黄敏镁.粒子群算法在物流配送中心选址中的应用[J].计算机工程与应用，2011，47（4）：212214.

[5]李文超.用蚁群算法求解物流配送中心選址优化问题[J].物流技术，2014，33（9）：276277，295.

[6]WANG YONG，MA XIAOLEI，XU MAOZENG.Twoechelon logistics distribution region partitioning problem based on a hybrid particle swarm optimizationgenetic algorithm[J].Expert Systems With Applications，2015，42（12）：50195031.

[7]马毓咛，许峰.免疫粒子群算法及其在物流配送中心选址问题中的应用研究[J].软件导刊，2013，12（12）：7174.

[8]费腾，张立毅，陈雷.配送中心选址问题的BFOAFSA算法研究[J].计算机工程与应用，2015，51（23）：15，10.

[9]TAN YING，ZHU YUANCHUN.Fireworks algorithm for optimization[C].Berlin：Springer，2010：355364.

[10]YAN PEI，ZHENG SAOQIU，TAN YING，et al.An empirical study on influence of approximation approaches on enhancing fireworks algorithm[C].IEEE International Conference on Systems，Man，and Cybernetics. Seoul，South Korea，2012：13221327.

[11]DING KE，ZHENG SHAOQIU，TAN YING.A GPUbased parallel fireworks algorithm for optimization[C].Proceedings of the Fifteenth Annual Conference on Genetic and Evolutionary Computation Conference，2013：916.

[12]朱启兵，王震宇，黄敏.带有引力搜索算子的烟花算法[J].控制与决策，2016，31（10）：18531859.

[13]杜振鑫.基于种群进化速度的动态烟花算法[J].微电子学与计算机，2016，33（10）：2427.

责任编辑（责任编辑：孙娟）endprint