基于自适应大规模邻域搜索算法的带时间窗的车辆路径问题-论文.pdf

《基于自适应大规模邻域搜索算法的带时间窗的车辆路径问题-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、技术与方法物流技术2015年第34卷6月刊(上半月)doi：1O．3969／j．issn．1005—152X．2015．06．049基于自适应大规模邻域搜索算法的带时间窗的车辆路径问题苗国强，于岚，胡娟娟。，赵劫，王璐，竺寒冰’(1．大连海事大学交通运输管理学院，辽宁大连116026；2．燕京理工学院，北京065201；3．北京工业大学建工学院，北京100022；4．交通运输部管理干部学院，北京101601；5．中国民航科学技术研究院，北京100028)【摘要】引入自适应大规模邻域搜索算法进行带时间窗的车辆路径问题的求解

2、，通过移除和插入规则，分别在客户层级和路线层级上，不断地摧毁和重建解决方案，并通过局部优化策略来提高解的质量，最终得到最优的解决方案。结果表明，相较于传统的启发式算法，该算法求解此类问题的速度更快、结果更好。[关键词】车辆路径问题；时间窗；自适应大规模邻域搜索算法；毁坏重建原则【中图分类号]U116．2；F224【文献标识~-nJlA[文章编号]1005-152X(2015)06—0156—03StudyonVRPTWBasedonAdaptiveLarge—scaleNeighborhoodSearchAlgorith

3、mMiaoGuoqiang。，YuLan，HuJuanjuanZhaoJim，WangLu，ZhuHanbing(1．SchoolofTransportationManagement，DalianMaritimeUniversity，Dalian1160262．YanjingUniversityofTechnology，Beijing065201；3．SchoolofCivilEngineering，BeijingUniversityofTechnology，Beijing100022；4．Adnfinistrative

4、CadreInstituteofMinist~ofTransport，Bering101601；5．ChinaAcademyofCivi1AviationScience＆Technology，Beijing100028，China)Abstract：Inthispaper，weintroducedtheadaptivelarge—sea]eneighborhoodsearchalgorithmintothesolutionofthevehicleroutingproblemwithtimewindow，nextthrou

5、ghthelocaloptimizationstrategy，obtainedtheoptimalsolution，andattheend，bycomparingitwiththesolutionobtainedusingthetraditionalheuristicalgorithm．denlonstrateditssuperiority．Keywords：vehicleroutingproblem；timewindow；adaptivelarge—scaleneighborhoodsearchalgorithm；de

6、structionandrebuildingprinciple问题；Yuvraj和Prakash运用蚁群系统来解决VRPTw问题；1引言Emmanouil等15-81提出一种基于禁忌搜索和导引式局部搜索的混合式启发式算法来求解VRPTW问题。大量研究结果表明，车辆路径问题(VehicleRoutingProblem，VRP)产生于现vRPTw问题的研究更加具有现实意义，更符合实际中对车辆实的公路交通运输领域，是近几十年来运筹学、应用数学、网路径问题的优化要求。络分析、图论、计算机应用及交通运输等学科研究的热点问现有研究表

7、明，自适应大规模邻域搜索算法(Adaptive题，在物流研究领域中也具有非常重要的理论意义和实际的LargeNeighborhoodSearchAlgorithm，ALNS)在求解VRP问题应用价值，并在通讯、生产、国防、生物、计算机应用等领域得上表现出很大的优越性，保障在有限的时间范围内最大程度到了广泛的应用。白1959年Danting和Ramser／”提出VRP问地遍历客户，该算法依据毁坏重建原则(Ruin—and—Recreate题以来，之后的学者在相关的研究与应用中，加入了大量新的Principle)191，通过

8、在每个迭代过程中摧毁和重建部分方案来逐约束，形成了新的问题，如当前有大量研究成果的带时问窗的步得到更好的方案。因此，本文基于客户和路线层级，以最小车辆路径问题(VehicleRoutingProblemwithTimeWindows，化运输距离为目标，运用自适应大规模邻域搜索算法，对VRPTW)。Dehhof：I首次