旅行商问题的算法研究
文献类型：学位论文
| 作者 | 苏丽杰 |
| 学位类别 | 博士 |
| 答辩日期 | 2005-05-30 |
| 授予单位 | 中国科学院沈阳自动化研究所 |
| 授予地点 | 中国科学院沈阳自动化研究所 |
| 导师 | 聂义勇 |
| 关键词 | 旅行商问题 启发式算法 内点法 等高面 割平面 |
| 其他题名 | Reseach on Algorithms for Traveling Salesman Problem |
| 学位专业 | 机械电子工程 |
| 中文摘要 | 本文在对TSP求解方法进行深入分析的基础上，提出了几种改进算法和新算法，并定义了两种现实TSP模型。首先，对TSP的典型算法，主要包括松弛问题的求解、启发式算法和精确算法，进行了分析、比较和评价，指出各方法存在的问题及研究倾向。其次，对求解TSP的近似算法进行了研究，包括启发式算法评价标准的探讨、两种改进的启发式算法的提出以及对TSP线性松弛问题求解方法的比较。评价启发式算法性能的标准主要是计算复杂性和计算精度。指引最近邻算法和选择“龙骨”的指数级邻域搜索算法是本文提出了的两种改进的启发式算法。数值实验表现出这两种改进算法的有效性及优点。将两种内点算法：原-对偶内点算法和等高面法，用于求解TSP的线性松弛问题。数值实验显示出这两种内点算法的计算性能都好于单纯形法。同时，等高面法的计算复杂性略低于原-对偶内点算法。再次，提出了一种新的整数规划算法－等量面法，并用其对TSP进行了精确求解。理论上证明了该算法是一种良性隐式枚举，数值实验表明该算法具有很好的性能。应用等量面法迭代求解了TSP的最优解。最后，本文给出了图形旅行商问题的数学模型，同时定义了两种新的现实旅行商问题－实用旅行商问题和动态旅行商问题。 |
| 索取号 | O157/S91/2005 |
| 英文摘要 | Based on thorough analysis of these methods for TSP, the thesis presents several kinds of improved algorithms, one new algorithm, and defining tow kinds of real-life TSP models. Firstly, analyse the main algorithms of TSP, including algorithms solving of relaxation problems, heuristic algorithms and exact algorithms. Compare and evaluate these typical algorithms, point out exiting problems and research trends. Secondly, do some work on approximation algorithm, including discussing on the evaluated criterions of Heuristic Methods, presenting two kinds of improved Heuristics and comparing the methods solving the linear relaxation problem of TSP. The main criterions of evaluated algorithm performance are computational complexity and computational precision. The paper also presents two improved heuristics: Guided Nearest Neighbor Algorithm and Selected “Backbone” Exponential Neighborhood Search Algorithm. Data experiments display the validity of the two improved algorithms and virtues. Using two kinds of Interior Point Methods: Primal-dual Interior Point Method and Isometric Plane Method, solves the Linear Relaxation Problem of TSP. Data experiments show that the two Interior Point Methods perform better than Simplex Method. And the complexity of Isometric Plane Method is lower than Primal-dual Interior Point Method. Thirdly, the thesis presents a new Integer Programming Algorithm-Isometric Surface Method (ISM), and uses it solving TSP exactly. ISM is proved a well-implied enumeration in theory, and data experiments show its well performance. And solve TSP using iterative ISM with subtour elimination inequalities. At last, the thesis presents the mathematical model of Graphical TSP, and defines two kinds of real-life Traveling Salesman Problem: Practical TSP and Dynamical TSP. |
| 语种 | 中文 |
| 公开日期 | 2012-08-29 |
| 产权排序 | 1 |
| 分类号 | O157 |
| 源URL | [http://ir.sia.ac.cn/handle/173321/9470]  |
| 专题 | 沈阳自动化研究所_工业信息学研究室_工业控制系统研究室 |
| 推荐引用方式 GB/T 7714 | 苏丽杰. 旅行商问题的算法研究[D]. 中国科学院沈阳自动化研究所. 中国科学院沈阳自动化研究所. 2005. |
入库方式： OAI收割
来源：沈阳自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。