在本文中，我们解释了解决旅行商问题的公式、概念和算法。这个问题在管理的各个方面都有应用，包括服务运营、供应链管理和物流。
旅行推销员问题（TSP）
这是运营研究领域最有趣和最受研究的问题。
这种“易于州”和“难以解决”的问题引起了一直试图在实践中解决和使用结果的院士和从业者的注意力。
图片:pixabay
问题如下所示：
推销员必须访问n个城市，然后返回起点。他(她)应该怎样访问那些总距离是最小的城市?
假设启动城市包含在要访问的N城市（或点）中。由于该人返回到起点，因此任何N个城市都可以是起点。因此，对于给定的解决方案，存在相同的N-1其他解决方案。起始城市通常根本没有规定。任何城市都可以成为起始城市。对于N城市TSP，该人恰好行进了n弧（或n距离）
还有一个旅行推销员路径问题，其中指定了开始和结束点。这里的人提供N-1弧线并到达目的地。
通常在TSP语句中，还有一个提到这个人访问每个城市一次和只有一次然后回到起点。如果距离矩阵由欧氏距离构成，它满足三角不等式(给出三个点i, j, k, dik£dij + djk)，这将迫使销售人员访问每个城市一次，且仅一次。如果距离不满足三角形不等式，或者如果我们考虑成本或时间而不是距离，这些可能不满足三角形不等式，我们必须明确指出，人访问每个城市一次，而且只有一次。
旅行商问题的数学规划公式
用已知的距离矩阵D考虑N个城市TSP。我们考虑一个5个城市TSP用于解释制剂，距离矩阵在表中给出
——10 |
8 |
9 |
7 |
|
10 |
- |
10 |
5 |
6 |
8 |
10 |
- |
8 |
9 |
9 |
5 |
8 |
- 6 |
|
7 |
6 |
9 |
6 |
- |
如果销售人员在访问城市i后立即访问城市j，设Xij = 1，公式为
最小化σςdij xij
受到约束
σxij=1¼i
Σxij= 1∀j
xij = 0，1
让我们验证配方是否足够并满足TSP的所有要求。目标函数最小化了行进的总距离。约束确保仅访问每个城市一次。这种制剂显然不足，因为它是分配问题的制定。例如，可以是5x5分配问题的可行解决方案
X12 = x23 = x31 = x45 = x54 = 1。这对TSP来说是不可行的，因为这意味着这个人离开城市1去城市2，从那里去城市3，再回到城市1。他也去了城市4(从5?)，从5回来。这对TSP来说是不可行的，因为这包含子行程。例如
x12 = x23 = x31 = 1是城市的子流量1-2-3-1。显而易见的是，如果有一个子之旅，解决方案总是还有一个。我们有x45 = x54 = 1给出的另一个子电台是另一个x12 = x24 = x45 = x53 = x31 = 1表示解决方案1-2-4-5-3-1，而不是子之旅。它代表了完全的巡演，并且对TSP是可行的。制定应导致不具有子旅行的解决方案。我们需要添加副库消除约束。
对于5个城市TSP，我们可以具有长度为1,2,3或4的子流。例如，XJJ = 1是长度的子流程。我们间接地通过考虑DJJ =¥（显示为-IN）来消除长度1的子流量距离矩阵）。修复DJJ =¥不会允许XJJ = 1.这也将间接不允许4个城市的子系统，因为如果在5个城市TSP中有4个城市的亚型，那么必须有一个城市巡回赛。
一个形式Xij + Xji£1的限制将消除所有2城市的郊区旅游。这个必须加入到配方中。这也将消除所有3个城市的支线，因为一个3城市的支线应该导致一个2城市的支线在5城市的TSP。因此，添加双城郊区游消除约束将完成我们对5城TSP的制定。
完整的公式是
最小化σdijxij.
受到约束
σxij=1¼i
Σxij= 1∀j
xij + xji£1 1∀i，j
xij = 0，1
如果我们考虑六个城市TSP，我们必须添加2城市的子旅程消除限制，并添加了表格的3个城市的副库
Xij + Xjk + X ki£1 1∀i, j, k。
这大大增加了约束的数量。
一般来说，对于n个城市tsp，其中n是奇数，我们必须添加子学会消除约束，从而消除长度2到n-1的子流量，并且当n甚至时，我们必须添加用于消除长度2到n的子学会的子旅水库消除约束。
当n =6时，2城市子游消除约束的个数为6C2 = 15和3城市的子台楼的数量是6C3 = 20。
TSP的启发式算法
我们已经看到TSP是一个NP完全问题，分支定界算法(最坏情况枚举算法)可以用来最优地解决它们。我们没有多项式有界的算法来得到最优解。分支定界算法可以在一定规模内最优地解决问题。对于大型问题，我们必须开发近似算法或启发式算法。在本节中，我们将解释TSP的一些启发式算法。
最近邻居算法
在这个算法中，我们从一个城市出发，然后从那里向最近的城市前进。如果我们从城市1出发，我们可以到最近的城市，也就是城市5。从5号我们可以到达2号城市(2号和4号是相等的)，从2号我们可以到达4号，从4号我们可以到达3号城市。解是1-5-2-3 -1,Z = 34。
从城市2开始，移动到最近的邻居，我们通过z = 36获得解决方案2-4-5-1-3-2。
从3市开始，解是3-1-5-2-4-3,Z = 34
从城市4开始，解决方案是4-2-5-1-3-4，Z = 34
从5号城市开始，解决方案是5-2-4-3-1-5,Z = 34
最佳解为1-5-2-3 -1,Z = 34。这也是最优解。
最近邻搜索启发式是一种“贪婪”搜索启发式，即最后一个添加到列表中的城市没有被优化。因此，这可能会导致糟糕的结果。最近邻搜索的最坏情况性能界由
LH / LO£1 +（log10 n）/ 2
这表明，在最坏情况下，启发式算法与最优算法的距离为1 + log10 n倍。对于100城市问题，最坏情况界为2，表明启发式算法在最坏情况下可能是最优算法的两倍。
成对交互启发式启发式
我们从一个可行的解决方案开始，并通过在两个城市之间交换来改善它。在n城市问题中nC2互换是可能的，并且选择了最佳选择。
我们可以从任何序列开始，说1-2 -3-4-5 -1，z = 41.序列表示为1 -2-3-4-5，表明我们将从最后一开始就回到第一个城市。互换位置1和2我们通过z = 38获得序列2-1-3-4-5。这更好，我们接受这个解决方案。
我们将算法再次启动算法2-1-3-4-5，其中z = 38.在互换2和5上，我们得到5-1-3-4-2，z = 34.进一步的交换不完善
方案和评估后的最佳方案nC2互换为5-1-3-4-2-5，Z = 34。
这对明智的交汇处启发式评估nC2交换，可能会占用大量的CPU时间。有时我们使用相邻的成对交换，我们交换(n-1)个序列，取最好的，直到没有更多的改进是可能的。
这篇文章由印度理工学院勒克瑙分校的Sumit Prakash撰写
参考
i)希勒的《运筹学9e》
II）讲座笔记
iii) james fitzsimmons的服务管理
