旅行商问题-毕业设计外文翻译

《旅行商问题-毕业设计外文翻译》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、旅行商问题1引言在运筹学和理论计算机科学中，旅行商问题（TSP）是一个NP-困难的组合优化问题。通过给出成对的城市间距离，找到每个城市恰好访问一次最短的周游。它是购买者旅行问题的一个特殊情况。问题最早是在1930年作为数学问题和优化中最深入研究的问题之一被系统地阐述。它成为许多优化方法的一个基准。虽然问题难以计算，但已知大量的启发式检测和确切方法，可以解决含有数以万计城市的某些情况。TSP有许多应用，甚至基于它最本质的概念本身，如规划，物流，制造微芯片。略作改动，在许多领域中，它作为子问题出现，如DNA测序。在这些应用中，TSP中的城市代表的是,客户，焊接点，或DNA片段，T

2、SP中的距离代表的是，行驶时间或成本，或DNA片段之间的相似性度量。在许多应用中，额外的限制，如有限的资源或时间窗口使问题变得相当困难。在计算复杂性理论中，TSP的决定版本（给定一个长度L，目标是判断是否有比L短的任何周游）属于np完全问题的一类。因此，很可能在最坏的情况下，解决TSP的任何算法所需的运行时间随城市数量的增加而成倍增加。2历史旅行商问题的起源目前还不清楚。一本1832年的手册提到了旅行推销员的问题，其中有德国和瑞士周游的例子，但书中未含数学处理。旅行商问题在19世纪被爱尔兰数学家W.R.和英国数学家ThomasKirkman所阐述。Hamilton的Icosi

3、an游戏就是一个基于找到哈密顿圈的休闲游戏。一般形式的TSP，最早在1930年的维也纳和哈佛大学被数学家特别是KarlMenger所研究，KarlMenger定义了问题，考虑了显然的蛮力算法，并考察了非最近邻的启发式：我们表示信使问题（因为在实践中，每个邮递员都要解决这个问题，7许多游客也一样），它的任务是，已知有限多点及其成对距离，找到最短的连接路线。当然，这个问题是可解的有限多个试验。规则可使试验的次数少于给定点的排列种数，但它不为人所知。首先从起点到最近点，然后从该点到离它最近的下一点……，这样的规则一般不构成不了最短路线。HasslerWhitney在普林斯顿大学介绍

4、了TSP后，这个问题很快在20世纪五六十年代的欧洲和美国科学界流行。在圣莫尼卡，兰德公司的GeorgeDantzig，DelbertRayFulkerson和SelmerM.Johnson，为此做出了贡献，他们把TSP作为一个整数线性规划和改进的切割平面问题求解。有了这些新的求解方法，他们构建了一个最佳周游，解决了一个含49个城市的实例，同时证明没有其它的周游可以更短。在接下来的几十年中，问题被许多数学，计算机科学，化学，物理和其他科学的研究者做了研究。RichardM.Karp在1972年研究表明，哈密顿圈问题是NP完全的，这意味着TSP是NP-困难的。这提供一个数学解释，

5、为什么找到最佳周游有明显的计算难度。在20世纪70年代末和1980年，问题有了重大突破，Grötschel,Padberg,Rinaldi和其他人一起，采用切割平面法与分支定界，完全成功地解决最多含2392个城市的实例。在20世纪90年代，Applegate,Bixby,Chvátal,andCook开发了“协和”程序，在最近的许多求解中被使用。1991年，GerhardReinelt公布了TSPLIB，其搜集了不同难度的例子，被许多研究小组用于比较结果。2005年，cook和其他人由一个芯片布局问题找到了通过33810个城市的最佳周游，这是目前TSPLIB中最大的求解实例。

6、对于其它含以百万计城市的许多实例，可以找到问题求解，且保证有1％是一个最佳周游。3描述3.1作为一个图形问题TSP可以转化为无向带权图，如同，城市是图的顶点，路径是图的边，路径距离是边长。这是一个最小化问题，开始和结束在一个指定的顶点，其它顶点恰好访问一次。一个哈密顿圈是TSP的一个最佳周游则每边的距离成正比。通常情况下，该模型是一个完全图（即每对顶点是由边相连）。7如果两个城市之间没有路径存在，增加一个任意长度不影响最佳周游的边，成为完全图。3.2非对称和对称在对称的TSP中，两个城市之间在每一个相反的方向的距离是一样的，形成一个无向图。这种对称将可能的求解分半。在不对称的

7、TSP中，可能不存在双向路径或双向路径不同，形成一个有向图。交通事故，单行道，不同时间和价格的机票正是破坏这种对称性的例子。3.3相关问题在图论中的一个等价命题是：给定一个完全带权图（其中顶点表示城市，边表示的路径，权值表示成本或距离），找到权值最小的哈密顿环。返回出发城市的要求，并不改变问题的计算复杂性，看哈密尔顿路径问题。另一个相关的问题是瓶颈旅行商问题（瓶颈TSP）：在带权图中找到关键边权值最小的一个汉密尔顿环。问题具有相当的实际意义，除了在明显的运输和物流领域，一个典型的例子是制造印刷电路调度的