基于鲶鱼效应粒子群算法的物流配送中心选址

黎 华

（西昌学院 汽车与电子工程学院，四川 西昌 615000）

1 引言

随着我国经济的迅速发展，物流配送业务日益增多，配送中心在物流系统中起着枢纽作用，其目标主要根据区域内不同客户要求，将商品货物及时、准确和有效地送到客户手中，因此物流配送中心选址是物流系统研究中的核心，对于选择最佳物流配送中心具有十分重要的实用价值[1]。

针对物流配送中心选址问题，国内外学者进行了大量的研究，提出了许多选址模型[2]。大量研究表明，物流配送中心选址问题是一个带有复杂约束的目标优化问题，属于NP-hard问题[3]。为此，学者们提出了禁忌搜索算法、遗传算法、蚁群算法等，这些算法都取得了一定的成效[4-6]。由于这些算法都属于启发式搜索算法，当所求问题的规模较大时，寻优速度慢，难以获得全局最优的物流配送中心选址方案，选址效果不够理想[7]。粒子群优化算法（PSO)模拟鸟群觅食行为，具有收敛速度快、寻优能力强、参数设置简单等优点，成为物流配送中心选址问题求解的主流算法[4,8]。在实际应用中，标准PSO算法存在一些缺陷，如易出现“早熟”现象，当物流配送点多时，PSO算法易获得物流配送中心选址的局部最优解，寻优效果差[9]。

为了解决标准PSO算法在物流配送中心选址问题求解过程存在的缺陷，引入自然界的“鲶鱼效应”（catfish effect），提出了一种基于鲶鱼效应粒子群算法的物流配送中心选址策略（CFPSO），并通过对实际物流配送中心选址问题进行仿真实验，与标准PSO算法、遗传算法进行对比，验证CFPSO用于物流配送中心选址问题求解的有效性。仿真结果表明，CPSO算法较好地克服了其它算法存在的缺点，可以获得全局最优的物流配送中心选址方案，具有对比算法无法比拟的优势。

2 物流配送中心选址问题描述

物流配送中心选址模型可表示为：

式（1）中，Wij表示需求点i对配送中心j的需求量；l表示需求点与配送中心的距离上限；M为被选为配送中心的需求点的集合；N表示所有需求点的序号集合；Cj为配送中心的建设费用；gj表示配送中心物资流转的单位管理费用；hj∈{0,1}，当其为1时表示点j被选为配送中心；dij表示需求点i离它最近的配送中心j的距离；Zij∈{0,1}表示需求点与配送中心的服务分配关系，当其为1时，表示需求点i的需求量由配送中心j供应，否则Zij＝0[10]；Bj表示配送中心j的供应上限。

式（1）相应的限制条件为：

约束条件中，式（2）表示需求点i对配送中心j的需求量应小于配送中心j的总供应量；式（3）表示每个需求点由离它最近配送中心服务；式（4）表示没有配送中心的地点不会有客户；式（5）表示有p个需求点被选为配送中心；式（6）表示配送中心只对附近的需求点进行服务。

3 鲶鱼效应的粒子算法

在PSO算法中，每一个粒子代表待求解问题的一个潜在解，由适应度函数确定粒子的优劣程度。首先随机产生一群粒子，然后计算粒子的适应度值，最后粒子在解空间不断飞行，最终找到问题的解。设粒子个体和整个群体的最优位置分别为pbest和gbest，粒子的速度与位置更新公为：

其中，ω 为惯性权重；c1和c2为学习因子；rand()为（0,1）之间的随机数；vi,dk和xi,dk分别为粒子i在第k次迭代中第d维的速度和位置；pbesti,dk是粒子i在第d维的个体极值的位置；gbestdk是群体在第d维的全局极值的位置。

由式（7）和式（8）可知，粒子群算法出现早熟收敛现象，那么pg一定是局部最优解，通过改变pg或pi，让粒子逃出局部最优解区域。

CFPSO采用偏差阈值作为触发条件，通过鲶鱼算子对全局极值或个体极值进行扰动，粒子速度更新变如下：

式（9）中，c3表示鲶鱼对个体最优的冲撞强度;c4表示鲶鱼对全局最优的冲撞强度；c3·rand()和c4·rand()称为鲶鱼算子，其定义如下：

式中，ep表示当前值与当前个体最优值的偏差；eg表示当前值与当前全局最优值的偏差；e0p表示当前值与当前局部最优值之偏差的阈值；e0g表示当前值与当前全局最优值之偏差的阈值。

由式（10）、式（11）可知，若当前值的偏差大于偏差阈值，鲶鱼算子取为1，此时CFPSO算法为标准PSO算法；反之，认为此时粒子发生聚集，引入鲶鱼算子去冲撞个体最优值或局部最优值，以跳出局部最优。

4 基于CFPSO的物流配送中心选址问题求解

4.1 粒子的编码方式

采用CFPSO算法对物流配送中心选址问题进行求解时，首先也是最为关键的一步就是粒子编码。粒子的具体编码方式为：X=(x1,x2,...,xN)，其中粒子的长度N为物流中心备选点的个数，若最后求出的最优粒子X=(1,0,0,1,1,0,0)，则表示在7个物流备选点中，第1、第4和第5个备选点将作为物流配送中心。

4.2 求解的具体步骤

Step 1:设置CFPSO算法的参数。主要包括粒子数目、ω、c1、c2、粒子速度以及粒子位置。

Step 2:初始化粒子群。传统PSO算法采用随机方式产生初始粒子群，易使粒子集中于某一局部，可行解分布不均匀，本文采用均匀方法产生初始粒子群，保证初始粒子群分布的均匀性。

Step 3:计算每个粒子的适应度值，根据适应度值确定个体最优值和群体最优值。

Step 4:根据式（10）和式（11）确定鲶鱼算子，并更新粒子的速度和位置。

Step 5:计算每个粒子在新位置上的适应度值，如果粒子的适应度值优于个体的适应度值，则个体更新为新位置；如果粒子的适应度值优于群最优值，则群体最优值更新为新位置。

Step 6:如果达到最大迭代次数，输出最优物流配送中心选址方案，否则转到Step 2，继续进行寻优。

具体流程如图1所示。

图1 CFPSO的物流配送中心选址问题求解流程

5 仿真实验

5.1 仿真环境

为了验证CFPSO算法对物流配送中心选址问题求解的有效性，在P4双核2.8G CPU、1G内存，操作系统为Windows XP的计算机上，在Matlab2009环境下进行了实验。客户地址和物流需求量见表1，为使CFPSO算法的选址结果具有可比性，采用遗传算法、标准粒子群算法进行对比仿真实验。

表1 需求点位置和物资需求量

5.2 CFPSO的结果分析

采用CFPSO算法对表1的物流配送中心选址问题进行求解，从26个客户点中选择5个位置作为配送中心。c1＝c2=2，w为0.55，最大迭代次数为100，粒子数目为20，那么CFPSO算法的收敛曲线如图2所示。

图2 CFPSO的收敛曲线

物流配送中心选址方案如图3所示。从图3可知，采用CFPSO算法可以获得较优的物流配送中心选址方案，其圆点表示需求点，方框表示配送中心。

5.3 与其它算法的性能对比

遗传算法、标准粒子群算法和CFPSO算法的物流配送中心选址问题求解性能对比结果见表2。从表2可知，相对于遗传算法、标准粒子群算法，CFPSO算法对物流配送中心选址问题进行求解时，求解速度明显加快，求解效率更高。对比结果表明，CFPSO较好地克服了传统算法求解过程存在的不足，是一种有效的物流配送中心选址问题求解算法，尤其对于大规模物流配送中心选址问题的优势更加明显。

图3 基于CFPSO的物流配送中心选址方案

表2 不同算法的总体性能比较

6 结语

针对标准粒子群算法存在早熟收敛、易出现局部最优等缺陷，引入自然界的“鲶鱼效应”，提出了一种基于鲶鱼效应粒子群算法的物流配送中心选址策略。由于引入“鲶鱼效应”，可以较好地保持粒子的活性，更加真实地反映了粒子的运动规律。仿真实验结果表明，相比于遗传算法、标准粒子群算法，CFPSO算法可以获得更优的物流配送中心选址方案，可以快速、准确地找到最优的物流配送中心。

[1]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001.

[2]Ming-Shin Kuo.Optimal location selection for an international distribution center by using a new hybrid method[J].Expert Systems with Applications,2011,38(6):7 208-7 221.

[3]Xu Jiuping,Yao LM,Zhao XD.A multi-objective chance-constrained network optimal model with random fuzzy coefficients and its application to logistics distribution center location problem[J].Fuzzy Optimization and Decision Making,2011,10(3):255-285.

[4]Yang Lixing,Ji Xiaoyu,Gao Ziyou.Logistics distribution centers location problem and algorithm under fuzzy environment[J].Journal of Computational and Applied Mathematics,2007,208(2):303-315.

[5]Ye Lia,Xiaodong Liua,Yan Chen.Selection of logistics center location using Axiomatic Fuzzy Set and TOPSISmethodology in logistics management[J].Expert Systems with Applications,2011,38(6):7 901-7 908.

[6]Huijun Sun,Ziyou Gao,Jianjun Wu.A bi-level programming model and solution algorithm for the location of logistics distribution centers[J].Applied Mathematical Modelling,2008,32(4):610-616.

[7]Sen Liua,Felix T S Chanb,S H Chungb.A study of distributioncenter location based on the rough sets and interactive multi-objective fuzzy decision theory[J].Robotics and Computer-Integrated Manufacturing,2011,27(2):426-433.

[8]Yasanur Kayikci.A conceptualmodel for intermodal freight logistics centre location decisions[J].Procedia-Social and Behavioral Sciences,2010,2(3):6 297-6 311.

[9]程明辉,齐名军.基于粒子群算法的物流配送路径优化问题研究[J].中国外资,2008,(8):254-256.

[10]易文周.混沌鲶鱼粒子群优化和差分进化混合算法[J].计算机工程与应用,2012,48(15):54-58.

[11]Chuang L Y,Wei T S,Yhong Y C.Chaotic catfish particle swarm optimization for solving global numerical optimization problems[J].Applied Mathematics and Computation,2011,217:6 900-6 916.