开放式车辆路径问题的混合算法.pdf

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

1、第28卷第8期计算机仿真2011年8月文章编号：1006—9348(2011)08—0207—04开放式车辆路径问题的混合算法钟雪灵1，王雄志2(1．广东金融学院计算机系，广东广州510520；2．华南农业大学经济管理学院，广东广州510642)摘要：为研究开放式车辆路径问题(OpenVehicleRoutingProblem，OVRP)，建立了数学模型。针对遗传算法(GeneticAlgo-rithm，GA)与禁忌搜索算法(TabuSearchAlgorithm，TSA)的不足。提出了一个采用GA和TSA相

2、结合的混合算法求解OVRP。混合算法中以GA为主，把TSA用在GA的变异操作中，增强算法的爬山能力。通过仿真，将提出的混合算法与文献中其它算法比较，结果表明它可以快速、有效求得最优解或近似解。关键词：开放式车辆路径问题；混合算法；遗传算法；禁忌搜索算法中图分类号：TI'202文献标识码：AHybridAlgorithmforOpenVehicleRoutingProblemZHONGXue—lin91．WANGXiong—zhi2(1．DepartmentofComputer，GuangdongUnivers

3、ityofFinance，GuangzhouGuangdong510520，China；2．CollegeofEconomicsandManagement，SouthChinaAgricultureUniversity，GuangzhouGuangdong510642，China)ABSTRACT：Thispaperstudiestheopenvehicleroutingproblem(OVRP)．First，themathematicsmodelofOVRPisdescribed．Thenhybridalg

4、orithmofgeneticalgorithm(GA)andtabusearchalgorithm(TSA)areproposedonthebasisofanalyzingtheweaknessofGAandTSA．TheGAistaken聃themainpart．andtheTSAisusedinthebigcycleoftheGA．So，thehill—climbingpowerofthealgorithmisincreased，andtheprobabilityofobtainingtheopti-r

5、ealsolutionisincreased．Finally，theproposedhybridalgorithmiscomparedwithotheralgorithmswithsimulationresults，whichdemonstratesthatitisallefficientandeffectivemethodforfindingtheoptimumorapproximatesolu-tion．KEYWORDS：Openvehicleroutingproblem；Hybridalgorithm；

6、GeneticAlgorithm；Tabusearchalgorithml引言自从1959年Dantzig和Ramser提出车辆路径问题(ve-hicleRoutingProblem，VRP)以来，一直受到国内外学者的大量关注，产生了众多的研究成果，如文献[1—3]等。VRP通常描述为：对一系列给定的客户需求点设计适当的行车路线，使车辆有序地通过，在满足一定的约束条件(如货物需求量、发送镀、交发货时间、车辆容茸限制、行驶距离限制、时间限制等)下，达到一定的优化日标(如路程最短、费用最少、时间尽可能少、车队规模

7、尽可能小、车辆利用率高等)。开放式车辆路径问题(OpenVehicleRoutingProblen0VRP)是VRP的拓展。OVRP和VRP最突出的区别在于：VRP中车辆行车路线是一个哈密尔顿回路，车辆完成运输任基金项目：广东省自然科学基金项目(8451064201000819)收稿口期：2010—05—25修I田日期：2010—07—21●务后必须返同原出发点，而OVRP中，则是一个哈密尔顿路径，车辆在服务完最后一个客户点后，不要求其同到出发点，若需要同到出发点，则必须沿原路返回。OVRP是配送服务中广泛存

8、在的问题。比如一个没有自己运输队的配送中心。将其配送业务分包给车队，在配送活动中，配送中心并不关心车辆是否回到车队的车场，也不支付车辆从最后一个客户点回到车场的费用。求最小哈密尔顿路径是NP—hard的问题，所以OVRP也是NP—hard的。若N≠NP，则它不存在多项式时间的最优算法。国内外的学者对OVRP也有一些研究，提出了各种启发式算法或智能算法。符卓和聂靖Ho对OVRP的研究进展进行了简要的综