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

TSP是旅行购买者问题与车辆路径问题的一种特殊情况。

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

The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.