运筹优化领域的旅行商问题各种模型求解与应用研究开题报告

1. 研究目的与意义

本课题的现状及发展趋势：

旅行推销员问题（英语：travelling salesman problem,tsp）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个np难问题，在运筹学和理论计算机科学中非常重要。

最早的旅行商问题的数学规划是由dantzig（1959）等人提出，并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难，但已经有了大量的启发式算法和精确方法来求解数量上万的实例，并且能将误差控制在1%内。

2. 研究内容和问题

基本内容：

1、从课本读物及文献等方面了解各种旅行商问题的模型并对其适用的情况进行分析。

2、从dantzig-fulkerson-johnson模型，miller-tucker-zemlin模型等模型中选取合适的模型并用lingo软件进行编程。

3. 设计方案和技术路线

研究方法：

1、文献分析法。通过查阅文献资料，探索和学习国内外相关内容的研究手段和技巧，为本课题的研究奠定基础。

2、调研访谈法。实地调查，摸查实际的数据。

4. 研究的条件和基础

1、设计条件：毕业设计教室、设计所用软件Lingo。

2、技能条件：学校图书馆与学院资料室供补充学习、配备指导教师。