基于两种改进策略的亚启发式算法求解路径相关问题研究

《基于两种改进策略的亚启发式算法求解路径相关问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、天津大学硕士学位论文基于两种改进策略的亚启发式算法求解路径相关问题研究TheStudyonMeta-heuristicAlgorithmsBasedonTwoImprovedStrategiestoSolveRoute-relatedProblems学科专业：工业工程研究生：边哲永指导教师：蔺宇副教授企业导师：王涛天津大学管理与经济学部2015年11月中文摘要路径相关问题一直是运筹学研究中的一个热点，研究路径相关问题具有重要的理论和实际意义。而亚启发式算法是求解路径相关问题的有效方法，同时也是当前学术界的研究热点。对传

2、统亚启发式算法进行改进，可以更加高效精确的求解路径相关问题。本文首先对路径相关问题的研究背景及研究意义做了介绍，对求解路径相关问题计算方法的国内外研究现状进行了回顾，总结了研究现状中的不足之处。针对研究的不足之处，本文首先分析了一般亚启发式算法的共有特点，据此，提出了两种亚启发式算法的改进策略，即选择性定向变异策略以及限制搜索范围策略，并说明两种策略的适用范围。紧接着，本文研究了两个具有代表性的路径相关问题，旅行商问题和考虑在途库存成本的多对多Milk-run路径规划问题。为验证这两种改进策略的可行性和有效性，分别提出

3、了基于这两种改进策略的亚启发式算法，即基于圆定向变异动态邻域结构的自适应混合模拟退火禁忌搜索算法以及带限制搜索范围的两阶段模拟退火算法，分别求解以上两种问题。对于旅行商问题，本文利用TSPLIB中标准的benchmark测试提出的算法求解该问题，并与文献中传统亚启发式算法以及其他启发式算法进行比较，表明算法具有显著的优越性。对于考虑在途库存成本的多对多Milk-run路径规划问题，本文首先建立数学模型；再根据建立的数学模型，提出带限制搜索范围的两阶段模拟退火算法；然后利用计算机随机产生的算例测试提出的算法，并与文献中常

4、用的亚启发式算法进行比较，表明了算法的优越性；最后利用案例分析表明多对Milk-run运输模式的优越性。最后，表明两种改进策略可应用于改进其他算法求解更多的路径相关问题。关键词：选择性定向变异策略；限制搜索范围策略；旅行商问题；考虑在途库存成本的多对多Milk-run路径问题；亚启发式算法ABSTRACTRoute-relatedproblemsarehottopicsinoperationsresearchsinceithasboththeoreticalandpracticalsignificancetostudy

5、route-relatedproblems.Inaddition,meta-heuristicalgorithmscansolveroute-relatedproblemseffectively,andthusmeta-heuristicalgorithmsarealsoresearchhotspotsinrecentyears.Route-relatedproblemscanbesolvedmoreefficientlyandaccuratelythroughimprovingtraditionalmeta-heur

6、isticalgorithms.Firstly,thispapergaveabriefintroductiononthebackgroundsofroute-relatedproblemsandtheiracademicsignificance,reviewedtheresearchstatusofalgorithmsusedtosolveroute-relatedproblemsathomeandabroad,andsummarizedshortcomingsoftheresearchstatus.Then,base

7、dontheshortcomings,twoimprovedstrategiesformeta-heuristicalgorithms—strategyofselective-directedmutationandstrategyoflimitingsearchscope—wereproposedthroughanalyzingcommoncharacteristicsofgeneralizedmeta-heuristicalgorithms,andapplicationscopesforthetwostrategie

8、swerealsoclarified.Then,thispaperstudiedtworepresentativeproblems—travelingsalesmanproblem(TSP)andmany-to-manyMilk-runroutingproblemwithpipelineinventorycost(MM-MRP-P