改进的粒子群算法在ＶＲＰ中的应用
摘 要：运输调度 问题 在 理论 和实践方面都是一个难题。粒子群算法是一种可以解
决复杂组合优化问题的有效求解算法。提出了改变惯性权重的粒子群算法，并 应用 该
方法 用于求解典型的运输调度问题，结果表明，所提出的方法不仅能得到理想的结果，
而且减少运算时间。∈
关键词：粒子群算法;运输调度;惯性权重∈
中图分类号：O24 文献 标识码：A文章编号：1672-3198（2008）08-0393-02∈∈
1 VRP的数学模型∈
一般运输调度问题的文字描述：已知需求点的位置坐标和货物需求量，一个车队（有
多个车辆）从一个供应点（配送中心）出发，每个需求点只被一辆车访问，且该车所访问
需求点的需求量总和不能超过车辆的负载能力，应如何安排车辆的行走路线使得总路线最
短。要求：每辆车运输完毕后回到出发点（供应点）。设供应点有 K辆车，每辆车的载重
为 Qk（k=1,2…K）,需求点个数为 L，每个需求点的需求量为 qi（i=1,2...,L）;需求点 i
到 j的距离为 qi（i,j=0,1,2...,L,其中 i=0或 j=0表示该点为供应点）；第 k辆车访问
的需求点个数为 nk(nk=0表示未使用第 k辆车)；用集合 Rk表示第 k辆车的行驶路线，
r∈ki∈代表 Rk中一个需求点，它在路线 Rk中的顺序为 i,r∈k0∈表示供应点。借鉴的数
学模型：∈
minZ=∑kk=1∈n∈k-1∈i=0dr∈ki∈r∈k(i+1)∈+d∈r∈kn∈kr∈k0∈∈（1）∈
∑nki=1qrn≤Qk,0≤nk≤L（2）∈
0kk=1nk=L（3）∈
Rk=r∈ki∈｜r∈ki∈∈1,2…，L，
i=1,2 …nk,R∈k1∈∈∩R∈k2∈=∈,∈k1≠k2(4)∈
∈sign∈(nk)=1nk≥1∈0其他(5)∈
其中式（1）为目标函数；式（2）保证每条路径上各需求点需求量之和不超过汽车的
重量并表明每条路径上的需求点数不超过总需求点数；式（3）表明每个需求点都得到配
送服务；式（4）为每条路径的需求点的组成并且限制每个需求点仅能由一辆汽车送货；
式（5）表明当第 K辆汽车服务的客户数大于或等于 1时。该车参加了配送，此时取
∈sign∈(nk)=1,当第 K辆汽车服务的客户数小于 1时，表示未使用该车，取
∈sign∈(nk)=0。∈
上述数学模型的最终优化目标就是：在满足以上各种约束条件的情况下，使得所有车
辆路径之和 Z最小。∈
2 粒子群优化算法∈
标准粒子群算法∈
设在一个 n维的搜索空间中，由 m个粒子组成的种群 X={x1,…x2,…xm}，其中第 i个
粒子位置为 xi=(x∈i1∈,x∈i2∈,…,x∈im∈)T,其速度为
vi=(v∈i1∈,v∈i2∈,…,v∈in∈)T。它的个体极值为
pi=(p∈i1∈,p∈i2∈,…,p∈in∈)T，种群的全局极值为
pg=(p∈g1∈,p∈g2∈,…,p∈gn∈)T。按追随当前最优粒子的原理，粒子 xi将按(6)、
(7)式改变速度和位置。∈
vi∈k+1∈=vik+c1r1(pik-xik)+c2r2(pgk-xik)（6）∈
xi∈k+1∈=xi∈k∈+vi∈k+1∈（7）∈
其中，k为迭代次数，vik及 xik分别为粒子 i在第 k次迭代的速度与位置，而 pik
则是粒子 i在第 k次迭代的自身最佳解，pgk为第 k次迭代的整体最佳解，其更新后粒子
i在第 k+1次迭代的速度为 vi∈k+1∈，xi∈k+1∈则是粒子 i在第 k+1次迭代的位置，r1
、r2为介于 0~1之间的随机数，c1和 c2为 学习 因子，建议将 c1和 c2取值为 2。在上
式中的第二部分被称为粒子本身的认知模式，而第三部分是粒子群中的群体模式。每个粒
子的速度以及移动的位置，均受最大速度 v∈∈max∈∈和最大位置 x∈∈max∈∈的限制
。一旦粒子更新后的速度和位置超出所限定的最大极限时，则需将其分别设定为
v∈∈max∈∈和 x∈∈max∈∈。∈
主要针对速度更新公式(6)中的第一部分，期望给予 vik一个惯性权重 w，测量出粒子
本身搜索最佳解的能力，加入惯性权重 w之后速度更新公式如下所示：∈
vi∈k+1∈=wvik+c1r1pik-xik+c2r2(pgk-xik)（8）∈
式中 w为一常数，为提供各粒子速度 vik的一个移动比例，对于各粒子而言，该权重
可以调整速度 vik的移动速度大小。当惯性权重 w较大时，决定粒子下一次搜索方向的主
要 影响 因素为 vik，所以粒子会呈现较稳定的搜索路径，进而表现出较好的全局搜索特
性。反之，如果惯性权重 w较小时，则会受到 vik、自身最佳解 p∈best∈与整体最佳解
g∈best∈等三种因素的影响，出现搜索路径不稳定的现象，仅能发挥出局部搜索的能力
。∈
改进的粒子群算法∈
为了解决不易选取合理的惯性权重的困难，本文提出将惯性权重以线性递减方式加以
考虑的 方法 ，即将式(8)中的 w由下列式子决定：∈
w=w∈max∈-w∈max∈-w∈min∈k∈max∈×k(9)∈
式中 w∈max∈为使用者设定的惯性权重上限值，w∈min∈为惯性权重下限值，一般惯
性权重 w的范围为 ~。通过添加线性惯性权重使得初始搜索阶段具有较高的惯性权
重值，从而保证搜索初期全局搜索的灵活性，随着迭代过程的进行逐渐降低惯性权重，转
入局部搜索，加强粒子局部搜索能力。∈
为了避免各粒子在使用式(7)后产生过大移动步幅，给各粒子最大移动速度进行限制
，其最大速度 计算 公式如下所示：∈
v∈max∈γ(x∈ub∈-x∈lb∈)(10)∈
式中 x∈ub∈及 x∈lb∈分别为搜索空间中变量的上、下限值，γ式用于取决搜索空
间中最大速度的移动距离。采用最大速度限制加以约束后，使得粒子的搜索效果更好，并
且可以减少不必要的计算时间。∈
改进粒子群算法流程∈
第一步：设定初始值：最大迭代次数 k∈∈max∈∈， 学习 因子 c1、c2，动态周期
递减周期 h，惯性权重以及最大速度动态系数α、β，初始最大速度 v∈∈max∈∈0，γ
，惯性权重上限值 w∈∈max∈∈，惯性权重下限值 w∈∈min∈∈，以及其它初始值。在
搜索空间中，随机产生初始粒子群的速度 v0及位置 x0。∈
第二步：对各粒子进行 分析 计算，根据所设定的目标函数与限制，进一步计算各粒
子的适应值。初始阶段的自身最佳解 pi0即为各粒子的初始解 xi0，而所有粒子自身最佳
解中适应值最好的解即为整体最佳解 pg0。∈
第三步：利用自身最佳解 pik以及整体最佳解 pgk修正各粒子下一次搜索的速度，速
度更新公式如式（8）,其中惯性权重采用动态调整策略。并根据该调整策略更新搜索速度
，进一步更新各粒子的所处位置，其位置更新公式如式（7）所示。∈
第四步：将更新后各粒子的适应值与自身最佳解的适应值进行比较，产生下一次迭代
的自身最佳解 pi∈k+1∈。将整体最佳解与自身最佳解中适应值最佳的解进行比较，一旦
自身最佳解中适应值最好的解优于整体最佳解，则需将下一次迭代的整体最佳解
pg∈k+1∈加以更新。∈
第五步：若经过 h次迭代后，整体最佳解的适应值仍然无法改善，则需根据将惯性权
重和最大速度调整策略进行调整，如式（9）、（10）所示。∈∈
第六步：若是满足终止条件则迭代停止，否则重复第三步，终止条件则是取决于最大
迭代次数 k∈∈max∈∈。
∈
3 实验分析∈
引用一个常用的运输调度 问题 为例来测试算法。有 8个需求点和一个供应点的系统
，各个需求点对应供应点的需求量为 qi(i=1,2,…,8)（单位为 t）。供应点只有两辆车用
于配送，每辆车的载重均为 8吨，已知供应点与各个需求点之间的距离（单位为 km）。算
法由 Matlab 仿真，运行环境为 Pentium 4,，内存为 2G的微机上进行。用 文
献 的遗传算法与本文的改进粒子群算法相比较，两种算法在结论上的差异是很明显的，
另外达到最优路径的迭代时间，改进粒子群算法为 ；遗传算法为 。实验证明
本算法的可行性
