旅行商问题，适用于工业和创新

想象一下，在一个繁忙的配送中心，机器和工人在各个工作地点和存储地点之间以最佳方式移动。必须妥善规划路线，以满足严格的时间限制，并降低成本和其他因素。这一挑战正是历史上所谓的 旅行推销员问题 (TSP).它不仅应用于物流领域。这篇文章探讨了旅行推销员问题如何应用于现实生活和制造业。它探讨了如何改进所有行业的路线规划。

虽然这个问题是纯数学和算法研究中的经典问题，在物流领域也有更实用的研究方法，但在其他行业和制造领域几乎无人知晓。

这篇文章特别关注我们的文章 "工程学中需要了解的 10 种主要算法和方法 "中的一种算法。

关键要点

• 旅行推销员问题（TSP）是在几个点之间寻找最优化的路线。
• 这一问题在 1930-1940 年间开始受到关注。
• 它有助于各组织提高效率、降低运营成本、限制资源和改善服务提供。
• 这个问题广泛适用于不同部门和行业，而不仅仅是物流和运输业。
• 只要点数超过 12-20 个，问题就会变得过于复杂，无法计算出完美的解决方案
• 为了找到好的近似值，人们发明了几种算法，但并非完美的近似值

什么是旅行推销员问题？

旅行推销员问题 寻找最有效的方式，让销售人员访问各个城市，然后返回起点。他必须在每个城市只停留一次，并尽可能缩短总路程。

要理解 TSP 的定义，就要知道路线的数量会随着城市的增加而增加。例如，四个城市意味着有 24 条可能的路径。增加更多城市就会增加挑战，导致需要考虑的潜在路线过多。

许多企业，如物流、电信和制造业企业，经常面临这个问题。解决巡回推销员问题的好办法可以节约成本，提高效率。 它展示了与数学相关的理论研究如何帮助解决现实生活中的问题。

旅行推销员问题的历史

旅行推销员问题起源于 20 世纪初，这要归功于一些聪明的数学家。威廉-罗文-汉密尔顿（William Rowan Hamilton）和卡尔-门格尔（Karl Menger）是帮助我们了解如何在复杂路径上航行的大人物。他们真正关注的是如何更容易地找到最佳路线。

到 20 世纪 30 年代，人们开始更清晰地定义 TSP。来自维也纳和哈佛大学的学者们就此展开了合作。他们开始发现它可以解决实际问题，比如改善校车路线。这让更多人对解决 TSP 问题产生了兴趣。

TSP 对企业，尤其是航运和运输企业超级有用。二十世纪五六十年代，兰德公司挺身而出。他们提出了解决 TSP 的巧妙方法，这些方法成为使物流更加顺畅的关键部分。

为什么这是一个 NP 难问题？

旅行推销员问题（Traveling Salesman Problem）是计算机科学中的一个难题。它之所以被称为 "NP-hard "难题，是因为如果有很多城市，它的增长速度会呈指数级增长，超出任何计算机的处理能力，因此很难解决。

什么是 "NP-困难 "问题？ 在计算机科学和计算复杂性理论中，"NP "代表非确定多项式时间。一个 NP-困难问题至少和 NP 中最难的问题一样难，这意味着 NP 中的每个问题都可以用多项式时间还原成 NP-困难问题。与 NP-完全问题不同的是 可以在多项式时间内验证、 吨目前还没有一种已知算法能在多项式时间内解决 NP 难问题。

正因为如此，专家们使用特殊的快捷方式和聪明的猜测。这些技巧可以帮助他们找到相当不错的路径，而不需要不可能达到的计算能力，就能得到一个在现实生活中足够好用的像样的解决方案。请看下一章，其中一些方法可以帮助他们处理大量可能的路径。

工业应用

旅行推销员问题 不同行业 让路线和流程等事情变得更好。物流、运输和制造等许多领域都使用 TSP 来简化工作。TSP 近似解决方案及其变体可用于以下领域：

常见问题

为什么 TSP 被认为是 NP 难问题？

TSP 的难度很大，因为每增加一个城市，潜在路线的数量就会成倍增加。这就很难快速找到最佳路线，尤其是当增加的地点超过 20 个时。

TSP 有哪些常见应用？

TSP is used in many areas, like making delivery routes more efficient and managing supply chains. It’s also helpful in healthcare for scheduling visits and in 机器人 for guiding movements or in manufacturing electronics positioning or testing small components and copper routes.

图论和启发式算法与 TSP 有什么关系？

图论是 TSP 背后的数学原理。它用点（顶点）表示城市，用线（边）表示城市之间的路径。这有助于开发有效解决 TSP 问题的方法。启发式算法是解决 TSP 的智能捷径。它们有助于快速找到足够好的路径，即使它们并不完美。近邻算法和贪婪算法就是常见的例子。模拟退火和遗传算法等技术也特别适用于大型问题。