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

1、车辆调度问题的全局局部最优信息比粒子群算法研究摘要文章提出了一种新的改进标准粒子群算法即全局局部最优信息比粒子群算法。该算法与标准粒子群算法和全局局部最优最小值粒子群优化算法作了比较，仿真实验结果表明，该算法在收敛速度、解的质量和鲁棒性上都表现出了较优的性能，是求解车辆调度问题的一种较好方法。 关键词车辆调度问题；粒子群算法；全局局部最优信息比；数学模型 1 引 言 近年来，研究者们先后将一般启发式算法和智能化启发式算法用于车辆调度问题，取得了一些较好的效果。1粒子群算法（Particle Swarm Optimization，PSO）是一种模拟鸟群飞行的仿生算法，有着个体数目少、计算简单、鲁

2、棒性好等优点。2 2 车辆调度问题（VRP）的描述及数学模型 VRP 描述为：有一个配送中心 0，配送车辆 K 辆和货运点个 N，每辆车的载重量为 qi，各个送货点的需求量为 gi，且 maxqimaxgi，把货物配送到 N 个送货点，使车辆调度问题的目标函数达到最小。 式（3）为目标函数：车辆行驶的总路径最小；式（4）：每条线路上配送点需求量之和不超过最大载重量；式（5）：每个配送点仅被访问一次；式（6） （7）：每个送货点的需求量只能由一辆车完成；式（8）（9）：变量取值范围；式（10）：支路消去约束。该问题在约束条件下，使所有车辆的总路径最小。 3 粒子群算法及其改进 3.1 粒子群算法

3、 PSO 算法初始化粒子群，在迭代过程中，粒子将跟踪个体极值 pbest和全局极值 gbest 来更新下一时刻的位置，设搜索空间为 D 维，总粒子数为 n，粒子 i 在 t 时刻的位置为： 3.2 改进的粒子群算法 粒子群算法参数的设置对算法的寻优性能起着重要的作用。全局局部最优最小值粒子群算法（GLBest-PSO）对标准 PSO 进行了改进，即：4 车辆调度问题的 GLIR-PSO 算法 4.1 问题的编码与解码 实现该算法的关键问题之一是找到一种合适的表达方法，使粒子与解对应。本文根据文献3的思路，将车辆和对应的送货点的顺序表示出来。对于 N 个送货点的 VRP 问题，每个送货点对应两个

4、属性：完成该配送任务的车辆号 k 和在车辆中的配送顺序 r，每个粒子对应的 2N 维向量被分解为两个 N 维向量：Xk 和 Xr，其中 Xk 表示各配送点的车辆编号，Xr 表示各配送点对应的配送顺序。速度向量 V 对应的被分解为 Vk 和Vr。 假设有 7 个送货点的 VRP 问题，所需车辆数为 3，编码过程如表 1 所示。 这种编码方式使得每个配送点都能得到服务并且每个送货点的需求量只能由一辆车完成，粒子更新的方式简单、易懂，求解过程的计算量大大减少。 4.2 GLIR-PSO 算法实现过程 粒子群算法的具体实现步骤如下： 步骤 1：初始化粒子群。 初始化种群规模 P，粒子维数 2N，w，c

5、1，c2，最大迭代次数 Loop count； 初始化 Xk 和 Xr，使其分别属于 1K 的随机整数和 1L 的随机实数；初始化 Vk 和 Vr 的分量，使其分别属于-（K-1）（K-1）的随机整数和-（L-1）（L-1）的随机实数； 用评价函数 Eval 评价所有粒子的适应度，若不满足约束条件则令f=fmax，fmax 是一个很大的数； 初始评价值作为每个粒子的局部极值，最优的初始评价值作为全局极值。 步骤 2：更新位置、速度，并输出优化结果。 按式（15）计算 Vk 和 Vr，按式（12）计算 Xk 和 Xr，如果超过边界值则取边界值； 用 Eval 评价所有粒子的适应度； 更新局部极值

6、和全局极值，若某粒子当前的位置优于 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

7、.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 的最短路径的方差小于

8、 BPSO 和 GLBest-PSO 算法所得结果（137.12645 和 86.28476） ，其最短路径的方差为61.11745，比 BPSO 和 GLBest-PSO 算法的结果小 55.4%和 29.2%，所以GLIR-PSO 算法在解的鲁棒性上表现出了较优的性能。以上结论在表 4 中显示： 通过上述仿真实验有效地验证了这种新的改进算法GLIR-PSO 算法，有效地避免了标准粒子群算法的“趋同性” ，确保正确的搜索方向，且持续地找到全局最优解。 6 结 论 目前，虽然车辆调度系统已在国内一些领域得到初步应用，但发展很不成熟，存在算法复杂和运行不稳定等缺陷，针对此现状，本文提出一种新型的

9、 GLIR-PSO 算法以有效提高车辆调度系统运行的效率性和稳定性，将全局和局部最优信息比引入到算法的更新过程，来对标准粒子群算法进行有效改进，该新型算法有效克服了早熟收敛现象，在收敛速度、解的质量和鲁棒性上都表现出了较优的性能。 参考文献： 1李军，郭耀煌.物流配送车辆优化调度理论与方法M.北京： 中国物资出版社，2001：76-77. 2Kennedy J，Eberhart R C.Particle swarm optimizationC/Proc.IEEE international conference on neural networks，IV.Piscataway，NJ： IEEE service center，1995： 1942-1948. 3Salmen A，Ahmad I，Al-Madani S.Particle swarm optimization for task assignment problemJ.Microprocessors and microsystems，2002（26）： 367-371. 4李宁，邹彤，孙德宝.带时间窗车辆路径问题的粒子群算法J.系统工程理论与实践，2004，4（4）： 130-135.