简介

旅行商问题(TravelingSalesmanProblem，TSP)是一个经典的组合优化问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。

研究历史

TSP的研究历史很久，最早的描述是1759年欧拉研究的骑士环游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。1954年，Geo~eDanzig等人用线性规划的方法取得了旅行商问题的历史性的突破——解决了美国49个城市的巡回问题。这就是割平面法，这种方法在整数规划问题上也广泛应用。后来还提出了一种方法叫做分枝限界法，所谓限界，就是求出问题解的上、下界，通过当前得到的限界值排除一些次优解，为最终获得最优解提示方向。每次搜索下界最小的分枝，可以减小计算量。1

分类

经典TSP

CTSP是在一个带权无向完全图中找一个权值最小的Hamilton回路。在各类TSP中，该类问题的研究成果最多。近几年来，研究者或者基于数学理论构造近似算法，或者使用各种仿自然的算法框架结合不同的局部搜索方法构造混合算法。同时，神经网络和自组织图方法在该问题上的应用研究也引起了研究者的关注。

不对称TSP

若在CTSP模型中，两个顶点i和j间的距离d不一定相等，则称为 ATSP。ATSP由于两点间距离的不对称性，所以求解更困难，但由于现实生活中多数实际场景都为不对称的TSP，所以对于基于实际交通网络的物流配送来说，其比CTSP更具有实际应用价值 。

配送收集TSP

TSPPD是由CTSP适应物流配送领域的实际需求而产生的。这个问题涉及到两类顾客需要：一类是配送需求，要求将货物从配送中心送到需求点；另一类是收集需求，要求将货物从需求点运往配送中心。当所有的配送和收集需求都由一辆从配送中心出发、限定容量的车辆来完成时，怎样安排行驶路线才能构成一条行程最短的 Hamilton回路。

多人旅行商问题

即多个旅行商遍历多个城市，在满足每个城市被一个旅行商经过一次的前提下，求遍历全部城市的最短路径。解决 MTSP对解决 “车辆调度路径安排 ”问题具有重要意义。过去的研究大多将 MTSP转化成多个TSP，再使用求解 TSP的算法进行求解。Hong Qu等人结合胜者全取 (winner—take—all)的竞争机制设计了一个柱形竞争的神经网络模型来求解MTSP，并对网络收敛于可行解进行了分析和论证。

多目标旅行商问题

CRISP的路径上只有一个权值 (即距离)，而 MoTSP研究的是路径上有多个权值的 TSP，要求找一条通过所有顶点并最终回到起点的回路，使回路上的各个权值都尽可能小。由于在多目标情况下，严格最优解并不存在，研究 MoTSP的目的是找到Pareto最优解，这是一个解集，而不是一个单一解。现阶段算法为构造一个求解单目标的遗传局部搜索算法，然后基于此求解多目标组合优化问题算法。

问题解法

旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP完全问题，所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种：

1、途程建构法（TourConstructionProcedures）

从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：