在本文中，我们解释了解决这个问题的制定，概念和算法，称为旅行推销员问题。这种问题在管理的各个方面具有应用，包括服务运营，供应链管理和物流。
旅行推销员问题（TSP）
这是运营研究领域最有趣和最受研究的问题。
这种“易于州”和“难以解决”的问题引起了一直试图在实践中解决和使用结果的院士和从业者的注意力。
图片：Pixabay.
问题如下所示：
推销员必须访问n个城市并返回起点。他（她）应该如何访问城市，以便旅行的总距离最低？
假设启动城市包含在要访问的N城市（或点）中。由于该人返回到起点，因此任何N个城市都可以是起点。因此，对于给定的解决方案，存在相同的N-1其他解决方案。起始城市通常根本没有规定。任何城市都可以成为起始城市。对于N城市TSP，该人恰好行进了n弧（或n距离）
还有一个旅行推销员路径问题，其中指定了开始和结束点。这里的人提供N-1弧线并到达目的地。
通常在TSP语句中，还有一个提到这个人访问每个城市一次和只有一次并返回起点。如果距离矩阵由欧几里德距离制成，它满足了三角不等式（给定三个点I，J，K，Dik£Dik£Dik£Dik + 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. |
- |
如果推销员在访问城市之后立即访问City J 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，回来到城市他也去城市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城市的子我们应该导致5个城市TSP中的2城市的子大楼。因此，增加了2城级的亚古无法消除约束将完成我们的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城市子旅游消除约束的数量是6.C2 = 15和3城市的子台楼的数量是6.C3 = 20。
TSP的启发式算法
我们已经看到TSP是NP完成问题，分支和绑定算法（最坏情况枚举算法）可用于最佳地解决它们。我们没有多项式有界算法来获得最佳解决方案。分支和绑定算法可以最佳地解决问题，最多尺寸。对于大型问题，我们必须开发近似算法或启发式算法。在本节中，我们向TSP解释了一些启发式算法。
最近的邻居算法
在这种算法中，我们从一个城市开始，然后从那里前往最近的城市。如果我们从城市开始，我们可以前往最近的城市，这是城市5.从5我们可以到达城市2（2到4之间有一个领带），我们可以达到4我们到达城市3。该溶液为1-5-2-4-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-4-3-1，Z = 34。这也恰好是最佳解决方案。
最近的邻居搜索启发式是一个“贪婪”搜索启发式，其中未在列表中添加的最后城市未得到优化。因此这可以给出差的结果。对最近的邻居搜索的最坏情况突出
LH / LO£1 +（log10 n）/ 2
这表明，在最坏的情况下，启发式将远离最佳1倍+ log10 n。对于100个城市问题，最坏的情况绑定是2表示启发式可以是最坏情况下最佳的两倍。
成对交互启发式启发式
我们从可行的解决方案开始，并尝试通过交换城市进行改进。在一个城市问题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，Iim Lucknow撰写
参考
i）Hiller的操作研究9e
II）讲座笔记
III）James Fitzsimmons的服务管理
