旅行推销员问题

维基百科,自由的百科全书
跳转至: 导航搜索

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

旅行商问题的解

TSP是旅行购买者问题英语Travelling pruchaser problem车辆路径问题英语Vehicle routing problem的一种特殊情况。

计算复杂性理论中,TSP的做决定版本(其中,给定长度 L,任务是决定图中是否有路径比 L 还要短)术语NP完全问题。因此随着城市数量的增多,任何TSP算法最坏情况下运行时间都有可能随着城市数量的增多超多项式(可能是指数英语Exponential time hypothesis)级别增长。

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

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

描述[编辑]

作为图论问题[编辑]

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

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

非对称和对称[编辑]

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

相关问题[编辑]

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

整数线性规划形式[编辑]

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

 x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise} \end{cases}

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

\begin{align}
\min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} &&  \\
     & 0 \le x_{ij} \le 1  && i,j=0, \cdots, n  \\
     & u_{i} \in \mathbf{Z} && i=0, \cdots, n \\
     & \sum_{i=0,i\ne j}^n x_{ij} = 1 && j=0, \cdots, n \\
     & \sum_{j=0,j\ne i}^n x_{ij} = 1 && i=0, \cdots, n \\
&u_i-u_j +nx_{ij} \le n-1 && 1 \le i \ne j \le n
\end{align}

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

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

nk \leq (n-1)k,

这构成矛盾。

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

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

u_i-u_j\le n-1,

由于 u_i 不大于 nu_j 不小于1;因此,每当 x_{ij}=0 时满足约束。对于 x_{ij}=1,我们有:

  u_{i} - u_{j} + nx_{ij} = (t) - (t+1) + n = n-1,

满足约束。

参见[编辑]

注释[编辑]

  1. ^ 参见已解出精确解0.05%范围内的TSP世界巡游问题。[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.

参考文献[编辑]

  • Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook, W. J., The Traveling Salesman Problem, 2006, ISBN 0-691-12993-2 .
  • Arora, Sanjeev, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM, 1998, 45 (5): 753–782, doi:10.1145/290179.290180, MR 1668147 .
  • Beardwood, J.; Halton, J.H.; Hammersley, J.M., The Shortest Path Through Many Points, Proceedings of the Cambridge Philosophical Society, 1959, 55: 299–327, doi:10.1017/s0305004100034095 .
  • Bellman, R., Combinatorial Processes and Dynamic Programming, (编) Bellman, R., Hall, M., Jr. (eds.), Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10,, American Mathematical Society, 217–249, 1960 .
  • Bellman, R., Dynamic Programming Treatment of the Travelling Salesman Problem, J. Assoc. Comput. Mach., 1962, 9: 61–63, doi:10.1145/321105.321111 .
  • Berman, Piotr; Karpinski, Marek, 8/7-approximation algorithm for (1,2)-TSP, Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA '06), 641–648, 2006, doi:10.1145/1109557.1109627, ISBN 0898716055, Template:ECCC .
  • Christofides, N., Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, 1976 .
  • Hassin, R.; Rubinstein, S., Better approximations for max TSP, Information Processing Letters, 2000, 75 (4): 181–186, doi:10.1016/S0020-0190(00)00097-1 .
  • Held, M.; Karp, R. M., A Dynamic Programming Approach to Sequencing Problems, Journal of the Society for Industrial and Applied Mathematics, 1962, 10 (1): 196–210, doi:10.1137/0110015 .
  • Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M., Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs, In Proc. 44th IEEE Symp. on Foundations of Comput. Sci, 56–65, 2004 .
  • Kosaraju, S. R.; Park, J. K.; Stein, C., Long tours and short superstrings', Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci, IEEE Computer Society, 166–177, 1994 .
  • Orponen, P.; Mannila, H., On approximation preserving reductions: Complete problems and robust measures', Technical Report C-1987–28, Department of Computer Science, University of Helsinki, 1987 .
  • Padberg, M.; Rinaldi, G., A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems, Siam Review, 1991: 60–100, doi:10.1137/1033004 .
  • Papadimitriou, Christos H., The Euclidean traveling salesman problem is NP-complete, Theoretical Computer Science, 1977, 4 (3): 237–244, doi:10.1016/0304-3975(77)90012-3, MR 0455550 .
  • Papadimitriou, C. H.; Yannakakis, M., The traveling salesman problem with distances one and two, Math. Oper. Res., 1993, 18: 1–11, doi:10.1287/moor.18.1.1 .
  • Serdyukov, A. I., An algorithm with an estimate for the traveling salesman problem of the maximum', Upravlyaemye Sistemy, 1984, 25: 80–86 .
  • Steinerberger, Stefan, New Bounds for the Traveling Salesman Constant, Advances in Applied Probability, 2015, 47 .
  • Woeginger, G.J., Exact Algorithms for NP-Hard Problems: A Survey//Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570, Springer, 185–207, 2003 .

延伸阅读[编辑]

外部链接[编辑]