1、旅行商问题Traveling Salesman Problem（TSP）旅行商问题的发展历史 旅行商问题，也称货郎担问题，是一个较古老的问题。其起源已经有些模糊了。最早大概可以追溯到 1759 年 Euler 提出的骑士旅行问题。 十九世纪初，爱尔兰数学家 William R. Hamilton和英国数学家 Thomas P. Kirkman研究过一些与旅行商问题相关的数学问题。 二十世纪初，人们开始研究通用形式的旅行商问题。 二十世纪二十年代，数学家和经济学家 Karl Menger 在维也纳向他的同事提出了这个问题。 二十世纪三十年代，旅行商问题出现在 Princeton 大学的数学圈子里
2、，主要的推动者有 Hassler Whitney 与 Merrill Flood。 二十世纪四十年代，统计学家 (Mahalanobis(1940), Jessen(1942), Gosh(1948), Marks(1948)把它和农业应用联系在一起研究。美国 RAND 公司也推动了这个问题的发展。 最终， 旅行商问题成为了组合优化问题中的一个困难问题原型的典型代表 。求解这种问题令人望而生畏：当问题规模变大的时候，路径的数目将是个天文数字，逐一检查它们几乎是不可能的。在很长的一段时间内，没有任何解决这个问题的好想法出现 . 1954 年，旅行商问题的求解终于获得了突破。 George Dan
3、tizig, Ray Fulkerson 和 Selmer Johnson 提出了一个求解旅行商问题的算法并用它成功地解决了一个有 49 个城市的实例。这个规模在当时相当引人注目 ; 1977 年， Groetschel 找到了有 120 个城市的旅行商问题的最优路径 ; 1987年， Padberg 与 Rinaldi 找到了规模为 532 和 2392 的旅行商问题的最优路径； Groetschel与 Holland找到了规模为 666的旅行商问题的最优路径。 Applegate, Bixby,Chavtal 和 Cook 于 1994 年 ,1998年和 2001年解决了规模为 7397
4、, 13509和 15112的旅行商问题。 2004 年，一个具有 24978 个城市的旅行商问题的最优路径由 Applegate, Bixby,Chavtal, Cook 和 Helsgaun 找到。这是到目前为止 精确找到最优解 的最大规模的旅行商问题 . 旅行商问题吸引了越来越多的人对它进行研究。其中，有数学家，计算机科学家，运筹学家，还有一些其它领域的研究者。 然而， 该问题是否存在一个有效的通用的求解方法仍然是一个开放性的问题 。事实上，旅行商问题的解决将意味着 P=NP问题的解决。 Clay Mathematics Institute 曾悬赏 100 万美元来寻求这个问题的解法，但
5、没人拿到这个奖。旅行商问题的描述 旅行商问题 (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、任意两个城市
6、间的距离都是对称的，它对应的是图论中的 无向图 ；2、两个城市间的距离是非对称的，它对应的是图论中的有向图 ； 从问题本身的限制条件的强弱，主要有三类：1、 不做任何限制 (但是一般都要求城市间的费用不为负数 )，只给出距离矩阵，求最短回路；2、要求距离间要满足 三角不等式 ；3、定义在欧氏平面上的 TSP，即 Euclidean TSP，它给出每个城市在欧氏平面上的坐标，而城市间的距离就是以它们的 欧氏距离 来定义。 从问题的多项式可解性上分， TSP 可以分为两类：1、目前己经知道有多项式时间算法可解的，比如其距离矩阵满足特定的条件 (Demidenko 条件、 Kalmanson 条件、
7、 Supnick 条件 )等；2、目前尚没有发现多项式时间算法可解的，而研究热点是如何寻找更多的多项式时间可解的情形。 对旅行商问题的研究经过几十年的发展，已经产生了许多其它 扩展形式 ,例如多旅行商问题 (Multi-Salesman Problem),多目标旅行商问题 (Multi-Objective TSP)等等。旅行商问题的应用和价值 旅行商问题是一个具有广泛的实用背景与重要的理论价值的组合优化难题。 许多关于 TSP 的工作并不仅是由实际应用直接推动的，而是因为 TSP 为其它一般的各类算法提供了思想方法平台，而这些算法广泛地应用于各种离散优化问题。 其次， TSP 大量的直接应用给研究领域带来了生机，并引导了未来的工作 运输问题是 TSP 最自然的应用。由于其模型的简单性，TSP 在其它一些领域有着有趣的应用。一个经典的例子是如何安排机器在一块电路板或其他物体上钻孔，其中需要钻的孔可以看成是各个城市，而旅行的费用就是钻头从一个孔移到下一个孔所花的时间。虽然钻孔的技术不断发展，但无论何时，只要钻机设备的移动时间在所有制造业的过程中占据显著的地位， TSP 在减少费用上就扮演了一个非常重要的角色。 许多实际中出现的问题都可以转化成旅行商问题的模型而解决。例如还有结晶学中的结构分析问题，车辆调度问题，计算机布线问题，单个机器上的工序调度问题等等。
