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

旅行商问题1 引言在运筹学和理论计算机科学中，旅行商问题（TSP）是一个NP-困难的组合优化问题。通过给出成对的城市间距离，找到每个城市恰好访问一次最短的周游。它是购买者旅行问题的一个特殊情况。问题最早是在1930年作为数学问题和优化中最深入研究的问题之一被系统地阐述。它成为许多优化方法的一个基准。 虽然问题难以计算，但已知大量的启发式检测和确切方法，可以解决含有数以万计城市的某些情况。 TSP有许多应用，甚至基于它最本质的概念本身，如规划，物流，制造微芯片。 略作改动，在许多领域中，它作为子问题出现，如DNA测序 。 在这些应用中，TSP中的城市代表的是,客户，焊接点，或DNA片段，TSP中的距离代表的是，行驶时间或成本，或DNA片段之间的相似性度量。 在许多应用中，额外的限制，如有限的资源或时间窗口使问题变得相当困难。 在计算复杂性理论中，TSP的决定版本（给定一个长度L，目标是判断是否有比L短的任何周游） 属于np完全问题的一类。 因此，很可能在最坏的情况下 ，解决TSP的任何算法所需的运行时间随城市数量的增加而成倍增加。 2 历史 旅行商问题的起源目前还不清楚。一本1832年的手册提到了旅行推销员的问题，其中有德国和瑞士周游的例子，但书中未含数学处理。旅行商问题在19世纪被爱尔兰数学家W. R.和英国数学家Thomas Kirkman所阐述。Hamilton的Icosian游戏就是一个基于找到哈密顿圈的休闲游戏。一般形式的TSP，最早在1930年的维也纳和哈佛大学被数学家特别是Karl Menger所研究，Karl Menger定义了问题，考虑了显然的蛮力算法，并考察了非最近邻的启发式： 我们表示信使问题 （因为在实践中，每个邮递员都要解决这个问题，许多游客也一样），它的任务是，已知有限多点及其成对距离，找到最短的连接路线。当然，这个问题是可解的有限多个试验。 规则可使试验的次数少于给定点的排列种数，但它不为人所知。首先从起点到最近点，然后从该点到离它最近的下一点，这样的规则一般不构成不了最短路线。 Hassler Whitney在普林斯顿大学介绍了TSP后， 这个问题很快在20世纪五六十年代的欧洲和美国科学界流行。在圣莫尼卡，兰德公司的George Dantzig ，Delbert Ray Fulkerson 和 Selmer M. Johnson，为此做出了贡献 ，他们把TSP作为一个整数线性规划和改进的切割平面问题求解。 有了这些新的求解方法，他们构建了一个最佳周游，解决了一个含49个城市的实例，同时证明没有其它的周游可以更短。 在接下来的几十年中，问题被许多数学，计算机科学，化学，物理和其他科学的研究者做了研究。 Richard M. Karp在1972年研究表明， 哈密顿圈问题是NP完全的，这意味着TSP是NP-困难的。 这提供一个数学解释，为什么找到最佳周游有明显的计算难度。 在20世纪70年代末和1980年，问题有了重大突破，Grötschel, Padberg, Rinaldi和其他人一起，采用切割平面法与分支定界，完全成功地解决最多含2392个城市的实例。 在20世纪90年代，Applegate, Bixby, Chvátal, and Cook开发了“协和”程序，在最近的许多求解中被使用。 1991年，Gerhard Reinelt 公布了TSPLIB，其搜集了不同难度的例子，被许多研究小组用于比较结果。2005年，cook和其他人由一个芯片布局问题找到了通过33810个城市的最佳周游，这是目前TSPLIB中最大的求解实例。 对于其它含以百万计城市的许多实例，可以找到问题求解，且保证有1是一个最佳周游。 3 描述 3.1 作为一个图形问题 TSP可以转化为无向带权图，如同，城市是图的顶点 ，路径是图的边，路径距离是边长。 这是一个最小化问题，开始和结束在一个指定的顶点，其它顶点恰好访问一次。一个哈密顿圈是TSP的一个最佳周游则每边的距离成正比。通常情况下，该模型是一个完全图（即每对顶点是由边相连）。 如果两个城市之间没有路径存在，增加一个任意长度不影响最佳周游的边，成为完全图。 3.2 非对称和对称 在对称的TSP中，两个城市之间在每一个相反的方向的距离是一样的，形成一个无向图。 这种对称将可能的求解分半。 在不对称的TSP中，可能不存在双向路径或双向路径不同，形成一个有向图 。交通事故，单行道，不同时间和价格的机票正是破坏这种对称性的例子。3.3 相关问题 在图论中的一个等价命题是：给定一个完全带权图（其中顶点表示城市，边表示的路径，权值表示成本或距离），找到权值最小的哈密顿环。返回出发城市的要求，并不改变问题的计算复杂性，看哈密尔顿路径问题。 另一个相关的问题是瓶颈旅行商问题 （瓶颈TSP）：在带权图中找到关键边权值最小的一个汉密尔顿环 。 问题具有相当的实际意义，除了在明显的运输和物流领域，一个典型的例子是制造印刷电路调度的路线钻机在PCB上钻孔。在机械加工或钻孔应用中，“城市”是零件或钻的孔（尺寸不同），“遍历的开销”包含为更换零件（单机作业排序问题）的时间。 广义旅行商问题涉及“州”，（一个或多个）“城市”，推销员从各个“州”拜访每个“城市”一次， 也被称为“旅行政治家问题”。令人惊讶的是，Behzad和Modarres发现，广义旅行商问题可以转化成与城市数量相同的一个标准的旅行商问题，是修改后的距离矩阵。 顺序排序问题涉及访问一系列相互存在优先关系城市的问题。旅行商问题解决购买者购买一套产品。 他可以在几个城市购买这些产品，但价格不同，同时不是所有城市提供相同的产品。目标是在所有城市中找到一条路径，最大限度地减少总开销（旅行开销+采购开销）。4 计算的解决方案 解决NP-困难问题的传统思路有以下几种： 1）设计算法找到确切的解决方案（只适用于小的问题，这将很快完成）。 2）制定“次优”或启发式算法 ，即算法看似或可能提供良好的解决方案，但它不能被证明是最佳的。 3）找出问题（子问题）的在特殊情况下的解或启发式是可能的。4.1 计算复杂性 问题已被证明是NP-困难问题 （更确切地说，它是复杂类 FP NP）， 决策问题版本（给定的开销和一个数x，判断是否有比 X便宜路径）是NP完全问题 。 瓶颈旅行商问题，也是NP-困难问题。取消每个城市“只访问一次”这个条件，并不能消除Np-困难，因为很容易看到，在平面的情况下最佳的周游一定是每个城市只访问一次（否则，由三角不等式可知，一条跳过重复访问的捷径不会增加周游的长度）。 4.2 近似的复杂性在一般情况下，找到最短的旅行商问题的周游，是NPO-完全。若距离是可度量和对称的，问题就变为APX-完全。Christofides的算法约在1.5 以内。 如果限制为1和2（但仍然是一个度量），近似比为7/ 6。在不对称，计量的情况，只有对数性能可以保证，目前算法最好的实现性能为0.814log n; 如果存在一个常数因子近似，则它是一个开放的问题。 相应的最大化问题找到最长的旅行商周游逼近63/ 38 。如果距离函数是对称的，最长周游可以通过确定性算法和随机算法近似在4/ 3。4.3 精确算法 最直接的办法，是尝试所有的排列（有序组合），看看哪一个是开销最小（使用蛮力搜索）。 这种方法的时间复杂度为O(n!)，城市数量的阶乘，所以这种求解，即使只有20个城市也是不切实际的。动态规划的最早的应用之一是HeldKarp算法 ，解决问题时间复杂度为O(n22n)。 动态规划解决方案，需要指数的时间复杂度。使用列入-排除 ，可以在2n时间和空间内解决问题。 改善这些时间效率似乎很难。 例如，尚不知道是否存在TSP的精确算法，时间复杂度为O(1.9999n)。4.4 其他方法包括 1）不同的分支定界算法，可用于40-60个城市的TSP。 2）改进的线性规划的算法，很好地处理含200个城市的TSP。 3）分支限界和具体切代，是解决大量实例的首选方法。 当前这种方法拥有解决85900个城市实例的记录（2006年）。 一个为15112个德国城镇的求解，于2001年在TSPLIB中被发现，其使用1954年，George Dantzig, Ray Fulkerson, 和 Selmer M. Johnson提出的割平面法，基于线性规划。莱斯大学和普林斯顿大学对含有110个处理器的网络进行了演算，总计算时间相当于一个500兆赫处理器工作22.6年。在2004，旅行商问题访问所有24978个城镇在瑞典被解决，周游长度约72500公里，同时被证明了不存在更短的周游。2005年3月，在一块电路板上的访问所有33,810点的旅行商问题通过使用协和TSP的求解器被解决：一个长度为66048945单位的周游被发现，同时证明没有更短的周游存在。 计算了约15.7 CPU年（Cook等，2006）。2006年4月，85900点的一个实例使用协和TSP的求解器，解决时间超过136的CPU年（2006年） 。4）启发式近似算法 多种能迅速产生良好的求解的启发式近似算法，已经被制定。现在的方法可以在合理的时间内解决非常大的问题（含以百万计的城市），且只有23%的概率远离最优解。建设性启发式 最近邻（神经网络）算法 （或所谓的贪婪算法）让推销员选择未访问过的最近城市作为他的下一步行动目标。 该算法快速产生一个有效的短路径。 对于随机分布在一个平面上的N个城市，该算法平均产生的路径比最短的路径长的25。然而，存在着许多特殊分布的城市，使神经网络算法给出最坏的路径 (Gutin, Yeo, and Zverovich, 2002)。 这是对称和非对称旅行商问题真正的问题(Gutin and Yeo, 2007)。 Rosenkrantz等人研究表明，神经网络算法具有近似因子(log  | V | )的情况下满足三角不等式。 基于最小生成树的构造的近似比为2 。Christofides算法达到了1.5的比例。 Bitonic周游是一组点的最小周长构成的单调多边形 ，它可以通过动态规划有效地计算。 另一种建设性的启发式，两次比较合并（MTS）(Kahng, Reda 2004 )，执行两次连续的匹配，第二次匹配在删除所有第一次匹配的边后执行。然后合并，以产生最终的周游。迭代改进 ，成对交换，或LinKernighan启发式 ，成对交换或2-技术涉及反复删除两条边和替换那些建立一个新的和更短的周游所不需要的边。 这是一个K-OPT方法的特殊情况。 请注意，LinKernighan经常是 2-OPT的误称。 LinKernighan实际上是一个更一般的方法。 k-opt启发式 ，一个给定的周游，删除k相互不相交的边。将其余部分重新组合成一个周游，留下不相交子周游（即，不相连的一个部分的终点在一起）。 这实际上使正在考虑的TSP简化为一个简单得多的问题。 每部分端点有2K-2个其他的连接可能性：2 K总体终点可连接，则该部分是不能考虑的。 这种受约束的2K - TSP然后可以用蛮力方法解决，找到最低开销的原部分重组。K-opt是一种特殊情况下的 V-opt或variable-opt技术。 最流行的K opt是3-opt，这些都是由贝尔实验室的Shen Lin在1965年推出的。 有一个边不相交的3 - OPT特殊情况（两边相邻）。 v-opt启发式 ，variable-opt方法与k-opt方法相关，是K-opt方法的推广。而K -opt从原来的周游删除一个固定的数（K），variable-opt方法不删除固定大小的边集。相反，他们搜索过程中继续成长。 在这里已知最好的方法是LinKernighan的方法（上面提到作为一个2-OPT 误称）。Shen Lin和 Brian Kernighan在1972年首次公布他们的方法，这作为最可靠的解决旅行商问题的启发式近二十年。更先进的variable-opt方法是在贝尔实验室在80年代后期由David Johnson和他的研究团队发展。这些方法（有时被称为）在LinKernighan方法上，从禁忌搜索和进化计算添加了一些方法。基本的LinKernighan技术给出的结果，是保证至少3 -opt。 LinKernighanJohnson方法计算的LinKernighan周游，然后通过所谓移动至少四条边和以不同方式连接周游的突变打乱周游，然后以V-opt方法建立新的周游。 v-opt方法被广泛认为是解决问题的最强大启发式，并能够在特殊情况下解决问题，如汉密尔顿环问题和其他非十进制的TSP，而其他启发式做不到。多年来，Lin-Kernighan-Johnson已经被证明是对TSP所有已经尝试过的求解中的最佳求解。7 Traveling salesman problem 1 Introduction The traveling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once. It is a special case of the Traveling purchaser problem. The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved. The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents traveling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder. In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether any tour is shorter than L) belongs to the class of NP-complete problems. Thus, it is likely that the worst case running time for any algorithm for the TSP increases exponentially with the number of cities. 2 HistoryThe origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, but contains no mathematical treatment. William Rowan HamiltonThe travelling salesman problem was defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman. Hamiltons Icosian Game was a recreational puzzle based on finding a Hamiltonian cycle. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger, who defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic: We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route. Hassler Whitney at Princeton University introduced the name travelling salesman problem soon after. In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the USA. Notable contributions were made by George Dantzig, Delbert Ray Fulkerson and Selmer M. Johnson at the RAND Corporation in Santa Monica, who expressed the problem as an integer linear program and developed the cutting plane method for its solution. With these new methods they solved an instance with 49 cities to optimality by constructing a tour and proving that no other tour could be shorter. In the following decades, the problem was studied by many researchers from mathematics, computer science, chemistry, physics, and other sciences. Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours. Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2392 cities, using cutting planes and branch-and-bound. In the 1990s, Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions. Gerhard Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2005, Cook and others computed an optimal tour through a 33,810-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 1% of an optimal tour. 3 Description 3.1 As a graph problem TSP can be modeled as an undirected weighted graph, such that cities are the graph's vertices, paths are the graph's edges, and a path's distance is the edge's length. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. An Hamiltonian cycle is a optimal tour of a TSP where each edge has a distance proportional to the distance. Often, the model is a complete graph (i.e., an edge connects each pair of vertices). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour. Symmetric TSP with four cities TSP can be modeled as an undirected weighted graph, such that cities are the graph's vertices, paths are the graph's edges, and a path's distance is the edge's length. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. An Hamiltonian cycle is a optimal tour of a TSP where each edge has a distance proportional to the distance. Often, the model is a complete graph (i.e., an edge connects each pair of vertices). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour. 3.2 Asymmetric and symmetric In the symmetric TSP, the distance between two cities is the same in each opposite direction, forming an undirected graph. This symmetry halves the number of possible solutions. In the asymmetric TSP, paths may not exist in both directions or the distances might be different, forming a directed graph. Traffic collisions, one-way streets, and airfares for cities with different departure and arrival fees are examples of how this symmetry could break down. 3.3 Related problems An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight. The requirement of returning to the starting city does not change the computational complexity of the problem, see Hamiltonian path problem. Another related problem is the bottleneck traveling salesman problem (bottleneck TSP): Find a Hamiltonian cycle in a weighted graph with the minimal weight of the weightiest edge. The problem is of considerable practical importance, apart from evident transportation and logistics areas. A classic example is in printed circuit manufacturing: scheduling of a route of the drill machine to drill holes in a PCB. In robotic machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to drill, and the "cost of travel" includes time for retooling the robot (single machine job sequencing problem). The generalized traveling salesman problem deals with "states" that have (one or more) "cities" and the salesman has to visit exactly one "city" from each "state". Also known as the "traveling politician problem". One application is encountered in ordering a solution to the cutting stock problem in order to minimise knife changes. Another is concerned with drilling in semiconductor manufacturing, see e.g. U.S. Patent 7,054,798. Surprisingly, Behzad and Modarres demonstrated that the generalised travelling salesman problem can be transformed into a standard travelling salesman problem with the same number of cities, but a modified distance matrix. The sequential ordering problem deals with the problem of visiting a set of cities where precedence relations between the cities exist. The travelling purchaser problem deals with a purchaser who is charged with purchasing a set of products. He can purchase these products in several cities, but at different prices and not all cities offer the same products. The objective is to find a route between a subset of the cities, which minimizes total cost (travel cost + purchasing cost) and which enables the purchase of all required products. 4 Computing a solution The traditional lines of attack for the NP-hard problems are the following1) Devising algorithms for finding exact solutions (they will work reasonably fast only for small problem sizes). 2) Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver either seemingly or probably good solutions, but which could not be proved to be optimal. 3) Finding special cases for the problem ("subproblems") for which either better or exact heuristics are possible. 4.1 Computational comple