万维百科

旅行推销员问题

旅行商问题(英语:travelling salesman problem, 旅行商问题)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学理论计算机科学中非常重要。

旅行商问题的解

旅行商问题是旅行购买者问题英语travelling purchaser problem车辆路径问题的一种特殊情况。

作为计算复杂性理论中的一个典型的判定性问题,旅行商问题的一个版本是给定一个图和长度 L,要求回答图中是否存在比 L 短的回路(英语:circuit或tour)。该问题被划分为NP完全问题。已知旅行商问题算法最坏情况下时间复杂度随着城市数量的增多而成超多项式(可能是指数英语Exponential time hypothesis)级别增长。

问题在1930年首次被形式化,并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难,但已经有了大量的启发式和精确方法,因此可以完全求解城市数量上万的实例,并且甚至能在误差1%范围内估计上百万个城市的问题。

甚至纯粹形式的旅行商问题都有若干应用,如企划物流芯片制造。稍作修改,就是DNA测序等许多领域的一个子问题。在这些应用中,“城市”的概念用来表示客户、焊接点或DNA片段,而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。旅行商问题还用在天文学中,观察很多光源的天文学家会希望减少在不同光源之间转动望远镜的时间。在许多应用场景中(如资源或时间窗口有限等等),可能会需要加入额外的约束条件。

描述

作为图论问题

四个城市的对称旅行商问题

可以用无向加权图来对旅行商问题建模,则城市是图的顶点,道路是图的,道路的距离就是该边的长度。它是起点和终点都在一个特定顶点,访问每个顶点恰好一次的最小化问题。通常,该模型是一个完全图(即每对顶点由一条边连接)。如果两个城市之间不存在路径,则增加一条非常长的边就可以完成图,而不影响计算最优回路。

非对称和对称

对称旅行商问题问题中,两座城市之间来回的距离是相等的,形成一个无向图。这种对称性将解的数量减少了一半。在非对称旅行商问题问题中,可能不是双向的路径都存在,或是来回的距离不同,形成了有向图交通事故单行道和出发与到达某些城市机票价格不同等都是打破这种对称性的例子。

相关问题

  • 另一个相关问题是瓶颈旅行商问题英语bottleneck traveling salesman problem[译名请求](bottleneck 旅行商问题):求加权图中权重最大的最小的哈密尔顿回路。问题在运输和物流之外都有相当广泛的实际意义。一个典型的例子是在印刷电路板制造中:规划打孔机在PCB版上钻孔的路线。在机械加工或钻孔应用中,“城市”是需要加工的部分或需要钻的(不同大小)的孔,而“旅行成本”包括更换机具所用的时间(单机作业排序问题)。
  • 旅行推销员问题,处理“国家”中有(一个或多个)“城市”,而旅行商需要在每个“国家”访问恰好一座“城市”。其中一种应用是在求解裁切问题英语cutting stock problem时,想要最小化刀具改变次数中。另一种应用与半导体制造业中的打孔有关,见美国专利第7,054,798号。令人惊喜的是,Behzad与Modarres证明了广义旅行商问题可以转化为相同城市数量的标准旅行商问题 ,只是要改变距离矩阵
  • 优先顺序旅行推销员问题处理城市之间存在访问次序的问题。
  • 旅行购买者问题涉及购买一系列产品的购买者。他可以在若干城市购买这些产品,但价格会有不同,也不是所有城市都有售相同的商品。目标是在城市的子集中间找到一条路径,使得总成本(旅行成本 + 购买成本)最小,并且能够买到所有需求的商品。

整数线性规划形式

单钻头的运动可以看成是典型的旅行商问题问题。旅行商问题可以用整数线性规划来形式化。 用数字 0, ..., n 标记这些城市(打孔位置),并定义:

对于 i = 0, ..., n,令 为一人工变量,最后把 作为从城市 ij 的距离。那么旅行商问题可以写成下面的整数线性规划问题:

第一组等式要求每个城市都能另一个城市前来,而第二组等式要求每个城市都能出发。最后的约束迫使覆盖所有城市的路径只有一条,而不是两条或者多条分散的路径在一起覆盖的。要证明这一点,下面会去证 (1)每个可行解包含只有一条封闭城市序列,以及(2)对于每条覆盖所有城市的单独路径,虚拟变量 有值可以满足限制式。

证明可行解中的每个子回路经过0号城市(注意到等式保证了只有一条这样的路径),就能证明所有可行解只包含一个封闭城市序列。对于若我们对所有 对应的不等式求和的话,对 k 步不经过0号城市的任何子回路,我们得到:

这构成矛盾。

必须证明对每个覆盖所有城市的单独回路,虚拟变量 有值可以满足约束。

为了不失一般性,定义起始点为0号城市。如果在第 t 步访问城市 i 后 (i, t = 1, 2, ..., n) 选取 。则

由于 不大于 n 不小于1;因此,每当 时满足约束。对于 ,我们有:

满足约束。

参见

注释

  1. ^ 参见已解出精确解0.05%范围内的旅行商问题世界巡游问题。[1]
  2. ^ Behzad, Arash; Modarres, Mohammad, New Efficient Transformation of the Generalized Traveling Salesman Problem into Traveling Salesman Problem, Proceedings of the 15th International Conference of Systems Engineering (Las Vegas), 2002
  3. ^ Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, Mineola, NY: Dover, 1998 , pp.308-309.
  4. ^ Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)
  5. ^ Dantzig, George B. (1963), Linear Programming and Extensions, Princeton, NJ: PrincetonUP, pp. 545–7, ISBN 0-691-08000-3, sixth printing, 1974.

延伸阅读

外部链接


本页面最后更新于2021-09-09 15:03,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器