旅行推销员问题——公式和概念
在这篇文章中，我们解释了解决这个问题的公式、概念和算法，称为旅行商问题。这些问题在管理的各个方面都有应用，包括服务运营、供应链管理和物流。
旅行商问题(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 -5-3-1，而不是子行程。它代表了一个完整的行程，对TSP是可行的。配方应导致解决方案没有子行程。我们需要添加子行程排除约束。
对于5个城市的TSP，我们可以有长度为1、2、3或4的子旅游。例如，Xjj = 1是长度为1的子游历。通过考虑djj =¥(在距离矩阵中表示为a -)，我们间接地消除了长度为1的子行程。修正djj =¥将不允许Xjj = 1。这也间接地不允许4个城市的子旅游，因为如果在5个城市的TSP中有一个4个城市的子旅游，就必须有一个1个城市的子旅游。
Xij + Xji£1形式的约束将消除所有2城市的子旅游。这必须加入到配方中。这也将消除所有3个城市的子旅行，因为3个城市的子旅行将导致5个城市TSP中的2个城市的子旅行。因此，加入2城子游剔除约束，就完成了5城TSP的制定。
完整的公式是
最小化∑∑dij Xij
受
∑Xij = 1∀i
∑Xij = 1∀j
Xij + Xji£11 1∀i, j
Xij = 0,1
如果考虑6个城市的TSP，我们必须添加2个城市的子旅行排除约束，还必须添加一个形式为3个城市的子旅行排除约束
Xij + Xjk + xki£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-4- 1,Z = 34。
从城市2开始，移动到最近的邻居，我们得到了解2-4-5-1-3-2,Z = 36。
从城市3开始，解决方案是3-1-5-2-4-3,Z = 34
从城市4开始，解是4-2-5-1-3-4,Z = 34
从城市5开始，解是5-2-4-3-3 -1-5,Z = 34
Z = 34时，最佳方案为1-5-2-4- 1。这也是最优解。
最近邻搜索启发式是一种“贪婪”搜索启发式，其中最后一个要添加到列表中的城市没有得到优化。因此，这可能会产生较差的结果。最近邻域搜索的最坏情况性能界限由
Lh/Lo£1 + (log10 n)/2
这表明，在最坏的情况下，启发式将以1 + log10 n的因素远离最优。对于一个100个城市的问题，最坏情况的界限是2，表明启发式可以在最坏的情况下是最优的两倍。
成对交换启发式
我们从一个可行的解决方案开始，并试图通过成对交换城市来改进它。在n个城市的问题中nC2交换是可能的，并选择最好的。
我们可以从任何序列开始，比如1-2 -3-4-5 -1,Z = 41。该序列由1 -2-3- 5表示，这表明我们将从最后一个城市回到第一个城市。交换位置1和2，我们得到序列2-1-3-4-5,Z = 38。这样比较好，我们接受这个解决方案。
我们用Z = 38的初始解2-1-3-4-5重新开始算法。在互换2和5时，我们得到5-1-3-3 -2,Z = 34。进一步的交流不会改善
方案和评估后的最佳方案nC2的交汇处是5-1-3-4-2-5,Z = 34。
成对交换启发式计算nC2进行交换，可能会占用相当多的CPU时间。有时我们使用相邻的成对交换，其中我们交换(n-1)个序列，取最好的，直到没有更多的改进可能。
本文作者是印度管理学院勒克瑙分校的Sumit Prakash
参考
i)希勒《运筹学9e》
(二)课堂笔记
iii) james fitzsimmons的《服务管理》
