旅行商问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地，应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路1。
由于其可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。因为在NP完全问题中，要找到一个最优解可能需要花费指数级的时间，随着问题规模（城市数量）的增大，计算量会迅速增长。
TSP问题在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。例如，在物流配送中，如何规划送货路线使得货车经过所有的送货地点并且总路程最短，这就类似于旅行商问题
声明：文章来源于网络，如有侵权请联系删除！