改进的离散粒子群算法在配送问题中的应用

胡 书， 张 莉， 彭文敏 （内江师范学院 数学与信息科学学院，四川 内江 641112）

粒子群算法 （Particle Swarm Optimization，PSO）是由Kennedy和Eberhart[1]等人于1995年提出的一种新的进化计算算法，它来源于鸟类或鱼类觅食过程中迁徙和群集的模拟，是群智能的代表性方法之一。在PSO中，每一个粒子的位置代表问题的一个潜在解，在迭代过程中，每一个粒子跟随代表最优解的个体在解空间中进行搜索，粒子群算法简单容易实现，而且具有比普通遗传算法更高的效率，特别是在连续函数的优化方面，PSO算法表现出非常强的适应性，被广泛研究和采用。

PSO算法发展迅速并取得了可观的研究成果，并且很多学者把粒子群算法用于解决离散问题，如张长胜[2]等人用自适应离散粒子群算法解决TSP问题，程序[3]等人用粒子群算法解决多模式项目再调度问题，这些改进的算法在一定程度上避免了粒子的早熟现象，使粒子尽可能在全局范围内搜索。

针对大多数文章未能将离散粒子群算法的内容描述清楚，本文在文献[4]的基础上对离散粒子群算法的位置和速度的初始化、位置的更新公式进行重新定义，并且保留惯性权值对速度的影响，把粒子的解储存为数组形式，增加群体相似度和排斥算子来让粒子跳出局部最优。

配送问题是如何合理优化配送资源，以最低的成本、最快的速度完成配送任务，也是任何一个现代物流企业的核心目标之一，优化配送方案不仅可以降低商品的流通费用，提高企业的利润源泉，而且对工作效率也会产生很大的促进作用，于是在此设计了用离散粒子群算法解决配送问题的算法步骤，并用matlab7.0编程仿真，仿真结果表明改进的离散粒子群算法能够找到更好的解，并且收敛速度快，在一定程度上避免了陷入局部最优。

1 改进的离散粒子群算法

1.1 粒子群算法原理

粒子群算法中的每个粒子代表一个解，每个粒子都有一个由优化函数决定的适应度，以评价该粒子当前位置的优劣。同时，每个粒子都有一个速度来决定它移动的方向和距离，然后粒子们追随当前的最优粒子在解空间中进行搜索，粒子群算法初始化为一群随机粒子 （随机解），然后通过如下迭代公式迭代找到最优解：

其中w为加权系数，表示历史速度对当前速度的影响，c1,c2是学习因子，分别表示粒子受群体认识和个体认识的影响程度，rand1（），rand2（）是0～1区间上的随机数，表示群体认识或个体认识对粒子的影响具有随机性。在每一次迭代中，粒子通过跟踪两个 “极值”来更新自己，一个是粒子本身所找到的最优解，即个体极值；另一个极值是整个种群目前找到的最优解，即全局极值。

1.2 改进的离散粒子群算法

在钟一文[4]等人提出的离散粒子群优化算法的基础上，对离散对粒子的位置和速度的初始化、位置的更新公式进行重新定义，并且保留了惯性权值的作用，最后定义群体相似度来让粒子跳出局部最优，部分定义如下。

1.2.1 初始化粒子的位置和速度

粒子的位置X用一个由点组成的表来表示，它是一个N维向量，在X中，第i维数据表示第i次访问地点xi，位置X表示为：X=（x1,x2,…,xN），其中N为地点数，按照数组X依次访问每个地点，最终形成一个回路的TSP问题。

在粒子的初始位置形成的基础上，以一定的概率取初始位置上的部分点作为粒子的初始速度，即对第i维上的点xi，随机产生一个0～1之间的数，如果这个数小于预先给定的常数c，则将此xi保留为速度vi，否则速度vi值为0，每一维速度vi表示为

速度V表示为：V=（v1,v2,…,vN），其中N为地点数。

1.2.2 位置与速度的加法

位置与速度相加，使粒子到达一个新的状态，即得到新的位置，对第i维上的位置xi和速度vi，如果速度vi为0或者与xi相同，则不改变位置X的第i维上的数，否则将速度vi插入到位置X的第i维上，而X的第i维及其以后的数依次向后移动一个单位，并且原位置X上与vi相同的那一维的数值为空，于是得到新的位置，即

1.2.3 排斥算子

为了避免粒子在搜索过程中出现早熟现象，于是引入排斥算子增加粒子的多样性，当粒子的群体相似度大于某一给定的阀值c时，表明粒子群在靠拢，为了避免早熟，于是启用排斥算子 （阀值c越大，表明粒子靠得越拢才启用排斥算子），即以一定的概率随机产生一个新的速度，并将速度作用在当前位置上得到新的位置。这里可用初始化粒子速度的方法产生新的速度，用位置与速度的加法来更新位置。

1.2.4 定义粒子的群体相似度

由于粒子在寻找最优解的过程中是以群体合作为前提的，因此以整个群体的相似度判断粒子是否陷入局部最优。首先求出任意两个粒子Xi和Xj的相似度Si,j[4]，然后把整个粒子群中任意两个粒子Xi和Xj的相似度Si,j的平均值作为粒子的群体相似度d，即

其中M表示粒子数，d的值仍在0～1之间。

1.2.5 离散粒子群算法

离散粒子群算法保留了惯性项的作用，在这里惯性权值w取常数，并且在定义常数与速度的乘法时引入了随机项，于是把c1×rand1（）和c2×rand2（）合并为常数c1和c2，于是离散粒子群算法定义为

2 配送问题描述

货物的配送是由中心仓库运到子库，再由子库的车辆运到多个零售点 （需求点）。从中心仓库到子库的配送安排可以按运筹学中的一般运输问题解决，配送中心要向整个区域内的各个地点送货，而且客户的数量、频率和方向具有不确定性。配送问题的数学模型为[5]：

约束条件为：

式中，m——配送中心拥有的车辆台数，Wk——车辆的载重量，n——客户需求点数，Ri——需求点的需货量，Lk——每辆车每日最大运行距离，di,j（i=1,2,…,n-1;j=1,2,…,n;i＜j,i=0表示配送中心）——配送中心到各需求点的距离及需求点之间的距离。

约束条件 （1）表示每辆车辆所运送的货物量不超出其载重量；约束条件 （4）表示若客户点i由车辆k送货，则车辆k送完该点的货后必到达另一个点j；约束条件 （5）表示每条线路距离不大于车辆的最大运行距离为Lk；约束条件 （6）表示需求点i由车辆k送货时，Yi,k=1；否则Yi,k=0；约束条件 （7）表示第k辆车从点i到点j时，Xi,j,k=1；否则Xi,j,k=0。

3 离散粒子群算法流程

配送问题属于多约束TSP问题，而离散粒子群算法可用于解决TSP问题，并且运算速度快，能够找到比一般算法更好的解，于是设计了用离散粒子群算法解决配送问题的算法流程。

4 实验仿真及结果分析

根据参考文献[5]，利用K-means聚类方法，将配送问题中的路径分为两类，于是转化为了TSP问题，并且配送中心坐标为 （0.4291,0.2354 ）。其余客户的坐标如下表所示。

利用改进的离散粒子群算法对以上数据进行仿真，其中惯性权值w取0.4，系数c1取0.2，c2取0.3，阀值c取0.4，在matlab7.0环境下，用10个粒子，迭代100次，仿真结果如下图：

与其它算法的结果进行比较，表明本算法能够找到更好的解，并且运算速度很快，不到两秒便可计算出这两个回路，结果如下表：

5 结束语

本文在参考文献[4]的前提下对粒子群算法进行重新定义和部分修改，得出改进的离散粒子群算法，并且在配送问题中，以最低的成本、最快的速度完成配送任务是任何一个现代物流企业的核心目标之一，因此很有必要对配送问题进行优化。于是设计了用改进的离散粒子群算法解决配送问题的算法流程，并用matlab7.0对它进行仿真，结果表明离散粒子群算法比其他算法找到的解更好，并且运算速度快。

[1] Keedny J,Eberhart R C.Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks.Perth,Australia:IEEE Press,1995:1942-1948.

[2] 张长胜，孙吉贵，欧阳丹彤.一种自适应离散粒子群算法及其应用研究[J].电子学报，2009(2):299-304.

[3] 程序，吴澄.粒子群优化算法求解多模式项目再调度问题[J].计算机集成制造系统，2009,15(1):97-101.

[4] 钟一文，杨建刚，宁正元.求解TSP问题的离散粒子群优化算法[J].系统工程理论与实践，2006(6):88-94.

[5] 王晓博，李一军.面向电子商务的协同配送路线优化研究[J].计算机工程与应用，2007,43(8):184-186,196.

[6] 田谦益，何田中.粒子群算法在PERT网络优化问题中的应用[J].计算机工程与科学，2008,30(9):58-59,72.