多车场车辆路径问题的改进粒子群算法

《多车场车辆路径问题的改进粒子群算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerEngineeringandApplications计算机工程与应用5多车场车辆路径问题的改进粒子群算法王铁君，邬开俊WANGTiejun．wuKaijun1．西北民族大学数学与计算机科学学院，兰州7300302．兰州交通大学电子与信息工程学院，兰州7300701．SchoolofMathematicsandComputerScience，NorthwestUniversityforNationalities，Lanzhou730030，China2．SchoolofElectronicandInformationEngin

2、eering，LanzhouJiaotongUniversity，Lanzhou730070，ChinaWANGTiejun．wUKaijun．Studyonmulti-depotsvehicleroutingproblembasedonimprovedparticleswarmoptimiza—tion．ComputerEngineeringandApplications，2013，49(2)：5-8．Abstract：Multi—DepotsVehicleRoutingProblem(MDVRP)isakindofNPcombinati

3、onproblemwhichpossessesimportantpracticalvalue．InordertoovercomePSO’Sprematureandslowconvergence，anewimprovedalgorithmisputforward，itadoptsCO—evolutionarythoughtandatthesametimepatternsearchmethodisintroducedwhilethesearchfallingintolocalopti-mum．Inthispaper,akindofnewpart

4、iclescodingmethodisconstructedandthesolutionalgorithmisdeveloped．Thesimula-tionresultsshowthatthealgorithmhasbetteroptimalspeedandoptimaleficiencythanGAandPSO，SOitprovesthealgorithmusedtooptimizeMDVRPisfeasibleandeffective．Keywords：vehicleroutingproblem；multi—depots；patter

5、nsearch；ParticleSwarmOptimization(PSO)：CO—evolutionary摘要：多车场车辆路径问题是一类实用性很高的NP难解问题。针对标准粒子群算法易早熟、收敛速度慢的缺陷，提出了一种新的改进算法，该算法采用协同进化思想，同时在搜索陷入局部最优的情况下引入了模式搜索方法。针对多车场车辆路径问题构造了一种新的粒子编码方法，建立了相应的数学模型，并介绍了该算法的详细实现过程。仿真结果通过和遗传算法和标准粒子群算法比较，表明该算法具有更好的寻优速度和寻优效率，从而证明了提出的算法用于优化多车场车辆路径问题是可行和

6、有效的。关键词：车辆路径问题；多车场；模式搜索；粒子群优化；协同进化文献标志码：A中图分类号：TP301．6doi：10．3778／j．issn．1002—8331．1207．0355车辆路径问题(VehicleRoutingProblem，VRP)是长、易于陷入局部最优解等问题。因此如何针对多车场车Dantzigz和RamserJ于1959年首次提出⋯，是指对一系列辆路径问题的特点，构造运算简单，寻优效果优异的启发发货点(或收货点)组织适当的行车路线，要求在满足一定式优化算法，对许多可转化为多车场车辆路径问题求解的约束条件前提下，达到一定

7、的目标(诸如费用最小、路程最组合优化问题具有十分重要的意义。短、消耗时间最少等)。粒子群算法(PSO)是新近出现的一种模仿鸟群找食飞由于VRP已被证明是一个NP完全问题，而多车场车行的仿生算法，有着个体数目少、计算简单、收敛速度快、辆路径问题(Multiple—DepotVehicleRoutingProblem，易于实现等优点，在车辆路径优化问题中已得到应用，MDVRP)是基本车辆路径问题的延伸，它的实现比VRP问取得了非常不错的效果，但由于粒子群算法易于停滞、易题更加复杂。只有在问题规模较小时才有可能求得其精陷入局部最优等问题，故本文将

8、粒子群算法和协同进化思确解，尤其对于大维数问题，很难求得最优解。近年来，遗想结合起来，并将模式搜索方法嵌入粒子群算法中，提出传算法、蚁群算法等启发式优化算法在解决这一类问题中一种