旅行商问题TravelingSalesmanProblem（TSP）.ppt

旅行商问题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)等等。 旅行商问题的应用和价值 旅行商问题是一个具有广泛的