旅行商问题(TSP)及其应用-安康学院毕业论文

《旅行商问题(TSP)及其应用-安康学院毕业论文》由会员分享，可在线阅读，更多相关《旅行商问题(TSP)及其应用-安康学院毕业论文（25页珍藏版）》请在金锄头文库上搜索。

1、学 号 分类号TP273本科生毕业论文（设计）题目： 旅行商问题(TSP)及其应用 院 （系） 数 学 系 专 业 班 级 数学与应用数学10专升本1班学 生 姓 名 王 文 指导教师（职称） 刘 铁 (讲师) 提 交 时 间 六月 安康学院学位论文独创性声明本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果.尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人已经发表或撰写过的研究成果，也不包含为获得安康学院或其他教育机构的学位或证书而使用过的材料.对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意. 作者签名： 日期： 安康学院学位论文使用授

2、权声明本人同意在校攻读学位期间论文工作的知识产权单位属安康学院.本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为安康学院.学校有权保留学位论文并向国家主管部门或其他指定机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要汇编出版. 作者签名： 日期： 旅行商问题(TSP)及其应用王 文（安康学院数学系，陕西安康，725000）摘 要：旅行商问题(TSP)是组合优化领域里的一个易于描述却难以处理的NP完全难题，其可能的路径数目与城市数目呈指数型增长，求解起

3、来非常困难，至今还没有一个完美的算法.该文首先介绍了什么是TSP，接着总结了八种目前针对TSP比较有效的解决方法的基本思路及各自算法的优缺点，最后通过生活中的例子展示其运用.关键词：旅行商(TSP) 算法 路径 Traveling Salesman Problem and Its ApplicationWang Wen（Department of mathematics, Ankang University, Ankang, Shanxi, 725000)Abstract: The traveling salesman problem (TSP) is a combinatorial opti

4、mization NP-complete problem in the field of an easy to describe but difficult to deal with, its number of possible paths and the number of cities growing exponentially, solving very difficult and has not yet been an ideal algorithm. This paper first introduces the TSP, and then summarizes the basic

5、 ideas of the eight kinds of effective ways to solve TSP, the respective advantages and disadvantages of the algorithms. Finally, the specific examples were used to illustrate the applications of TSP.Key words: Traveling salesman problem Algorithm Path 目 录前 言11 TSP简介22 旅行商问题(TSP)的求解方法221 禁忌搜索法322 改良

6、圈算法323 蚁群算法424 匈牙利算法525 分支界定法基本思想626 最邻近法基本思想627 最小生成树基本思想628 破圈法基本思想73 各种方法的优缺点84 TSP在实际生活中的应用9致 谢15参考文献16附录A 文中涉及的主要程序17附录B 文中涉及的数据21前 言旅行商问题(Traveling Salesman Problem,简称TSP)是数学领域的著名问题之一.TSP 的历史悠久，最早描述的是1759年欧拉研究的骑士周游问题.即对于国际象棋棋盘中的64个方格一次且仅一次并最终回到起点.从而将该问题抽象为给定个城市和两两城市间的距离，要确定一条经过各城市当且仅当一次最短路线.研究

7、的意义：旅行商问题(TSP)是组合优化领域里的一个典型的、易于描述却难以求解的NP完全难题，其可能的路径数目与城市数目呈现指数增长，求解非常困难，而快速、有效地解决TSP有着重要的理论价值和极高的使用价值，由于该问题在现实生活中应用广泛，所以研究其现实应用也具有相当的意义.研究的主要内容：该文首先介绍了什么是TSP，接着总结了八种目前针对TSP比较有效地解决方法的基本思路、各自算法的优缺点；最后通过生活中的例子展示其应用.通过 MATLAB、LINGO 软件利用最优算法求得最优解，实现其在最优化领域的应用.以体现TSP模型在现实生活中的应用价值.TSP 在图论意义下常常被称为Hamilton圈

8、问题(minimum hamiltonian cycle problem).Euler等人最早研究该问题的雏形，后来由英国Hamilton爵士作为一个悬赏问题而提出.但是，这个让普通人在几分钟内就能理解的游戏之作，却延续至今仍未能解决，成为世界上的一个难题.1 TSP简介旅行商问题(Traveling Salesman Problem,简称TSP),即给定个城市和两两城市之间的距离,要确定一条经过各城市当且仅当一次的最短路线,其图论语言描述为:给定图其中是为顶点集,为各顶点相互连接组成的边集,设是由定点和顶点之间的距离所组成的距离矩阵,要确定一条长度最短的Hamilton回路,即遍历所有的顶点

9、,当且仅当一次的最短路距离.这里，我们用数学语言来进行描述: 记为赋权图，为顶点集，为边集，各个顶点间距离已知，设则经典问题可以写为如下的数学规划模型:这里，为集合中所含图的顶点数，约束(a)和(b)意味着每一个顶点来说，仅有一条边进和一条边出;约束(c)则保证了没有任何子回路解的产生.于是，满足约束(a)(c)的解构成了一条Hamilton回路.上述约束也可以写成其他等价形式，此处不一一列举.TSP是一个经典的组合优化问题,并且是一个NP完全难题,是诸多领域内出现多种复杂问题的集中概括和简化，并且已成为各种启发式的搜索优化算法的间接比较标准.因此,快速有效地解决有着重要的理论价值和极高的实用

10、价值.2 旅行商问题(TSP)的求解方法基于TSP的问题特性，构造型算法成为最先开发的求解算法.如最近邻点、最近合并、最近插值、最近添加、贪婪插入等.但是,由于构造型算法优化质量较差,迄今为止已开发了许多性能较好的改进搜索算法1.主要有:禁忌搜索法;蚁群算法;遗传算法;最邻近算法；改良圈算法等.21 禁忌搜索法 211 基本思路 禁忌搜索(Tabu Search或Taboo Search,简称TS)是一种亚启发式搜索技术2.由Glover在1986年首席提出的.进而形成了一套完整的算法3.它是对局部领域搜索的一种扩展,是一种全局逐步寻求算法,是对人类智力过程的模拟. TS算法通过引入一种灵活的

11、存储结构和相应的紧急准则来避免迂回搜索,并且通过藐视来赦免一些被禁忌的优良状态,进而保证多样有效探索以实现最终实现全局化. 简单TS解法的基本思路:给定一个初始解(随机的),并且给定这个初始解的一个领域,然后初始解的领域中确定某些解作为算法候选解,给定一个状态”best to far”(即当前最优解),若最佳候选解对应目标优于”best to far”状态,并将相应的节加入到禁忌列表中,同时修改禁忌表中各个的任期,若找不到上述侯选解,则在候选解里边选择非禁忌的最佳状态作为性的当前解,并且不管他与当前解的优劣,且将相应的解加入到禁忌表中,同时修改禁忌表中各对象的任期,最后重复上述搜索过程,知道程

12、序解满足停止准则. 212 禁忌搜索法的流程Step1:选初始解,禁忌列表TL为定Step2:对以前解邻域中,若 且不在TL中或者TL中,但符合期望准则,则 ,进TL重复Step2的步骤直到结束22 改良圈算法221改良算法及其流程 这种算法得首先选取里的一个Hamilton圈,然后依据以下算法逐步修改,使之减小.设为图一个已知的Hamilton圈,对于圈中所有满足的,按照以下方法可得到一条新的Hamilton圈:流程:step1:在上检查是否有,使,满 成立新图Step2: 用代替转step1,直到结束为止.该算法所得到的全虽然未必是理想的圈,不过上述算法的时间复杂度是.这是显然的4.23

13、蚁群算法 231蚁群算法基本思路 蚁群算法是一种新型的模拟进化算法.由意大利学者M.Dorigo、V.Maniezzo和A.Colorini等人在90年代首先提出的.称之为蚁群系统(ant colony system).它是受到人们对自然界中真实的蚁群集体行为的研究成果的启发而提出的一种基于种群的模拟进化算法.生物学研究表明一群互相协作的蚂蚁能够相互协作的方法是它们在运动过程中能够在所经过的路径上留下一种称之为外激素(Pheromone)的物质进行信息传播,而蚂蚁在运动过程中能够感知这种物质,并且以此指导出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.该算法已成

14、功的解决诸如TSP问题等多种组合优化问题.结果可与模拟退火、遗传等通用启发算法相媲美！ 232 蚁群算法求解TSP流程将蚂蚁按照一定规则(如随机)分布在n个城市每一只蚂蚁可寻求一条可行路线并且进行局部信息更新寻出所有蚂蚁找到的最短路径进行全局信息更新233蚁群算法的研究进程赵天男等一群算法及其应用研究5一文中介绍了蚁群与改进的蚁群算法的不同及一群算法在各个领域中的应用,并且进一步给出了研究方面:进一步研究算法的收敛性分析,得出更强的收敛性证明并得出收敛速度将会加速算法的发展.理论性分析和参数设置.蚁群算法应用领域的扩展,应用较多的是静态组合优化问题,改进并将其应用于动态组合优化问题和连续优化问题是值得探索的.张晓玲等蚁群算法在车间调度问题中的应用6一文中提出了用蚁群算法求解车间调度问题.给出了用蚁群算法求解车间调度问题的流程,并进行了测试求解得到车间调度问题的最优解或近似最优解.24 匈牙利算法241匈牙利算法思想及其流程 首先将该问题写成得到相同的矩阵,其次将该矩阵中的某些元素换成一个很大正数的矩阵实施圈过程,找出所有独立元素,记下这些独立元素的位置,将这些独立元素所在位置的元素均换成1,其余位置处的元素均换0,得到一个只含1和0的新矩阵.这就是指