带时间窗的多车场车辆路径优化的粒子群算法.pdf

《带时间窗的多车场车辆路径优化的粒子群算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerEngineeringandApplications计算机工程与应用带时间窗的多车场车辆路径优化的粒子群算法王铁君1，邬开俊2WANGTieiunl．WUKaiiun21．西北民族大学数学与计算机科学学院，兰州7300302．兰州交通大学电子与信息工程学院，兰州7300701．SchoolofMathematicsandScience，NorthwestUniversityforNationalities，Lanzhou730030，China2．SchoolofElectronicandInformationEngineering，LanzhouJiaoton

2、gUnversity,Lanzhou730070，ChinaWANGTiejun．WUKaijun．Studyonmulti-depotvehicleroutingproblemwithtimewindowsbasedonParti—cleSwarmOptimization．ComputerEngineeringandApplications，2012，48(27)：27-30．Abstract：Multi--depotvehicleroutingproblemwithtimewindowsisavariationofthevehicleroutingproblemcon-·s

3、trainedbymulti—depotandtimewindows，whichisatypicalNP—hardproblem．Particleswarmoptimizationwithaparticlecodingmethodisdesignedtosolvetheproblem．Themathematicmodeisestablishedandthesolutionalgo—rithmisdeveloped．Thesimulationresultsofexampleindicatethatthealgorithmhasfastersearchspeedandstron—g

4、eroptimizationabilitythantheGAandACO．Keywords：timewindows；multi—depot；vehicleroutingproblem；ParticleSwarmOptimization(PSO)摘要：带时间窗的多车场车辆路径问题在基本车辆路径问题的基础上增加了“多车场”与“时间窗”两个约束条件，是一个典型的NP难解问题。将粒子群算法应用于带时间窗的多车场车辆路径优化问题，构造了一种适用于求解车辆路径问题的粒子编码方法，建立了相应的数学模型，在此基础上设计了相应的算法。算例通过和遗传算法、蚁群算法进行比较，证明了其搜索速度和寻优能

5、力的优越性。关键词：时间窗；多车场；车辆路径优化；粒子群算法文章编号：1002—8331(2012)27—0027—04文献标识码：A中图分类号：TP301车辆路径问题(VehicleRoutingProblem，VRP)是DantzigZ和RamserJ于1959年首次提出”1，它一般定义为：根据已知的需要服务客户点，组成适当的行车路线，使车辆依次地通过它们，满足以下约束条件：货物的需求量、车辆容量、运行时间、行驶里程，并达到一定目标：费用最少、行驶路程最短、时间尽量少、需要的车辆尽量少等。现实中许多的物流车辆优化问题都可以归结为带时问窗的多车场车辆路径问题。需要以最小的路径

6、成本将指定数量的货物在要求的时间范围内送达客户点，并最后返回车场。尽管该问题的应用已非常广泛，但该问题在理论研究中尚未得到很好的解决。“多车场”与“时间窗”这两个分别在问题的空间与时间方面施加的约束条件，使原本就具有NP复杂性的问题的求解具备了更加复杂的难度，只有在问题规模较小时才有可能求得其精确解，尤其对于大维数问题，很难求得最优解。近年来，遗传算法、蚁群算法等启发式优化算法在解决这一类问题中得到了初步的应用口卅，但是在求解精度和求解效率方面等还有待于提高。粒子群算法(PSO)是新近出现的一种模仿鸟群找食飞行的仿生算法芦，，有着个体数目少、计算简单、收敛速度陕、易于实现等优点

7、，在车辆路径优化问题中已得到应用陋。7，，取得了不错的效果，本文将粒子群基金项目：甘肃省教育厅科研项目(No．1118B一03)；西北民族大学中央高校基本业务费专项资金项目(No．ZYZ2011080)。作者简介：王铁君(198l一)，女，博士生，讲师，研究领域：智能优化算法，车辆路径问题优化；邬开俊(1978一)，男，博士生，副教授，研究领域：智能优化算法，应急物流。收稿日期：2012．01—31修回日期：2012．05．23CNKI出版日期：2012．07—03DOI：10．3778匀．