求解车辆路径问题的一种混合方法.pdf

《求解车辆路径问题的一种混合方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerEngineeringandApplications计算机工程与应用求解车辆路径问题的一种混合方法张思亮，葛洪伟ZHANGSiliang．GEHongwei江南大学信息工程学院，江苏无锡214061SchooloflnformationEngineering，JiangnanUniversity，Wuxi，Jiangsu214061，ChinaZHANGSiliang，GEHongwei．Hybridalgorithmforvehicleroutingproblem．ComputerEngineeringandAppncafions，2012，48(8)：226．22

2、9．Abstract：AmodifiedParticleSwarmOptimization(PSO)algorithmisadoptedtodealwithVehicleRoutingProblemwithTimeWin‘dows(VRPTW)．AntColonySystem(ACS)algorithmisadoptedtoproduceastagesolutionasatemplate．PSOalgorithmisusedtooptimizethetemplate．AndintheACS，antchoosesclientthatunvisitedandcapacityisultim

3、ateasstart，whencapacityisoverrunned．Fromthetestresults，itshowsthatthisalgorithmiseffectiveandpracticable．Keywords：vehicleroutingproblem；ParticleSwarmOptimization(PS0)；AntColonySystem(ACS)摘要：提出一种求解带软时间窗车辆路径问题的混合算法。采用蚁群系统算法产生阶段最优解，以此作为粒子模板，随机生成粒子群，利用粒子群算法在阶段最优解基础上进一步优化。且在蚁群系统算法中，当容量超过限制后，从剩余的客户里选

4、择需求量最大的作为新的起点继续探索路径，直到所有客户都被访问一遍。实验表明，该混合算法是解决带软时间窗车辆路径问题的一个有效算法。关键词：车辆路径问题；粒子群算法；蚁群系统算法DOI：10．3778／j．issn．1002—8331．2012．08．064文章编号：1002．8331(2012)08．0226．04文献标识码：A中图分类号：TP301．6l引言车辆路径问题(VehicleRoutingProblem，VRP)，是指将货物从配送中心按客户的需求发送到客户手中，在一定条件的约束下，达到一定的目标(诸如路程最短、费用最小、耗费时间尽量少等)。VRP问题属于NP问题。带时间窗

5、的车辆路径问题(VehicleRoutingProblemwithTimeWindows，VRPTW)是在vRP问题上加了客户要求访问的时间窗口。按客户对时间窗的要求，又分为带硬时间窗的车辆路径问题(VehicleRoutingProblemwithHardTimeWindows，VRPHTW)和带软时间窗的车辆路径问题(VehicleRoutingProblemwithSoftTimeWindows，VRPSTW)。由于在现实生活中许多问题都可以归结为VRPTW问题来处理，其处理的好坏将直接影响到企业的服务质量，所以对它的研究越来越受到人们的重视。近年来，现代启发式算法成为VRP算

6、法研究的新方向，如文献[1】中的遗传算法，通过引用一种新的编码方法、交叉和变异概率的自适应机制，构造一个改进的遗传算法来求解VRPSTW；文献[2]中的混合遗传算法，是一种结合模拟退火算法的混合遗传算法；文献[3]中的改进蚁群算法，在初始解的构造、路径优化、转移规则、信息素更新方式、算法终止判断等方面进行了改进。本文在现有算法研究的基础上，针对VRPSTW问题，设计了一种蚁群系统算法(AntColonySys．tern，ACS)和粒子群算法(ParticleSwarmOptimizationalgo．rithm，PSO)的混合算法(hybridalgorithmofPSOandACS

7、，ACSPSO)。PSO算法，具有计算速度快，全局寻优能力强，易于实现的特点，但在解决车辆路径问题时，很难直接产生出好的解，不能达到最小化车辆数目的目标，特别是对大规模问题。而ACS算法能够优化车辆数目，寻找的最终结果比较好。本文使用ACS算法产生粒子模板，按照模板产生粒子群，粒子群飞行一定次数得到最终解。通过对一个典型实际算例的计算，结果表明此算法是解决VRPSTW的一种较好方法。2VRPSTW问题2．1问题描述时间窗是一个时间段[EI，三明，是由客户f