求解旅行商问题的新方法研究

《求解旅行商问题的新方法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、F坠匦啊⑧天睾大薯硕士学位论文一■K_●■■0-爿

2、}●■!■■■¨0I学科专业：管理科学与工程作者姓名：黄厚生指导教师：郑丕谔教授～⋯⋯^2005年1月中文摘要本文对旅行商问题以及一些传统算法进行了介绍，并做出了评价。在此基础上提出了一种分割处理旅行商问题的合成算法。首先，本文描述了旅行商问题的定义和数学模型，并对旅行商问题的不同的分类与分类方法进行了介绍，还提供了一些旅行商问题应用的实际例子。其次，本文阐述了一些基本的旅行商问题的算法，其中着重研究了基于交换边来改进当前解的LK算法和目前最有潜力的神经网络和遗传算法。接着，本文利用实际数据检验了部分算法的优劣。再次，本文研究了目前

3、最新且最有效的LK算法的变种LKH算法，介绍了它的主要特点，利用实验数据分析了它的优点和缺点，提出了改进的思路。再次，本文提出了一种新的分割求解的方法。实证结果表明，这种方法有一定的作用，而且这种方法对其它算法的改进具有一定的参考价值。最后，本文将LKH算法和分割求解的方法相结合，提出了一种合成算法。实证结果表明，这种合成算法有一定的作用，特别是针对一些分布较有规律的旅行商问题。关键词：旅行商iu]NLK算法LKH算法r—opt算法分割求解ABSTRACTBasedonthe1nstroductiontotheTSPassociatedwithltstraditionalalgori

4、thm。AnevaluationisgivenandanewalgorithmisdevelopedtosolvetheTSRFirst，thisthesisintroducesthedefinitionandmathematicalmodelofTSP,andsummarizesdifferentclassificationswithsomecasestudiesinmanyfields．Secondly，inthisthesissometraditionalalgorithmsarereviewed，andLKalgorithm，whichusestheedge-exchangi

5、ngtoimproveitsperformance，ispresentedindetail．TheANNandGAalgorithm，whicharethemostpotential，aredescribedaswell．AndthensomevarientsofLKalgorithmsarecomparedbyexperiments，andthedifferencesbetweenthemcanbeeasilyrecognized．Thirdly，thisthesishasmadeacloselookintoLKHalgorithm，themostefficientvarianto

6、ftheLKalgorithms．TwomajorfeaturesofLKItalgorithmsareanalyzed．AndanexperimentismadetoanalysetheexcellenceandshortcomingofLKHalgorithm．Therefore，aconceptiontoimproveonthealgoritlmaisproposed．Finally，anewalgorithmwhichisbasedonthemethodofdivide—and—conquerisproposed．Theresultfromacasestudyshowstha

7、ttheproposedmethodisusefulandeffectiveandCanbeflreferenceforimprovementinalgorithmsrelated。KEYWORDS：TSPLKAlgorithmLKHAlgorithmr-optAlgorithmdivide·-and--conquer独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均

8、已在论文中作了明确的说明并表示了谢意。学位论文作者签名Z7／V签字日期：?“年V月y诮学位论文版权使用授权书本学位论文作者完全了解叁鲞盘堂有关保留、使用学位论文的规定。特授权基鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者虢兽咖签字日期0—西年y月协同翩躲幻产签字日期：(广年_月Ⅵ同