求解VRPSDP 问题的改进模拟退火遗传算法.pdf

362010，46（30）ComputerEngineeringandApplications计算机工程与应用

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

葛洪伟，王银年
GEHong-wei，WANGYin-nian

江南大学信息工程学院，江苏无锡214122
SchoolofInformationEngineering，JiangnanUniversity，Wuxi，Jiangsu214122，China
E-mail：[e-mail]

GEHong-wei，WANGYin-nian.ImprovedsimulatedannealinggeneticalgorithmforVRPSDPproblem.ComputerEngi-
neeringandApplications，2010，46（30）：36-39.

Abstract：VehicleRoutingProblemwithSimultaneousDeliveryandPickup（VRPSDP）isaverycomplexNPcompleteprob-
lem.Tosolvethisproblem，thispaperdesignsanImprovedSimulatedAnnealingGeneticAlgorithm（ISAGA），theuseof
non-zeronaturalnumbercodingmechanismandtheweakfeasiblesolutiontostrongfeasiblesolutiondecodingmechanism.
With3PMcrossoveroperatorandtochoosethecombinationofannealingtoform3PMgreedycrossoveroperator，theintro-
ductionofinsert，swapand2-optmutationoperatoraresuccessivelyused，whilesimulatedannealingalgorithmandgenetical-
gorithmclevercombinationofgeneticalgorithminthepre-madeplayapowerfulglobalsearchfunction；thelatterusingsim-
ulatedannealingalgorithmtodealwiththepre-geneticalgorithmoverallthanthesolution，makefulluseofsimulatedanneal-
ingalgorithmthelatterthepoweroflocalsearch.Aftertheinternationallyrecognizedtestnumericalexample，ISAGAalgorithm
Minexample，SalhiandNagyexamplesarefoundinthealgorithmthantheexistingbestsolutionknownbettersolution.
Keywords：VehicleRoutingProblemwithSimultaneousDeliveryandPickup（VRPSDP）；geneticalgorithms；simulatedanneal-
ing；greed3PMcross-operator；annealingchoice

摘要：配送和回收一体化的车辆路径问题（VRPSDP）是一种非常复杂的NP难题。针对这一问题，设计了一种改进的模拟退火遗
传算法ISAGA，采用非零自然数编码机制和弱可行解到强可行解的解码机制，将3PM交叉算子和退火选择相结合，形成贪心3PM交
叉算子，引进insert、swap和2-opt分别对解进行迭代优化，并将模拟退火算法和遗传算法巧妙地结合，使得遗传算法在前期发挥着全
局搜索的强大功能；后期用模拟退火算法来处理遗传算法前期的全局较优解，充分利用模拟退火算法后期局部搜索的强大功能。经
过国际公认的测试算例验证，ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。
关键词：配送和回收一体化的车辆路径问题；遗传算法；模拟退火算法；贪心3PM交叉算子；退火选择
DOI：10.3778/j.issn.1002-8331.2010.30.011文章编号：1002-8331（2010）30-0036-04文献标识码：Ａ中图分类号：TP18

车辆路径问题（VehicleRoutingProblem，VRP）是一个极经成为当前各国物流领域的一个研究热点。随着逆向物流的
具魅力的组合优化问题，已经被