车辆调度问题的全局—局部最优信息比粒子群算法研究

朱婷婷　单小红

[摘要]文章提出了一种新的改进标准粒子群算法即全局—局部最优信息比粒子群算法。该算法与标准粒子群算法和全局—局部最优最小值粒子群优化算法作了比较，仿真实验结果表明，该算法在收敛速度、解的质量和鲁棒性上都表现出了较优的性能，是求解车辆调度问题的一种较好方法。

[关键词]车辆调度问题；粒子群算法；全局—局部最优信息比；数学模型

1 引 言

近年来，研究者们先后将一般启发式算法和智能化启发式算法用于车辆调度问题，取得了一些较好的效果。[1]粒子群算法（Particle Swarm Optimization，PSO）是一种模拟鸟群飞行的仿生算法，有着个体数目少、计算简单、鲁棒性好等优点。[2]

2 车辆调度问题（VRP）的描述及数学模型

VRP描述为：有一个配送中心0，配送车辆K辆和货运点个N，每辆车的载重量为qi，各个送货点的需求量为gi，且maxqi≤maxgi，把货物配送到N个送货点，使车辆调度问题的目标函数达到最小。

式（3）为目标函数：车辆行驶的总路径最小；式（4）：每条线路上配送点需求量之和不超过最大载重量；式（5）：每个配送点仅被访问一次；式（6）（7）：每个送货点的需求量只能由一辆车完成；式（8）（9）：变量取值范围；式（10）：支路消去约束。该问题在约束条件下，使所有车辆的总路径最小。

3 粒子群算法及其改进

3.1 粒子群算法

PSO算法初始化粒子群，在迭代过程中，粒子将跟踪个体极值pbest和全局极值gbest来更新下一时刻的位置，设搜索空间为D维，总粒子数为n，粒子i在t时刻的位置为：

3.2 改进的粒子群算法

粒子群算法参数的设置对算法的寻优性能起着重要的作用。全局—局部最优最小值粒子群算法（GLBest-PSO）对标准PSO进行了改进，即：

4 车辆调度问题的GLIR-PSO算法

4.1 问题的编码与解码

实现该算法的关键问题之一是找到一种合适的表达方法，使粒子与解对应。本文根据文献[3]的思路，将车辆和对应的送货点的顺序表示出来。对于N个送货点的VRP问题，每个送货点对应两个属性：完成该配送任务的车辆号k和在车辆中的配送顺序r，每个粒子对应的2N维向量被分解为两个N维向量：Xk和Xr，其中Xk表示各配送点的车辆编号，Xr表示各配送点对应的配送顺序。速度向量V对应的被分解为Vk和Vr。

假设有7个送货点的VRP问题，所需车辆数为3，编码过程如表1所示。

这种编码方式使得每个配送点都能得到服务并且每个送货点的需求量只能由一辆车完成，粒子更新的方式简单、易懂，求解过程的计算量大大减少。

4.2 GLIR-PSO算法实现过程

粒子群算法的具体实现步骤如下：

步骤1：初始化粒子群。

①初始化种群规模P，粒子维数2N，w，c1，c2，最大迭代次数Loop count；

②初始化Xk和Xr，使其分别属于1～K的随机整数和1～L的随机实数；初始化Vk和Vr的分量，使其分别属于-（K-1）～（K-1）的随机整数和-（L-1）～（L-1）的随机实数；

③用评价函数Eval评价所有粒子的适应度，若不满足约束条件则令f=fmax，fmax是一个很大的数；

④初始评价值作为每个粒子的局部极值，最优的初始评价值作为全局极值。

步骤2：更新位置、速度，并输出优化结果。

①按式（15）计算Vk和Vr，按式（12）计算Xk和Xr，如果超过边界值则取边界值；

②用Eval评价所有粒子的适应度；

③更新局部极值和全局极值，若某粒子当前的位置优于pbest，则更新pbest，若粒子群的当前位置优于gbest，则更新gbest；

④若满足终止条件，输出gbest；否则返回①。

5 仿真实验结果与分析

现有一个配送中心，7个送货点，设所有车辆的最大装载量为1t，需求量矩阵为P=[0.89，0.14，0.28，0.33，0.21，0.41，0.57]，距离矩阵如表2所示。

使用Matlab7.0编程，参数设置：P=30，2N=14，wstar=0.9，wend=0.4，c1=c2=2，Loopcount=500，惩罚因子R=100000，最终由3辆车完成配送任务，并且最短总路径为217.81。车辆最优调度方案如表3所示。

本文将 GLIR-PSO算法与BPSO和GLBest-PSO进行仿真实验，并对优化结果进行比较。每种算法依次运行20次，其中，GLIR-PSO有13次搜索到最优解，而BPSO和GLBest-PSO分别只有11次和10次，并且GLIR-PSO的20次实验平均路径252.73km优于BPSO和GLBest-PSO算法所得结果（304.96km和276.44km），说明GLIR-PSO算法解的质量在一定程度上得到了提高，收敛速度变快。

在20次实验中，GLIR-PSO的最短路径的方差小于BPSO和GLBest-PSO算法所得结果（137.12645和86.28476），其最短路径的方差为61.11745，比BPSO和GLBest-PSO算法的结果小55.4%和29.2%，所以GLIR-PSO算法在解的鲁棒性上表现出了较优的性能。以上结论在表4中显示：

通过上述仿真实验有效地验证了这种新的改进算法——GLIR-PSO算法，有效地避免了标准粒子群算法的“趋同性”，确保正确的搜索方向，且持续地找到全局最优解。

6 结 论

目前，虽然车辆调度系统已在国内一些领域得到初步应用，但发展很不成熟，存在算法复杂和运行不稳定等缺陷，针对此现状，本文提出一种新型的GLIR-PSO算法以有效提高车辆调度系统运行的效率性和稳定性，将全局和局部最优信息比引入到算法的更新过程，来对标准粒子群算法进行有效改进，该新型算法有效克服了早熟收敛现象，在收敛速度、解的质量和鲁棒性上都表现出了较优的性能。

参考文献：

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

[2]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proc.IEEE international conference on neural networks，IV.Piscataway，NJ： IEEE service center，1995： 1942-1948.

[3]Salmen A，Ahmad I，Al-Madani S.Particle swarm optimization for task assignment problem[J].Microprocessors and microsystems，2002（26）： 367-371.

[4]李宁，邹彤，孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践，2004，4（4）： 130-135.