旅行商问题 Traveling Salesman Problem

旅行商问题 Traveling Salesman Problem (TSP)

旅行商问题的发展历史 旅行商问题，也称货郎担问题，是一个较 古老的问题。其起源已经有些模糊了。最 早大概可以追溯到 1759 年 Euler 提出的骑 士旅行问题。 十九世纪初，爱尔兰数学家William R. Hamilton和英国数学家Thomas P. Kirkman 研究过一些与旅行商问题相关的数学问题。

二十世纪初，人们开始研究通用形式的旅行商问题。 二十世纪二十年代，数学家和经济学家 Karl Menger 在维 也纳向他的同事提出了这个问题。 二十世纪三十年代，旅行商问题出现在 Princeton 大学的 数学圈子里，主要的推动者有 Hassler Whitney 与 Merrill Flood。 二十世纪四十年代，统计学家(Mahalanobis(1940), Jessen(1942), Gosh(1948), Marks(1948))把它和农业应 用联系在一起研究。美国RAND 公司也推动了这个问题的 发展。 最终，旅行商问题成为了组合优化问题中的一个困难问题 原型的典型代表。求解这种问题令人望而生畏：当问题规 模变大的时候，路径的数目将是个天文数字，逐一检查它 们几乎是不可能的。在很长的一段时间内，没有任何解决 这个问题的好想法出现.

1954 年，旅行商问题的求解终于获得了突破。George Dantizig, Ray Fulkerson 和 Selmer Johnson 提出了一个 求解旅行商问题的算法并用它成功地解决了一个有49 个 城市的实例。这个规模在当时相当引人注目; 1977 年，Groetschel 找到了有 120 个城市的旅行商问题 的最优路径; 1987年，Padberg 与 Rinaldi 找到了规模为 532 和 2392 的旅行商问题的最优路径；Groetschel与Holland找到了规 模为666的旅行商问题的最优路径。 Applegate, Bixby,Chavátal 和 Cook 于 1994 年,1998年和 2001年解决了规模为 7397, 13509和 15112的旅行商问题。 2004 年，一个具有 24978 个城市的旅行商问题的最优路 径由 Applegate, Bixby,Chavátal, Cook 和 Helsgaun 找到。 这是到目前为止精确找到最优解的最大规模的旅行商问题.

旅行商问题吸引了越来越多的人对它进行研究。 其中，有数学家，计算机科学家，运筹学家，还 有一些其它领域的研究者。 然而，该问题是否存在一个有效的通用的求解方 法仍然是一个开放性的问题。事实上，旅行商问 题的解决将意味着 P=NP问题的解决。Clay Mathematics Institute 曾悬赏 100 万美元来寻求 这个问题的解法，但没人拿到这个奖。

旅行商问题的描述 旅行商问题(TSP) 的文字描述可以表达如下：给定一组 N 个城市和它们两两之间的直达距离，找出一个闭合的回路， 使得每个城市刚好经过一次且仅一次且总的旅行距离最短。 即要寻求一条回路 T = (t 1 ,t2,...,tn),使得下列目标函数 最小：

上式中 t i为城市号，取值为 [1 ,n ],从而 ( t1 , t2,...,tn)就 可以看作是关于n的一个排列。d ( ti ,tj)表示城市 ti 与 t j之 间的距离。对于对称型 TSP,有 d ( ti ,tj)= d(tj,ti)

旅行商问题的分类 从问题对应到图的类型，TSP 可以分为两类： 1、任意两个城市间的距离都是对称的，它对应的是图论 中的无向图； 2、两个城市间的距离是非对称的，它对应的是图论中的 有向图； 从问题本身的限制条件的强弱，主要有三类： 1、不做任何限制(但是一般都要求城市间的费用不为负数), 只给出距离矩阵，求最短回路； 2、要求距离间要满足三角不等式； 3、定义在欧氏平面上的 TSP,即 Euclidean TSP,它给 出每个城市在欧氏平面上的坐标，而城市间的距离就是以 它们的欧氏距离来定义。

从问题的多项式可解性上分，TSP 可以分为两类： 1、目前己经知道有多项式时间算法可解的，比如其距离 矩阵满足特定的条件 (Demidenko 条件、Kalmanson 条件、 Supnick 条件)等； 2、目前尚没有发现多项式时间算法可解的，而研究热点 是如何寻找更多的多项式时间可解的情形。 对旅行商问题的研究经过几十年的发展，已经产生了许多 其它扩展形式,例如多旅行商问题(Multi-Salesman Problem),多目标旅行商问题(Multi-Objective TSP)等等。

旅行商问题的应用和价值 旅行商问题是一个具有广泛的实用背景与重要的 理论价值的组合优化难题。 许多关于 TSP 的工作并不仅是由实际应用直接推 动的，而是因为 TSP 为其它一般的各类算法提供 了思想方法平台，而这些算法广泛地应用于各种 离散优化问题。 其次，TSP 大量的直接应用给研究领域带来了生 机，并引导了未来的工作

运输问题是 TSP 最自然的应用。由于其模型的简单性， TSP 在其它一些领域有着有趣的应用。一个经典的例子是 如何安排机器在一块电路板或其他物体上钻孔，其中需要 钻的孔可以看成是各个城市，而旅行的费用就是钻头从一 个孔移到下一个孔所花的时间。虽然钻孔的技术不断发展， 但无论何时，只要钻机设备的移动时间在所有制造业的过 程中占据显著的地位，TSP 在减少费用上就扮演了一个非 常重要的角色。 许多实际中出现的问题都可以转化成旅行商问题的模型而 解决。例如还有结晶学中的结构分析问题，车辆调度问题， 计算机布线问题，单个机器上的工序调度问题等等。

旅行商问题的计算复杂性 时间复杂性，即随着输入问题规模的增长，算法所需计算 步数的增长速度。 计算机科学家们有一个共识：即当输入规模n表示的算法 复杂性函数 f (n)是以多项式为界的，算法才被认为

是有效 的。 从本质上讲，所有的计算问题又可以归结为判定问题，如 果说：一个算法解决了某一判定问题，则算法输出“是”, 否则输出“非”。而从输入到输出，算法所需要运行的步 骤即为算法的时间复杂性。

很多优化问题，诸如旅行商问题、最小覆盖问题、 多处理器任务调度问题、背包问题等都被发现可 以多项式约化为 NP 中最难的问题，即 NP 完全 问题。 普遍认为多项式时间的算法是“好的算法”、 “有效的算法”,而所有的 NP 完全问题目前都 还没有找到多项式时间的算法，它们需要耗费时 间复杂性函数的数量级往往是指数级的，所以单 单依靠提高计算机的速度对问题的解决是非常有 限的

TSP的时间复杂度 TSP 搜索空间随着城市数 n 的增大而增大，所有的旅程 路线组合数为( n -1)!/2。 5 个城市的情形对应 120/10=12 条路线； 10 个城市的情景对应3628800/20=181440 条路线； 100 个城市的情景对应有 4.666×10155 条路线。 所以对于输入规模为n个城市的 TSP 找到最优解的时间复 杂性函数的数量级是 O( n!),当n 比较大时，耗费的时间 已经是个天文数字。 表 2.1 是在假定所用计算机每秒可以执行 10 亿次运算的 前提下，对不同的时间复杂性函数所耗费时间的比较。

求解旅行商问题的已有算法 多年来对 TSP 的研究，人们提出了许多求解方法， 其中有精确算法如线性规划方法、动态规划方法、 分支定界方法； 近似算法如插入法、最近邻算法、Clark&Wright 算法、生成树法、Christofides 算法、r-opt 算法、 混合算法、概率算法等。 近年来，还有很多尝试解决该问题的较为有效的 方法不断被提出，例如禁忌搜索方法、遗传算法、 模拟退火算法、神经网络方法、蚁群算法等。

基于灾变思想的GA实现TSP实例 遗传算法的局部搜索能力较强，但是很容易陷入 局部极值。 虽然增加变异概率可以搜索到远离当前极值的点， 但是新点的值往往不能和当前保留下来的较优值 相提并论，因为这些较优值都是经过千百代的进 化而存留下来的，于是远离当前极值的点往往在 两到三代以内 …… 此处隐藏：2167字，全部文档内容请下载后查看。喜欢就下载吧 ……