基于遗传算法的多旅行商问题的优化

《基于遗传算法的多旅行商问题的优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号学校代码10372硕士学位论文基于遗传算法的多旅行商问题的优化作者姓名：束东来学号：Y15690017学科专业：统计学研究方向：统计信息技术导师及职称：张玉州副教授论文答辩日期：2018.06授予学位日期：2018.06安庆师范大学硕士学位评定委员会办公室安庆师范大学硕士学位论文题目：基于遗传算法的多旅行商问题的优化(英文题)：OptimizationofMultipleTravelingSalesmanProblemBasedonGeneticAlgorithm作者姓名：束东来学号：Y15690017学科专业

2、：统计学研究方向：统计信息技术导师及职称：张玉州副教授论文答辩日期：2018年6月授予学位日期：2018年6月安庆师范大学学位评定委员会办公室基于遗传算法的多旅行商问题的优化束东来安庆师范大学硕士学位论文2018年6月15日（论文提交日期）摘要旅行商问题（TravelingSalesmanProblem,TSP）是一个经典的NP-hard组合优化问题，多旅行商问题（MultipleTravelingSalesmanProblem,MTSP）作为其扩展模型，具有更强的实际意义。而在理想情况下的旅行商问题及多旅行商问题几

3、乎是不存在的，本文介绍了两种更符合实际意义的限容量多旅行商问题（MultipleTravelingSalesmanProblemWithLimitedCapacity,LCMTSP）和不确定性多旅行商问题（UncertainMultipleTravelingSalesmanProblem,UMTSP）模型，并设计了遗传算法（GeneticAlgorithm,GA）对这两种模型进行求解。本文首先对LCMTSP问题模型进行了研究，将容量限制条件加入到多旅行商问题模型中，以控制每个旅行商访问城市个数范围。鉴于问题的复杂性，

4、本文在传统GA的种群初始化过程中，采用完全随机法和适用于多旅行商问题模型的次优选择法，并在交叉算子中加入最小路径交叉等规则，且引入DI算子和3-opt算子。实验结果证明了所设计IGA求解LCMTSP问题时的可行性和有效性以及较高的计算效率。考虑到理想化的多旅行商问题在现实环境中的不可靠性，本文将现实情况下的不确定性因素归纳为一种路况系数，从而构建了不确定性多旅行商问题（UMTSP）模型。针对该问题，设计了遗传算法对其进行了求解，并比较基本MTSP问题与UMTSP问题的实验结果。实验结果证明了UMTSP问题模型的实际意

5、义以及所提遗传算法的可行性与实用性。关键词：多旅行商问题；容量限制；不确定性；遗传算法ABSTRACTTravelingSalesmanProblem(TSP)isaclassicalNP-hardcombinatorialoptimizationproblem.Asanextendedmodel,MultipleTravelingSalesmanProblem(MTSP)hasastrongerpracticalsignificance.Intheidealsituation,thetravelingsalesma

6、nproblemandthemultipletravelingsalesmanproblemalmostdonotexist.Thisthesisintroducestwomorepracticallymeaningfulmodels,i.e.,MultipleTravelingSalesmanProblemwithLimitedCapacity(LCMTSP)andUncertainMultipleTravelingSalesmanProblem(UMTSP)models.TheGeneticAlgorithms(

7、GA)isdesignedtosolvethesetwomodels.Inthisthesis,theLCMTSPproblemmodelisfirstlystudied,andthecapacityconstraintconditionisaddedtotheMTSPmodeltocontrolthecitynumberofeachtravelingsalesman.Inviewofthecomplexityoftheproblem,therandommethodandsuboptimalselectionmeth

8、odareadoptedinthepopulationinitializationprocessfortraditionalGeneticAlgoriyhm(GA)inthisthesis.Moreover,theminimumcrossoverruleisaddedtothetraditionalcrossoveroperator,andth