旅行推销员问题的形成与概念
在本文中，我们解释了解决这一问题的公式、概念和算法称为旅行推销员问题。这些问题在管理的各个方面都有应用，包括服务运营、供应链管理和物流。
旅行商问题(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-3 - 4-2-3 -1的解，不是子路径。它代表了一个完整的旅行，是可行的TSP。该配方应该导致解决方案没有子旅游。我们需要添加子环消除约束。
对于5个城市的TSP，我们可以有长度为1、2、3或4的subtours。例如，Xjj = 1是长度为1的子环。我们通过考虑djj =¥(在距离矩阵中表示为a -)间接消除长度为1的子旅行。修正djj =¥将不允许Xjj = 1。这也间接地不允许4个城市的子游，因为如果5个城市的TSP中有4个城市的子游，那么就必须有1个城市的子游。
形式Xij + Xji£1的约束将消除所有2城subtours。这必须加入到配方中。这也将消除所有3个城市的次游，因为3个城市的次游应该导致5个城市的TSP中的2个城市的次游。因此，加入2市副游消除约束将完成我们对5市TSP的制定。
完整的公式是
最小化∑∑dij Xij
受
∑Xij = 1∀i
∑Xij = 1∀j
Xij + Xji£11∀i, j
Xij = 0,1
如果我们考虑6个城市的TSP，我们必须添加2个城市的子游消除约束，同时还要添加3个城市的子游消除约束的形式
Xij + Xjk + X ki£11 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-3 -1-3-4,Z = 34
从5号城市开始，解决方案是5-2-3 -5,Z = 34
最佳解是1-5-2-3 -1,Z = 34。这也是最优解。
最近邻域搜索启发式是一种“贪婪”搜索启发式，即最后一个添加到列表中的城市没有得到优化。因此，这可能会带来不好的结果。最近邻搜索的最坏情况性能由
Lh/Lo£1 + (log10n)/2
这表明，在最坏情况下，启发式与最优解的距离是1 + log10n的一倍。对于一个100城市的问题，最坏情况的界限是2，这表明启发式在最坏情况下可以是最优解的两倍。
两两交换启发式
我们从一个可行的解决方案开始，并试图通过两两交换城市来改善它。在一个城市问题中nC2交换是可能的，并选择最好的。
我们可以从任意序列开始，比如1- 2,3 - 4,5 -1 Z = 41。序列用1-2-3 -4-5表示，表示我们将从最后一个城市回到第一个城市。将1和2互换位置，得到序列2-1-3-4-5,Z = 38。这样更好，我们接受这个解决方案。
我们用初始解2-1-4 -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希勒著
(二)课堂笔记
iii) james fitzsimmons的《服务管理》
