改进的粒子群算法在ＶＲＰ中的应用

摘 要：运输调度 问题 在 理论 和实践方面都是一个难题。粒子群算法是一种可以解决复杂组合优化问题的有效求解算法。提出了改变惯性权重的粒子群算法，并 应用 该 方法 用于求解典型的运输调度问题，结果表明，所提出的方法不仅能得到理想的结果，而且减少运算时间。

关键词：粒子群算法;运输调度;惯性权重

1 VRP的数学模型

minZ=∑kk=1nk-1i=0drkirk+drknkrk0

（1） 0kk=1nk=L

（3） sign=1nk≥10其他

 上述数学模型的最终优化目标就是：在满足以上各种约束条件的情况下，使得所有车辆路径之和Z最小。

2 粒子群优化算法

2.1 标准粒子群算法 vik+1=vik+c1r1+c2r2

（6）

xik유+1=xik+vik+1

（7） 主要针对速度更新公式

中的第一部分，期望给予vik一个惯性权重w，测量出粒子本身搜索最佳解的能力，加入惯性权重w之后速度更新公式如下所示： 式中w为一常数，为提供各粒子速度vik的一个移动比例，对于各粒子而言，该权重可以调整速度vik的移动速度大小。当惯性权重w较大时，决定粒子下一次搜索方向的主要 影响 因素为vik，所以粒子会呈现较稳定的搜索路径，进而表现出较好的全局搜索特性。反之，如果惯性权重w较小时，则会受到vik、自身最佳解pbest与整体最佳解gbest等三种因素的影响，出现搜索。路径不稳定的现象，仅能发挥出局部搜索的能力。

2.2 改进的粒子群算法

为了解决不易选取合理的惯性权重的困难，本文提出将惯性权重以线性递减方式加以考虑的 方法 ，即将式

中的w由下列式子决定：

w=wmax-wmax-wminkmax×k



式中wmax为使用者设定的惯性权重上限值，wmin为惯性权重下限值，一般惯性权重w的范围为0.8~1.4。通过添加线性ฑ惯性权重使得初始搜索阶段具有较高的惯性权重值，从而保证搜索初期全局搜索的灵活性，随着迭代过程的进行逐渐降低惯性权重，转入局部搜索，加强粒子局部搜索能力。

为了避免各粒子在使用式

后产生过大移动步幅，给各粒子最大移动速度进行限制，其最大速度 计算 公式如下所示：

v☢maxγ



式中xub及xlb分别为搜索空间中变量的上、下限值，γ式用于取决搜索空间中最大速度的移动距离。采用最大速度限制加以约束后，使得粒子的搜索效果更好，并且可以减少不必要的计算时间。

2.3 改进粒子群算法流程 第二步：对各粒子进行 分析 计算，根据所设定的目标函数与限制，进一步计算各粒子的适应值。初始阶段的自身最佳解pi0即为各粒子的初始解xi0，而所有粒子自身最佳解中适应值最好的解即为整体最佳解pg0。

第三步：利用自身最佳解pik以及整体最佳解pgk修正各粒子下一次搜索的速度，速度更新公式如式

（8）,其中惯性权重采用动态调整策略。并根据该调整策略更新搜索速度，进一☤步更新各粒子的所处位置，其位置更新公式如式

（7）所示。

第四步：将更新后各粒子的适应值与自身最佳解的适应值进行比较，产生下一次迭代的自身最佳解pik+1。将整体最佳解与自身最佳解中适应值最佳的解进行比较，一旦自身最佳解中适应值最好的解优于整体最佳解，则需将下一次迭代的整体最佳解pgk+1加以更新。

第五步：若经过h次迭代后，整体最佳解的适应值仍然无法改善，则需根据将惯性权重和最大速度调整策略进行调整，如式

（9）、

（10）所示。

第六步：若是满足终止条件则迭代停止，否则重复第三步，终止条件则是取决于最大迭代次数kmax。



3 实验分析

引用一个常用的运输调度 问题 为例来测试算法。有8个需求点和一个供应点的系统，各个需求点对应供应点的需求量为qi（单位为t）。供应点只有两辆车用于配送，每辆车的载重均为8吨，已知供应点与各个需求点之间的距离（单位为km）。算法由Matlab 7.1仿真，运行环境为Pentium 4,2.0GHZ，内存为2G的微机上进行。用 文献 的遗传算法与本文的改进粒子群算法相比较，两种算法在结论上的差异是很明显的，另外达到最优路径的迭代时间，改进粒子群算法为4.52S ；遗传算法为5.68S。实验证明本算法的可行性。