多类型请求的tsp问题研究

《多类型请求的tsp问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号：F2520单位代码：11232密级：◆t富信息科技太学管理学硕士学位论文多类型请求的TSP问题研究学院：学科(专业)：学号：作者：指导教师：完成日期：兀从口删：信息管理学院管理科学与工程2011020270张伊彤赵刚副教授二。一三年十二月二十五日万方数据学位论文版权使用授权书I舢籼舢删脚删删舢删删Y2659449本人完全了解北京信息科技大学关于收集、保存、使用学位论文的规定，按照学校要求提交学位论文的印刷本和电子版本。学校有权保留学位论文并向中国科学技术信息研究所等国家主管部门或其指定机构送交论文的电子版和纸质版，允许论文被

2、查阅和借阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。学校有权适当复制、公布论文的全部或部分内容。学校有权将本人的学位论文加入《中国优秀硕士学位论文全文数据库》和编入《中国知识资源总库》。口公开口保密(——年——月)(保密的学位论文在解密后应遵守此协议)指导教师签名：学位论文作者签名：确珊年月日年月日万方数据硕士学位论文原创性声明本人郑重声明：所呈交的论文题目为《多类型请求的TSP问题研究》学位论文，是本人在导师指导下，进行研究工作所取得的成果。尽我所知，除了文中特别加以标注的内容外，本学位论文的研究成果不包含任何他人创作的、已

3、公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明并表示了谢意。本学位论文原创性声明的法律责任由本人承担。作者粹獬年7月日万方数据摘要鉴于旅行商问题(TralVell崦SalesmanProblem，TSP)是个典型的NP难题，使用精确算法求解具有相当的复杂度，所以引入智能启发式搜索算法很有必要。在传统TSP的基础上引出的多类型请求TSP问题，使TSP问题的研究更进一步贴切实际问题，所以研究如何求解多类型请求的TSP问题不只是对TSP研究问题的一种完善，更具有显著的应用意义。物流

4、配送过程中，首先必须保证服务所有的配送请求，且为完成此活动付出的代价最小。物流运输方式多种多样，其内容涉及到配送车辆调度、路径规划、配送运输方式的选择等，本论文从智能算法和运筹学的角度对TSP问题进行分析。将TSP问题中的配送请求类型划分为两类：即立即配送请求与普通配送请求。对于48个立即配送请求，利用遗传算法和H0pfield神经网络算法求解其配送顺序并优化其配送路径长度。对于3个普通配送请求，利用层次分析法分析其配送顺序。由于将TSP问题中的配送请求划分为两类，所以应用排队论中多服务台混合排队制模型进行排队系统优化。首先，介绍遗传算法、

5、HopfieId网络算法、层次分析法、排队论这四种算法的基本原理以及旅行商问题的相关信息；然后针对单独使用这些方法的不足构建求解TSP的混合算法，即Hopfield网络与层次分析法结合，遗传算法与排队论结合的算法。利用典型测试数据，对比Hop丘eld网络与遗传算法在处理立即配送请求的访问路径长度的结果。仿真结果表明处理立即配送请求时，本文采用的改进遗传算法比H叩field神经网络求解效果好。通过论文工作的研究，作者认为将遗传算法和排队论相结合是很好的策略，既解决了路径选择方面的问题，又对配送过程进行优化。Hopfield神经网络和层次分析法

6、结合能更加全面的考虑配送请求配送问题，互补对方缺陷。关键词：遗传算法；H0p丘eld神经网络；层次分析法；排队论；旅行商问题万方数据ABSlRACTABSTRACTInViewofmeTraVell她SalesmanProblem，TSPisa咖icalNPhardproblem．UsingtlleexactalgorithmtosolVetlleproblemisconsiderablecomplexi坝sothein哟ductionofIntelligentHellristicsearchalgorithmisnecessary．Onm

7、ebasisof臼『aditionalTSP't11eiIl讯)ductionofmultipletypesofTSPisnotoIllymeimprovement，butals0makiIlgtlleprobl锄of胁herpmcticalsigIlificaIlce．IIl吐leprocessofIogistics孤ddist曲ution，‰firStthingtoconsideristoguamteeaUdistributiond锄andisservedandtocompleteⅡleaCtiVi哆costminimum．Therea

8、reaVarietyofwaysiIllogisticsanddistribution．ItScontent抽volvesdistributionvehicleschedulin