旅行商问题（英语：Travelling salesman problem，缩写：TSP）
是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。
问题内容为“给定一系列城市和每对城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路。”
TSP是旅行购买者问题与车辆路径问题的一种特殊情况。
作为计算复杂性理论中一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，
要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。
该问题被划分为NP完全问题。
已知TSP算法最坏情况下的时间复杂度随着城市数量的增多而成超多项式（可能是指数）级别增长。
问题在1930年首次被形式化，为优化中被研究得最深入的问题之一，许多优化方法都奉其为基准。
尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，
并且甚至能在误差1%范围内估计上百万个城市的问题。
甚至纯粹形式的TSP都有若干应用，如企划、物流、芯片制造。稍作修改，
就是DNA测序等许多领域的一个子问题。在这些应用中，
“城市”的概念用来表示客户、焊接点或DNA片段，
而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。
TSP还被应用在天文学中，减少在不同光源之间转动望远镜的时间。
在许多应用场景中（如资源或时间窗口有限等等），可能会需要加入额外的约束条件。
作为图论问题
四个城市的对称旅行商问题
可以用无向加权图来对TSP建模，则城市是图的顶点，道路是图的边，道路的距离就是该边的长度。
它是起点和终点都在一个特定顶点，访问每个顶点恰好一次的最小化问题。
通常，该模型是一个完全图（即每对顶点由一条边连接）。
如果两个城市之间不存在路径，则增加一条非常长的边就可以完成图，而不影响计算最优回路。
非对称和对称
在对称TSP问题中，两座城市之间来回的距离是相等的，形成一个无向图。
这种对称性将解的数量减少了一半。
在非对称TSP问题中，可能不是双向的路径都存在，或是来回的距离不同，形成了有向图。
交通事故、单行道和出发与到达某些城市机票价格不同等都是打破这种对称性的例子。
相关问题
图论中的一个等价形式是：
给定一个加权完全图（顶点表示城市，边表示道路，权重就会是道路的成本或距离）,
求一权值最小的哈密尔顿回路。
返回到起始城市的要求不会改变问题的计算复杂度，见哈密顿路径问题。
另一个相关问题是瓶颈旅行商问题（bottleneck TSP）：
求加权图中权重最大的边最小的哈密尔顿回路。
问题在运输和物流之外都有相当广泛的实际意义。
一个典型的例子是在印刷电路板制造中：规划打孔机在PCB版上钻孔的路线。
在机械加工或钻孔应用中，“城市”是需要加工的部分或需要钻的（不同大小）的孔，
而“旅行成本”包括更换机具所用的时间（单机作业排序问题）。
旅行推销员问题，处理“国家”中有（一个或多个）“城市”，
而旅行商需要在每个“国家”访问恰好一座“城市”。其中一种应用是在求解裁切问题时，
想要最小化刀具改变次数中。另一种应用与半导体制造业中的打孔有关，见美国专利第7,054,798号。
令人惊喜的是，
Behzad与Modarres证明了广义旅行商问题可以转化为相同城市数量的标准旅行商问题，
只是要改变距离矩阵。
优先顺序旅行推销员问题处理城市之间存在访问次序的问题。
旅行购买者问题涉及购买一系列产品的购买者。
他可以在若干城市购买这些产品，但价格会有不同，也不是所有城市都有售相同的商品。
目标是在城市的子集中间找到一条路径，使得总成本（旅行成本 + 购买成本）最小，
并且能够买到所有需求的商品。