基于粒子群算法的物资配送优化研究

方文超

(广东工贸职业技术学院经济贸易系，广东广州510510)

0 引言

物资配送是企业运营的基础之一，其关系到生产和销售的正常开展。优化物资配送不仅能够有效降低费用，而且能保障企业物资流转的协调发展。物资配送如何进行优化已成为企业运作的关键。但是，物资配送往往受到许多因素约束，这大大增加其复杂性。因此，优化物资配送成为学术界和企业界的研究热点。

粒子群算法是近年来新兴的人工智能技术，其通过模仿鸟群觅食而求得最优解，属于群智能算法。它能够通过个体与群体之间相互作用，突出群体智能的优势，并具有强大并行计算能力，有着高度鲁棒性。

关于物资配送优化研究，现有文献主要采用最小元素法、遗传算法、粗糙集等方法。［1］108-111，［2］13-16，［3］119-122目前采用粒子群算法求解物资配送优化问题的研究基本处于空白。因此，本文探索采用粒子群算法进行物资配送优化问题的求解，尝试填补该领域空白。由此为物资配送优化提供一种新的研究方法，并为企业决策提供参考。

1 粒子群算法

粒子群算法(Particle Swarm Optimization)是一种群智能算法，属于启发式全局优化算法。该算法通过模拟鸟群觅食行为寻找最优解。其所模拟的鸟群觅食过程是:假设鸟群正在随机寻找食物(即最优解)，当其中一只鸟成功找到食物，那么其周围的鸟就会向这个成功者学习，向着食物所在位置飞去，即成功者会引导其周围鸟类飞向食物所在地。并且鸟类觅食还有一个显著特点，这就是每只鸟既向成功者学习和模仿，使其能向食物所在地飞去，但也会设计自己的专属路线或个性化路线，以至于不会与其他鸟类发生碰撞。因此，粒子群算法的特点是既要使每个个体寻找最优解时与其他个体不发生碰撞，即保持其个性，又要使其向成功者学习模仿，走向目的所在地，即保持其社会性或共性。也就是说粒子群算法实现了个性和共性或社会性的协调和平衡，是一种新兴的人工智能技术。

粒子群算法的数学模型是［4］63-85，［5］269-273:

设 Si=(si1，si2，…，sin)为粒子i的当前位置，Vi=(vi1，vi2，…，vkn)为粒子i的当前飞行速度，Hi=(hi1，hi2，…，hin)为粒子i所经过的最佳位置，即最好的适应值。

一般地，设f(X)为实现最小化的目标函数，那么粒子i的当前位置由下式确定:

其中，k为粒子i的第k次循环。

粒子群算法的基本方程如下:

由式(2)可得，等式右边的第一项表示粒子以前的飞行速度，第二项表示粒子向自身最佳位置飞去，第三项表示粒子向全局最佳位置飞去。

在实际使用中，使用粒子群算法需进行改进和调整。这是因为由式(2)可知，如果w取值较大，可以提高全局搜索能力，但是也使得运算量变得过大;如果w取值较低，则可能会出现局部极小化的缺陷。而传统的基本算法中w设为1，会影响收敛能力。因此，本文使用权重线性调整法调整w，能够有效提高算法的全局搜索能力。惯性权重w 的调整公式是［5］269-273:

其中，wmax为最大惯性权重，wmin为最小惯性权重，q为当前粒子循环次数，qmax为预先设定最大循环次数。使用中，wmax通常在0．8 ～1．2之间取值，wmin通常在0．4～0．5之间取值。［6］69-73，［7］84-89

2 物资配送问题的描述

假设一个厂商生产一种产品，该产品在n个工厂生产，并对m个区域进行产品供应。设F1，F2，F3，…，Fn为所拥有的共 n 个生产工厂，设 R1，R2，R3，…，Rm为其供应共m个区域。设每个生产工厂的产量不大于Gi(i∈{1，2，…，n})，每个区域供应量不少于 Lj(j∈ {1，2，…，m})。并且，第 i个生产工厂把产品运到第j个区域的单位配送费用为Cij。设Xij为从第i个生产工厂运到第j个区域的产品数量，该物资配送问题的求解目标是实现总配送费用最小化。一般地，以上各个参数均不小于零，问题所求解的未知数为Xij。

上述物资配送问题的数学模型是:

以上数学模型的本质是一个优化问题，即求解Xij，实现y最小化。

3 粒子群算法对于物资配送问题的求解

使用粒子群算法对于上述物资配送问题求解的基本思路是:设所要求解的未知数Xij为粒子i在第j维的当前位置，并经过若干次循环后，满足设定精度，实现目标函数最小值的求解。

参考相关文献［5］269-273，根据物资配送问题的设计，本研究提出的粒子群算法对于物资配送问题求解的基本过程如下:

步骤1:初始化粒子群的基本参数。

步骤2:使用目标函数计算每个粒子适应度。

步骤3:把每个粒子的目前适应度与其之前最优适应度比较，如果目前适应度更优，则以目前适应度取代之前最优适应度;否则，不更新粒子自身最优适应度。

步骤4:设定群体最优值保持不变的次数为e，把每个粒子自身最优适应度与整个群体最优适应度比较，如果粒子自身最优适应度更优，则以该粒子自身最优适应度取代群体最优适应度，并设e=0;否则，不更新群体最优适应度，e增加1，若e大于设定次数，则需要对部分粒子初始化。

步骤5:更新每个粒子的位置和速度。

步骤6:如果达到设定精度，则算法结束，得到最优解;如果循环次数达到规定循环次数，但精度不满足要求，则返回步骤1，重新初始化算法;如果循环次数未达到规定次数，且精度不满足设定精度，则返回步骤2，继续寻找最优解。

本研究的粒子群算法对于物资配送问题求解的基本过程如图1所示。

图1 粒子群算法对于物资配送问题求解的基本过程

4 算例分析

在上文物资配送模型中，假设该产品在3个工厂生产，并对4个区域进行产品供应。设F1，F2，F3为所拥有的共 3 个生产工厂，设 R1，R2，R3，R4为其供应共4个区域;设F1，F2，F3的产量分别不大于5 000 个、9 000 个、11 000 个，设R1，R2，R3，R4供应量分别不少于7 000个、6 000个、4 000个、8 000个。并且第i个生产工厂把产品运到第j个区域的单位配送费用为Cij(单位:元 /个)，Cij的设置如表1所示。设Xij为从第i个生产工厂运到第j个区域的产品数量(单位:个)，该物资配送问题的求解目标是实现总配送费用最小化。

表1 单位配送费用 单位:元 /个

现使用粒子群算法进行求解。粒子群算法参数设置如下:wmax=0．95，wmin=0．4，c1=2，c2=2，粒子数为100，预定精度为0．001，最大循环次数为120。采用MATLAB编写程序运行程序，得到最优解即实现总配送费用最小值的方案是:只要从F1配送5 000个产品到R4，从F2配送7 000个产品到R1，从F2配送2 000个产品到R3，从F3配送6 000个产品到R2，从F3配送2 000个产品到R3，从F3配送3 000个产品到R4，就能实现最小总配送费用，即85 000元。并且，本算例在预定循环次数内达到预定精度。

这表明粒子群算法是求解物资配送优化问题的一种可行方法，能很好解决物资配送优化问题。

5 结语

粒子群算法是一种仿生型计算技术，是新兴的人工智能技术，有着高度鲁棒性等优点。本文探索把该算法应用于物资配送优化问题求解，构建了一个物资配送模型，阐述了粒子群算法对于物资配送优化的基本思路和流程，并通过一个实例计算验证。运算结果表明，粒子群算法对于物资配送优化问题求解取得良好效果。把粒子群算法拓展到其他领域，粒子群算法与其他算法结合使用将是未来的研究方向。

［1］耿雪，段会川．改进的最小元素法及其在物资配送问题中的应用［J］．物流工程与管理，2010(6)．

［2］陈城辉，徐永能，杨爱梅，等．遗传算法在多车型军备物资配送路径优化中的应用［J］．四川兵工学报，2010(2)．

［3］宋晓宇，刘锋，常春光．基于广义粗糙集的应急物资调度模型［J］．控制工程，2010(1)．

［4］ 段海滨，张祥银，徐春芳．仿生智能计算［M］．北京:科学出版社，2011．

［5］ 曹承志．人工智能技术［M］．北京:清华大学出版社，2010．

［6］SHI Y H，Eberhart R．A modified particle swarm optimizer［C］．Proceedings of IEEE International Conference On Evolutionary Computation，1998．

［7］Angeline P．Using selection to improve particle swarm optimization［C］．Proceedings of IEEE International Conference On Evolutionary Computation，1998．