基于蚁群算法的车辆路径规划问题的研究

《基于蚁群算法的车辆路径规划问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、巧姑字种乂麟圍硕±学位论文！圓磯基于蚁群算法的车辆路径规划问题的研究－目记篇阳庶２Ｌ薩Ｓｈ企幽导师姓名、职赖马岸英研究员Ｚｌ！申请学位类别工程硕±圓西安电子科技大学学位论文独创性（或创新性）声巧秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加＾＾＾标注和致谢中所罗列的内容レッ外，论文中不包含其他人已经发表或撰写过的研充成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料＾同王。与我作的同事对本研究所做的任何贡

2、献均已在论文中作了明确的说明并表示了谢意。一学位论文若有不实之处，本人承担切法律责任。办Ｉ＞巷建爱日ｉ王）：：本人签名期西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，目Ｐ；研究生在校攻读学位期间论文了作的知识产权属于西安电子科技乂学。学校有权保留送交论文、的复印件，允许查阅借阅论文；学校可Ｗ公布论文的全部或部分内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，结合学位论文研究成果完成的论文、保发密明专利等成果，署名单位为西安电子科技大学。本人的签学位论文在＿年解密后适用本

3、授权书。？＞名：老挺娃ｆ导师签名；日期：ＶＩＶ日期：学校代码10701学号1301120650分类号TP301.6密级公开西安电子科技大学硕士学位论文基于蚁群算法的车辆路径规划问题的研究作者姓名：李建军领域：电子与通信工程学位类别：工程硕士学校导师姓名、职称：栾英姿副教授企业导师姓名、职称：马岸英研究员学院：通信工程学院提交日期：2015年11月ResearchonthevehicleroutingproblembasedonantcolonyalgorithmAthesissubmittedtoXIDIANUNIVERSITYinpartial

4、fulfillmentoftherequirementsforthedegreeofMasterinElectronicsandCommunicationsEngineeringByLiJianjunSupervisor:LuanYingziAssociateProfessorMaAnyingResearchFellowNovember2015摘要摘要车辆路径规划问题（VehicleRoutingProblem，VRP）是现代物流配送过程中的关键环节，而且其在众多领域中都有广泛的应用，因此它的提出引起了不同学科的专家和物流管理者的极大重视,目前VRP已经成为研究的热点。但是如何找到

5、一种高效的算法使其在较短的时间内找到比较满意的全局解仍然是研究的重点。本文主要从以下几个方面进行阐述。（1）详细介绍和比较分析了国内外求解VRP问题的研究现状和求解方法，重点阐述了基本蚁群算法（AntSystem，AS）的工作原理、数学模型和实现旅行商问题（TravelingSalesmanProblem，TSP）的求解过程，剖析了蚁群算法的复杂度、特征以及重要参数的设置对算法性能的影响情况。但是，如何在蚁群算法求解TSP问题的基础上把其改造成适合求解VRP问题的算法是本文研究的主要内容，而从此问题出发可以有两个不同的方向：直接法和转化法。（2）本文首先从直接法出发提出了两种改进蚁

6、群算法的技术。技术方案一（简称ImproAS_VRP_ACSTSP）是先运用初步改造好的蚁群算法得到一个VRP可行解，然后在这个解的基础上分多段运用蚁群TSP算法以对该VRP解进行改善。技术方案二（简称OutsideAdvancedAS_InsideACSTSP）不仅对蚁群算法进行了充分的完善而且采用了两次蚁群算法，外部的蚁群算法只是为了得到多种不同的分组方案，而内部的蚁群算法则是为该分组规划出较短路线并指导蚂蚁按此路线行走。然后又从转化法出发提出了一种新型改进技术方案三（简称MutationSweep_ACSTSP），它是在之前顺序扫描算法的基础上增加了变异操作，并将变异算子用于

7、扫描过程中，既可保证得到VRP解依旧是可行的又可使不同的分组之间距离较接近，这样就可得到多个较合理的分组，然后在每个分组内部实现路内次序的再优化，最后就可以得到VRP问题的最优解。（3）利用Matlab在VRPLIB数据集上进行仿真测试，记录三种改进算法找到的最优目标函数值及运行时间，比较和分析得到的仿真结果，验证和评价这些改进技术方案的合理性和有效性。关键词：车辆路径规划问题，蚁群算法，旅行商问题，扫描法，VRPLIBIABSTRACTABSTRACTThevehi