旅行推销员问题（通常称为TSP）是计算机科学和运筹学领域的一个经典算法问题。它的重点是优化。在这种情况下，更好的解决方案通常意味着一个更便宜、更短或更快的解决方案。TSP是一个数学问题。它最容易表达为一个描述一组节点位置的图。

旅行推销员问题是由爱尔兰数学家W.R.汉密尔顿和英国数学家托马斯-柯克曼在19世纪定义的。汉密尔顿的Icosian游戏是一个基于寻找汉密尔顿周期的娱乐难题。TSP的一般形式似乎是在20世纪30年代由数学家在维也纳和哈佛大学首先研究的，特别是卡尔-门格尔。Menger定义了这个问题，考虑了明显的蛮力算法，并观察到最近的邻居启发式的非最优性。

我们用信使问题来表示（因为在实践中这个问题应该由每个邮递员解决，反正也是由许多旅行者解决），任务是为已知对向距离的无穷多的点找到连接这些点的最短路线。当然，这个问题是可以通过有限的试验来解决的。而将试验次数推到给定点的排列组合次数以下的规则，则是未知的。首先应该从起点到最近的点，然后再到离此点最近的点，等等规则，在一般情况下，不能得出最短的路线。

普林斯顿大学的哈斯勒-惠特尼在不久后就提出了旅行推销员问题的名称。