基于自适应多态蚁群算法的多约束车辆路径问题

《基于自适应多态蚁群算法的多约束车辆路径问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第38卷第1期东南大学学报(自然科学版)VOlI38No．12008年1月JOURNALOFSOUTHEASTUNIVERSITY(NaturalScienceEdition)Jan．2008基于自适应多态蚁群算法的多约束车辆路径问题陈美军张志胜史金飞(东南大学机械工程学院，南京211189)摘要：建立了在有客户优先级、路况影响、多车型、时间窗和容量等多约束条件下车辆路径问题(VRPMC)的数学模型．由于该模型是一个NP．hard问题，目前还没有多项式算法求解，又提出了采用自适应的多态蚁群算法(APACA)来对其

2、进行求解的策略．首先，算法中侦察蚁完成满足约束条件的路径侦察并设置侦察信息素；其次，搜索蚁利用侦察蚁提供的辅助信息进一步搜索可行路径，通过多态蚂蚁间的协作和自适应调整挥发系数，能更快地搜索到问题的优化解；最后通过一个实例与节约算法、遗传算法、禁忌搜索算法和基本蚁群算法进行了对比，结果表明：对VR—PMC问题，APACA算法比前述算法在算法稳定性、运行距离、计算速度方面更具有优势．关键词：车辆路径问题；时间窗；多约束；数学模型；自适应多态蚁群算法中图分类号：TP301．6文献标识码：A文章编号：1001—0505(2008)01-0037-06Vehiclero

3、utingproblemwithmultipleconstraintsusingadaptiveandpolymorphicantcolonyalgorithmChenMeijunZhangZhishengShiJinfei(SchoolofMechanicalEngineering，SourestUniversity，Nanjing211189，China)Abstract：Anovelmathematicalmodelhasbeendevelopedtoaddressthecomplicatedissueofvehi_cleroutingproblemwi

4、thmultipleconstraints(VRPMC)，whichincludestheclientprioritylevels，trafficconditioninfluences，multi—typevehicle，timewindowsandcapacityconstraints．AsanNP—hardproblem，thismodelhasnosolutionbasedonpolynomialalgorithmatpresent．Therefore，ana—daptiveandpolymorphicantcolonyalgorithm(APACA)h

5、asbeenbroughtforwardtosolvetheVR—PMC．First，spyantsfulfillthereconnaissancetotheroutethatsatisfiesconstraintconditionandsetreconnoiteringpheromonesontheroute．Then，searchantssearchthefeasiblepathbytheauxiliaryinformationfromspyants．Thecooperatingamongpolymorphicantsandadaptivelyadjust

6、ingthevolatilizingcoeficientcansignificantlyimprovethespeedtofindtheoptimumsolution．Finally，acasestudyispresentedtocompareAPACAwithsavingalgorithm，geneticalgorithm，tabu—searchal—gorithmandantcolonyoptimum．Thetestresultsshowthattheproposedalgorithmisofmoreadvan—tagethanforementioneda

7、lgorithmsincomputationalresultsstability，transportdistanceandcompu—tationalspeedforVRPMC．Keywords：vehicleroutingproblem；timewindows；multipleconstraints；mathematicalmodel；a—daptive；polymorphicantcolonyalgorithm现代物流是供应链管理过程的一个重要组成50％，比重最大．据统计，美国2000年的运输费用部分，与国民经济及生活的诸多领域密切相关，越为5900亿美元

8、，占当年GDP总值99600亿美元来越