求解vrpsdp 问题的改进模拟退火遗传算法

《求解vrpsdp 问题的改进模拟退火遗传算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、362010，46（30）ComputerEngineeringandApplications计算机工程与应用求解VRPSDP问题的改进模拟退火遗传算法葛洪伟，王银年GEHong-wei，WANGYin-nian江南大学信息工程学院，江苏无锡214122SchoolofInformationEngineering，JiangnanUniversity，Wuxi，Jiangsu214122，ChinaE-mail：wyn2008boy@126.comGEHong-wei，WANGYin-nian.Improvedsimulatedannealinggen

2、eticalgorithmforVRPSDPproblem.ComputerEngi-neeringandApplications，2010，46（30）：36-39.Abstract：VehicleRoutingProblemwithSimultaneousDeliveryandPickup（VRPSDP）isaverycomplexNPcompleteprob-lem.Tosolvethisproblem，thispaperdesignsanImprovedSimulatedAnnealingGeneticAlgorithm（ISAGA），theu

3、seofnon-zeronaturalnumbercodingmechanismandtheweakfeasiblesolutiontostrongfeasiblesolutiondecodingmechanism.With3PMcrossoveroperatorandtochoosethecombinationofannealingtoform3PMgreedycrossoveroperator，theintro-ductionofinsert，swapand2-optmutationoperatoraresuccessivelyused，while

4、simulatedannealingalgorithmandgenetical-gorithmclevercombinationofgeneticalgorithminthepre-madeplayapowerfulglobalsearchfunction；thelatterusingsim-ulatedannealingalgorithmtodealwiththepre-geneticalgorithmoverallthanthesolution，makefulluseofsimulatedanneal-ingalgorithmthelatterth

5、epoweroflocalsearch.Aftertheinternationallyrecognizedtestnumericalexample，ISAGAalgorithmMinexample，SalhiandNagyexamplesarefoundinthealgorithmthantheexistingbestsolutionknownbettersolution.Keywords：VehicleRoutingProblemwithSimultaneousDeliveryandPickup（VRPSDP）；geneticalgorithms；s

6、imulatedanneal-ing；greed3PMcross-operator；annealingchoice摘要：配送和回收一体化的车辆路径问题（VRPSDP）是一种非常复杂的NP难题。针对这一问题，设计了一种改进的模拟退火遗传算法ISAGA，采用非零自然数编码机制和弱可行解到强可行解的解码机制，将3PM交叉算子和退火选择相结合，形成贪心3PM交叉算子，引进insert、swap和2-opt分别对解进行迭代优化，并将模拟退火算法和遗传算法巧妙地结合，使得遗传算法在前期发挥着全局搜索的强大功能；后期用模拟退火算法来处理遗传算法前期的全局较优解，充分

7、利用模拟退火算法后期局部搜索的强大功能。经过国际公认的测试算例验证，ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。关键词：配送和回收一体化的车辆路径问题；遗传算法；模拟退火算法；贪心3PM交叉算子；退火选择DOI：10.3778/j.issn.1002-8331.2010.30.011文章编号：1002-8331（2010）30-0036-04文献标识码：Ａ中图分类号：TP18车辆路径问题（VehicleRoutingProblem，VRP）是一个极经成为当前各国物流领域的一个研究热点。随着逆向物流的具魅力

8、的组合优化问题，已经被证明是一个NP难题。该问题发展，近年来VRP的另一形式的问题—配送和回收