基于粒子碰撞的粒子群算法求解带时间窗车辆调度问题.pdf

《基于粒子碰撞的粒子群算法求解带时间窗车辆调度问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第29卷第4期2012年4月计算机应用研究ApplicationResearchofComputersV01．29No．4Apr．2012基于粒子碰撞的粒子群算法求解带时间窗车辆调度问题：秦家娇1，张勇2，毛剑琳1，付丽霞1(1．昆明理工大学信息工程与自动化学院，昆明650500；2．昆明理工大学津桥学院，昆明650106)摘要：带时间窗车辆调度问题属于离散NP—hard组合优化问题．传统的粒子群算法在离散域上表现了一定的劣性，对此提出了一种基于粒子碰撞的离散PSO算法来求解该问题。受物体相互碰撞之后物体的速度和位置会发生改变的现象启发，使当前粒子与个体最

2、优和全局最优粒子发生碰撞来更新粒子的位置，以避免传统更新操作中的取整，保证种群的进化能力。采用Solomon’sVRP标准问题集的实例来对算法进行测试，实验结果数据表明了该算法的有效性。关键词：带时间窗车辆调度问题；粒子碰撞；离散粒子群算法中图分类号：TP301文献标志码：A文章编号：1001-3695(-2012)04·1253·03doi：10．3969／j．issn．100l-3695．2012．04．014BasedonparticlescollisionPS0forvehicleroutingoroblemwithtimewindowsQINJi

3、a-jia01，ZHANG'ton∥，MAOJian·linl，FULi—xial(1．SchoolofInformationEngineering&Automation，KunmingUnivers蚵ofScience&Technology，Kunmi昭650500，China；2．SchoolofJinqiao，KunmingUniters酊ofScience＆Technology，Kunming650106，China)Abstract：Thevehicleroutingproblemwithtimewindows(VRPTW)istheNP—har

4、dcombinatorialoptimizationdiscreteprob—lem．TherewascertaininferiorityperformanceonsolvingitwithtraditionalPSO。80thispaperproposedaparticlescollisiondiscretePSOtosolveit．Inspiredbythephysicalphenomenaofthevelocityandpositionchangedafterobjectscollision。itmadethecurrentparticlecolli

5、dedwiththepersonalbestparticleanddobalbestparticletoavoidthetraditionroundingoperatinginupdating．andkeptparticlesswarlTIevolutionalcapabihty．ItusedtheSolomon’sVRPinstancetotest．Theresultsofexpori-mentsshowthatthealgorithmhasgoodperformance．Keywords：vehicleroutingproblemwithtimewin

6、dows(VRm7)；particlescollision；discretePSO0引言当前，物流的现代化水平不仅成为反映一个国家现代化程度和综合国力的重要标志，也成为城市经济发展水平的体现。车辆配送是物流的重要组成部分，国外将该问题归结为VRP(vehicleroutingproblem)，于1959年由Dantig和Ramser提出。该问题是物流系统优化的关键。带时间窗车辆调度问题(vehicleroutingproblemwithtimewindows，VRPTW)是由VRP衍生出来的一种问题类型，它是在基本VRP的约束条件的基础上增加了每个客户要求

7、被服务的时间范围限制，提前或者是拖后服务则客户将拒绝接受服务，这样更贴近现实的应用。粒子群算法是对鸟群觅食过程中的迁徙聚集的模拟，其概念简单易懂，易于计算机编程实现而广泛应用于组合优化问题。目前在用PSO求解VRFI'W的文献中，有两种方法对粒子的速度和位置进行更新：a)进行取整操作；b)基于交换原理更新粒子。文献[1]采用双层的二维粒子编码，一层从1到车辆数的可重复自然数表示任务对应的车辆编号，二层从1到客户数的可重复自然数表示任务在对应的车．辆路径中的执行次序，每次通过速度和位置更新公式得到新的粒子的位置和速度都需要进行取整和按边界取值操作，以符合编码

8、原理。文献[2]的编码方式与文献[1]不同，但是原理一致，对更新得