旅行售货商问题（travelling salesman problem；TSP），理学-数学-图论-旅行售货商问题，一个组合优化问题。它在运筹学和理论计算机科学中被广泛研究，通常被描述为：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。背景旅行售货商问题的起源尚不清楚。一本1832年的手册曾提到旅行售货商问题，也包括通过德国和瑞士旅游的例子，但不包含数学问题的处理。19世纪初叶，爱尔兰数学家W.R.哈密顿和英国数学家T.柯克曼（Thomas Kirkman）提出了旅行售货商问题的数学问题。哈密顿的Icosian游戏是一种基于找到哈密顿圈的休闲游戏。维也纳和哈佛大学的数学家们在19世纪30年代首先研究了TSP的一般形式，尤其是K.门格（Karl Menger）。之后，普林斯顿大学的H.惠特尼（Hassler Whitney）介绍了旅行售货商问题这个名字。在20世纪50年代和20世纪60年代，这个问题在欧洲和美国的科学界变得越来越流行。