PSO算法在有时间窗的车辆路径中应用.pdfVIP

PS0算法在有时间窗的车辆路径中的应用 杨志鹏 PSO算法在有时间窗的车辆路径中的应用 杨志鹏 摘要：由于VRPTW问题是许多分配和运输系统中的典型部分，因此有时间窗的车辆路径问题在当今的工业中 至关重要。本文介绍了一种启发式的粒子群算法(PSO)来处理带时间窗的车辆路径问题，并提出了一 种新的粒子群算法速度公式。通过应用MATLAB软件对典型的带时间窗的车辆路径问题的范例进行的实 验，表明该改进的粒子群算法可以有效解决带时间窗的车辆路径问题，为此被证明为处理该类问题的有 效方法。推广到实际的城市轨道交通建设中，具有现实意义。 关键词：PSO粒子群算法；有时间窗的车辆路径；VRPTW；Ⅵ诤；MATLAB；城市轨道交通 1引言 1．1车辆路径(VRP)类型问题描述 车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用 的广泛性和经济上的重大价值，受到国内外学者的广泛关注。车辆路线问题的图形表示可以描述 为图1所示。 设有一个场站，共有M辆货车，车辆容量为Q， 问题(VRPTW)。 有N位顾客，每位顾客有其需求量D。车辆从场站出 ／＼需求点 Z—j 发对客户进行配送服务最后返回场站，要求所有顾 客都被配送，每位顾客一次配送完成，且不能违反 车辆容量的限制，目的是所有车辆路线的总距离最 小。车辆路线的实际问题包括配送中心配送、公共 汽车路线制定、信件和报纸投递、航空和铁路时间 表安排、工业废品收集等，这些问题均可以提出与 车辆路径问题近似的数学模型。 由于VRP问题的持续发展，考虑需求点对车辆 到达的时间有所要求外，在车辆路径问题之中加入时 图1 VRP示意图 间窗的限制，便成为有时间窗的车辆路径。 有时间窗的车辆路径问题(VRPTW)是在车辆路径问题(Ⅵ心)上加上了客户的被访问的 时间窗约束。在VRPTW问题中，除了VRP问题考虑的行驶成本之外，成本函数还要包括由于 J。 提前到达某个客户点而引起的等待时间和客户需要的服务时间【1 1．2粒子群算法(PSO) 粒子群优化算法(PSO)又称为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟 群觅食行为而发展起来的一种基于群体协作的随机有哪些信誉好的足球投注网站算法。通常认为它是群集智能(sI)的一 作者简介：杨志鹏，北京交通大学电气工程学院，硕士研究生，北京：100044，电话：010 邮箱：．yzpee@1 26,con一= ．183． 城市轨道交通供电系统新技术年会 论文集 学家Kennedy博士发明的。 PSO算法初始化为一群随机粒子(随机解)，然后通过迭代找到最优解，在每一次迭代中，粒 子通过跟踪2个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解称为个体极 值pBest；另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不 用整个种群而只用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。 在找到这2个最优值时， 粒子根据如下公式来更新自己的速度和新的位置： v=v+c (1) present[]=present[]+v[】 (2) 式中 v_粒子的速度； present[】——当前粒子的位置； 0是介于(0，1)之间的随机数； pBest、gBest如前定义rand c1、c2——学习因子，通常el=e2=2。 PSO算法程序的伪代码为： Foreach