假设有一个旅行商人想要参观n个城市。他必须选择他想走的路。路径的限制是每个城市只能访问一次，最终必须回到原来出发的城市。路径选择的目标是要求路径距离是所有路径中最小的（总长度）。

在运筹学和理论计算机科学中，旅行商问题（TSP）是一个 NP 难组合优化问题。考虑到两座城市之间的距离，找到访问每个城市一次的最短旅行。这是买家出行问题的一个特例。

TSP 有很多应用，甚至基于其最基本的概念本身，例如规划物流和制造微芯片。稍微修改一下，在许多领域它都是作为子问题出现的，例如 DNA 测序。在这些应用中，TSP 中的城市代表客户、焊接或冲压点或 DNA 片段，TSP 中的距离代表旅行时间或成本，或 DNA 片段之间相似性的度量。在许多应用中，诸如有限资源或时间窗口之类的附加约束使问题变得相当困难。

在计算复杂度理论中，TSP的决策版本（给定长度L，目标是确定是否存在比L更短的路径）属于NP完全问题类。因此，在最坏的情况下，任何算法求解 TSP 所需的运行时间很可能随着城市数量呈指数增长。

针对芯片制造或计算机设计中的常见问题。在这些领域，激光可用于在平板上钻出数以万计的小孔。为了节省成本，设计者不希望钻井行为成为一种随机行为，像“休闲游客”一样。他们希望在钻孔之前找到最短的“路径”，这样每个孔只被“访问”一次。事实上，数学家从 20 年代起就一直在研究这个“旅行商问题”。该问题于 1930 年首次被系统阐述，是数学和优化领域研究最深入的问题之一。它成为许多优化方法的基准。尽管该问题在计算上很困难，但已知大量启发式测试和精确方法可以解决涉及数万个城市的某些情况。

1954年，美国人为49个城市提供了“旅行商问题”的解决方案，2004年，瑞典人为24,978个城市提供了解决方案。不同的分支定界算法可用于 40 至 60 个城市的 TSP。改进的线性规划算法可以很好地处理包含200个城市的TSP。分支定界和具体生成是解决大量实例的首选方法。该方法目前已解决 85,900 个城市实例（2006 年）。 2001 年，使用 Ray 和 Ray 于 1954 年提出的基于线性规划的割平面方法，找到了针对 15,112 个德国城镇的解决方案。莱斯大学和普林斯顿大学在包含 110 个处理器的网络上进行了计算。总计算时间相当于 500 MHz 处理器运行 22.6 年。

2004年，旅行推销员问题得到解决，访问了瑞典全部24,978个城镇，行程长度约为72,500公里，并证明较短的行程不存在。

2005 年 3 月，使用 TSP 求解器解决了访问电路板上所有 33810 个点的旅行商问题。找到了单位长度的游览，并证明不存在更短的游览。计算出大约 15.7 个 CPU 年（Coolk 等人，2006 年）。

2006 年 4 月，使用 TSP 求解器求解一个具有 85900 点的实例需要超过 136 个 CPU 年（2006 年）。

如今，电子行业、发送包裹的物流公司，甚至日本弹珠机的制造（与弹球机一样，需要数千次手指敲击）最终都可以简化为这个数学问题，而它们的效率提升取决于它。回答。等人。 2007年就这个问题给出了非常出色且极其专业的回答。