中国科学院沈阳自动化研究所机构知识库
Advanced  
SIA OpenIR  > 工业信息学研究室  > 工业控制系统研究室  > 学位论文
题名: 旅行商问题的算法研究
其他题名: Reseach on Algorithms for Traveling Salesman Problem
作者: 苏丽杰
导师: 聂义勇
分类号: O157
关键词: 旅行商问题 ; 启发式算法 ; 内点法 ; 等高面 ; 割平面
索取号: O157/S91/2005
学位专业: 机械电子工程
学位类别: 博士
答辩日期: 2005-05-30
授予单位: 中国科学院沈阳自动化研究所
学位授予地点: 中国科学院沈阳自动化研究所
作者部门: 工业控制系统研究室
中文摘要: 本文在对TSP求解方法进行深入分析的基础上,提出了几种改进算法和新算法,并定义了两种现实TSP模型。首先,对TSP的典型算法,主要包括松弛问题的求解、启发式算法和精确算法,进行了分析、比较和评价,指出各方法存在的问题及研究倾向。其次,对求解TSP的近似算法进行了研究,包括启发式算法评价标准的探讨、两种改进的启发式算法的提出以及对TSP线性松弛问题求解方法的比较。评价启发式算法性能的标准主要是计算复杂性和计算精度。指引最近邻算法和选择“龙骨”的指数级邻域搜索算法是本文提出了的两种改进的启发式算法。数值实验表现出这两种改进算法的有效性及优点。将两种内点算法:原-对偶内点算法和等高面法,用于求解TSP的线性松弛问题。数值实验显示出这两种内点算法的计算性能都好于单纯形法。同时,等高面法的计算复杂性略低于原-对偶内点算法。再次,提出了一种新的整数规划算法-等量面法,并用其对TSP进行了精确求解。理论上证明了该算法是一种良性隐式枚举,数值实验表明该算法具有很好的性能。应用等量面法迭代求解了TSP的最优解。最后,本文给出了图形旅行商问题的数学模型,同时定义了两种新的现实旅行商问题-实用旅行商问题和动态旅行商问题。
英文摘要: 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.
语种: 中文
产权排序: 1
内容类型: 学位论文
URI标识: http://ir.sia.cn/handle/173321/9470
Appears in Collections:工业信息学研究室_工业控制系统研究室_学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
旅行商问题的算法研究.pdf(1126KB)----限制开放 联系获取全文

Recommended Citation:
苏丽杰.旅行商问题的算法研究.[博士学位论文].中国科学院沈阳自动化研究所.2005
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[苏丽杰]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[苏丽杰]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2016  中国科学院沈阳自动化研究所 - Feedback
Powered by CSpace