作者：彭澜

纽约州立大学水牛城分校工业工程系在读博士生，研究方向：车辆路径规划问题（VRP）

旅行商问题（TSP）是运筹学领域最知名的问题之一。本文将从整数规划模型建模的角度，介绍七种不同的建模方式，给大家提供对TSP的不同视角。

引言

本文将讨论“茴”字的六种写法，啊不对，旅行商问题的五类共七种建模模型。首先是两个最经典的模型，即DFJ模型和MTZ模型，这两个模型相信了解运筹学的朋友都有所接触，本文仅作少量拓展介绍。接下来的两类模型分别是基于货物流和最短路的模型，在国内现行的教材和中文材料中介绍较少，借此文也给大家提供一些思路。最后一个模型是分配问题模型，讨论了同样是解决TSP，采取最糟糕的建模方式的情况下模型能有多糟糕，也算是一个很有意思的角度。

Dantzig-Fulkerson-Johnson模型

首先我们来介绍TSP发展历史上的第一个基于割平面法的，也是最重要的模型——Dantzig-Fulkerson-Johnson（DFJ）模型。一看名字就知道，这三位都是运筹学巨擘：G. Dantzig是单纯形法的发明者，R. Fulkerson和L. Ford Jr. 共同发明了最大流网络问题中的经典的Ford-Fulkerson算法, S. M. Johnson是Ford-Johnson排序算法的发明者之一，该排序算法在提出后的20年内一直是排序算法中已知需要进行排序次数最少的。DFJ模型自1954年提出以来，一直都在TSP和VRP（车辆路径规划问题）的研究中占据核心的地位，其子回路消除约束也启发了各类TSP或VRP拓展模型。

对于DFJ模型，我们定义决策变量为0-1变量xij:

模型的目标函数可以写作

DFJ模型只有三组约束条件，如下

 其中，约束（3）和约束（4）是流平衡约束，意味着对于每一个顾客（或仓库站点），都会从上一个顾客处出发去访问该顾客，也会从该顾客处出发去访问下一个顾客。但是如果只有这两组约束，我们只能保证每个顾客都连接到其他顾客处，无法保证所有的顾客都连接在同一条回路上，也就是无法避免下图所示的情形：

我们将这种无法覆盖所有顾客的回路称作子回路（subtour），约束（5）的目的就是消除所有的这种子回路，从而保证全局只有一条回路且该回路覆盖了所有节点。约束（5）的内容是，对于所有节点的集合V的所有子集合，如果这个子集合S不是只有一个节点或者包含了所有节点的特殊情形，那么，必须要有一条边从子集合S外出发，进入子集合S，且有另一条边从子集合S出发，到达子集合外的节点上。这样一来，所有的节点就都必须连接在同一条回路上，形成TSP的完整回路。

另一种对约束（5）等价的描述方式如下：

约束（6）的意思是，同样地，对于这些子集合，子集合内的节点之间的连边必须小于|S|-1，这样在子集合内就无法形成回路（对于n个节点，形成回路至少要n条边）。

由于子集合S是节点集合V的子集，而这种子集的数量是指数规模的，也就是说，在有n个顾客的算例中，DFJ模型的约束数量是级别的，决策变量的个数是级别的。这就使得直接使用DFJ模型，罗列出所有的约束条件后进行求解不具有可行性，因此，通常我们会使用Lazy约束来进行求解。

所谓的Lazy约束其实是指在模型建立的时候不添加这组子回路约束，每次求解得到可行解（这里的可行解是指没有添加子回路约束的情况下的可行解，对于TSP本身不一定是可行解）后验证得到的解，如果解中存在子回路，那么就将子回路对应的约束添加进模型中，继续/重新对模型进行求解。这样一来，在绝大多数情况下，我们就不需要涉及到所有子回路约束，而只需要添加相对之下非常少量的约束就能进行求解。

目前运筹学领域常用的求解器（包括Gurobi，CPLEX等）都提供了callback功能，也就是在求解的过程中，一旦搜索到一个整数解，就调用callback函数，添加约束。由于求解采用的是割平面法，添加约束后依然可以继续进行，所以模型求解不需要停下来。另一种实现方法相对简单，就是不使用callback功能，采用一个大的for loop，同样是先不添加任何子回路约束，然后在for loop中每次求解完成后判断是否产生了子回环，如果产生，那么添加对应的约束，重新求解整个模型，直至求得的解不包括子回路为止。有趣的是，后者虽然看上去一定比前者的效率低，但实际上并不一定，在一些少数情况下也有可能采用第二种方法的DFJ反而运算速度更快些。本文的最后我们将对比两种方法的运算效率（分别记作DFJ_Lazy和DFJ_PlainLoop）。

 Miller-Tucker-Zemlin模型

在DFJ模型中，虽然得到的可行域非常紧凑，但子回路约束的个数是指数增长的，学界为了替代这组约束进行了诸多尝试。著名的Miller-Tucker-Zemlin（MTZ）模型则通过增加了一组辅助决策变量解决了约束数量指数增长的问题。 

MTZ模型的决策变量包括DFJ模型中（1）所定义的0-1决策变量和整数随机变量。其中为访问节点i的次序，若。特别地，如果我们指定第1个节点为仓库，则有。MTZ模型的目标函数与DFJ模型相同，即前文所述的（2），流平衡约束，即（3）和（4），也与DFJ模型相同，不同的是，对于子回路约束，即（5）或（6），MTZ模型使用以下约束进行代替：

 其中，大M法的M可以被进一步缩小为n-1，因为两个节点的访问次序的差不会超过n-1。所以（7）可以进一步缩紧为：

类似的，MTZ模型还有另一种更易于推广的建模方法，即采用到达节点i的时间ti作为决策变量，则若。其中是从节点i到节点j所需要的时间。那么我们可以将约束（7）（8）改写成

这种改写的好处在于至少可以在以下两方面进行拓展：首先，如果顾客访问时间存在时间窗约束，即，这一模型可以很容易的通过引入类似于以下约束的办法实现:

 其次，如果我们需要决定是否在访问节点后进行某项其他的任务，我们也可以用MTZ模型来建立类似于如下约束

 其中是在节点i后，节点j前执行该认为需要的时间，而是确定是否执行该任务的0-1变量。

总的说来，MTZ模型共需要级别的约束数量，级别的0-1决策变量，还有个整数变量。约束的数量比DFJ模型要少，但是实际上约束不如DFJ模型紧凑。

 基于货物流的模型

 另一类消除子回路约束的TSP模型采用货物流进行建模，包括单类流模型（Single-Commodity Flow，SCM)，双类流模型（Two-Commodity Flow，TCM）和多类流模型（Multi-Commodity Flow，MCM）。单类流模型又称作Gavish-Graves（GG）模型，和MTZ模型一样，SCM模型采用了DFJ一样的目标函数（2），流平衡约束（3）（4）和决策变量的定义（1），不同的依然是对子回路约束（5）的处理。子回路约束被替换为以下约束：

 其中（15）可以被进一步缩紧替换为：

模型中是新引入的辅助决策变量，含义是在边上经过的流量。约束（15）中的n-1依然是大M法，由于流量不能大于n-1，于是用n-1代替中的大M。这个模型的逻辑是每个节点都需求一个货物，从仓库出发，携带了n-1个货物，即约束（16），每经过一个顾客放下一个货物，即约束（17）。这样一来，我们就无法形成子回路，因为如果有子回路那么不包括仓库的子回路里就没法放下货物。之所以被称作“单类流”（Single-Commodity Flow）是因为货物的种类只有一种。

类似的，可以得到双类流模型，即将子回路约束替换为：

其中，和是新引入的辅助决策变量，含义是在边上经过的两种不同货物的流量。其中一种货物（货物A）在从仓库出发时的数量是n-1个，每次经过一个顾客就放下一个货物A，另一种货物（货物B）在从仓库出发的时候数量为0个，每次经过一个顾客就搜集一个货物B。举个例子，牛奶配送员从配送站出发，给每家每户送牛奶，每到一家就放下一瓶牛奶（货物A），并把那家的空瓶子（货物B）带回去。与单类流模型类似，这种方式同样也避免了子回路。

进一步的，对于多类流模型，子回路约束将被替换为：

其中是第k种货物在经过i到j时的流量。而货物一共有n种，也就是每到一个顾客那里就留下一种货物，送完为止。约束（26）与约束（15）和约束（20）类似，只不过这里的大M直接取1就行，因为每类货物只有1件。约束（27）和约束（28）表示从仓库出发的时候每种货物只带了1件，回来的时候都送出去了。约束（29）和约束（30）表示，第k种货物送到第k个顾客的时候留在了顾客那里。而约束（31）则表示不是该顾客的货物在经过顾客的时候不会被留下。

这几种方法大同小异，其实是在模拟送货的整个过程，我们可以将这三个模型合起来看待，在后文的对比分析中，将对多类流模型的运算效率和其他模型进行对比。

最短路模型

现在我们回到TSP的定义，我们要找的是一条访问了所有节点的最短的路径，既然是最短的路径，那就意味着我们可能可以通过类似于解决最短路的方法来解决TSP。如下图所示，我们可以构造一个图，在这个图中，每列为所访问的节点的编号，最短路从节点1出发，经过n步，遍历通过所有节点并返回节点1。则这样的最短路就是我们要求的TSP路径。

值得指出的是，最短路问题是一个P问题，存在多项式时间内可解的算法，但这并不意味着TSP也是一个P问题（众所周知，TSP是一个经典的NPC问题）。原因在于，我们寻找的最短路不仅仅是一条最短路，同时增加了不能重复访问节点的约束条件，也就是说，在上图中，从左往右当我们每确定一条边的时候，右边的边就会发生变化，所以我们并不是在一个“静态”的图上寻找的最短路径。但这并不妨碍我们借鉴网络流模型中解决最短路问题所用到的约束条件。

对于最短路模型，决策变量为0-1变量，定义如下

 则目标函数为

 首先参考最短路问题的网络流模型，得到最短路相关的约束

约束（34）~（38）描述的是除了起点和终点（也就是仓库），其他的节点流入的次数等于流出的次数，其实也就是与之前模型中（3）（4）等价的流平衡模型，只不过是换了一种形式。接下来的约束是要求所有的顾客不会被重复访问：

 

 这样我们就得到了基于最短路的TSP整数规划模型。由于这个模型中存在n个阶段（也就是图中所示的t=0，t=1等），这个模型又被称作Time-staged模型。

分配模型

接下来，just for fun，我们介绍一个解决TSP的非常糟糕的整数规划模型，也就是分配模型，或者称作Quadratic模型（QAP）。注意到我们要找的TSP路径可以看作是一组长度为n的空“盒子”，构造TSP路径相当于把每个节点放入其中一个空“盒子”，这就把TSP问题转换为一个分配问题（Assignment Problem）了。

那么我们可以得到决策变量如下： 

约束则为分配问题的约束条件，即每个顾客只能分配到一个“盒子”，每个“盒子”只能分配一个顾客：

决策变量和约束确定后，我们该来讨论目标函数了（而这目标函数却是最需要技巧性的一步）。与其他模型采用0-1决策变量来确定TSP中是否存在从节点i到节点j不同，要确定分配模型中TSP的通路，我们需要不止一个决策变量。例如，要确定是不是存在从节点i到节点j的通路，我们需要看第1个“盒子”和第2个“盒子”里有没有i和j，再看第2个“盒子”和第3个“盒子”里有没有i和j，一直到第n-1个“盒子”和第n个“盒子”里有没有i和j，由于“盒子”其实是首位相接的，最后还要看第n个“盒子”和第1个“盒子”里有没有i和j。于是，我们得到了目标函数如下：

如果TSP路径中存在从i到j的边，那就会通过某个k使得（或）被激活从而计入目标函数。糟糕的是，这目标函数不是线性函数，而是二次函数。那既然是二次函数，我们就将其线性化，得到如下新的目标函数：

 和补充的约束：

下面我们继续讨论证明这个模型有多糟糕。我们知道，在求解整数规划的时候，最常见且基础的方法是分支定界法（Branch and Bound），而分支定界法通常是先进行线性松弛，然后对于其中非整数的决策变量进行分支，分别向上向下取整，得到两个子问题，然后分别进行求解，如果得到了整数解就更新上界（目标函数为最小化），如果搜索完子树后仍得不到非整数解就更新下界（目标函数为最小化），如此分支搜索，更新上下界直至找到最优解。

这个方法在这里就遇到了敌手。我们对这个模型进行线性松弛，得到的解是

这意味着每个决策变量都是对称的，都需要进行分支定界，线性松弛没有给我们提供任何帮助。因此，用这个方法求解我们可以观察到求解过程中下界会非常难以收敛，事实上，求解过程将按最糟糕的方式，分支遍历搜索全部个分支。在下一小节的对比中我们也可以看到QAP模型的下界收敛的速度之慢。

几种模型的对比分析 

在本文的最后，我们来对比一下通过本文涉及的几种建模方式分别求解TSP的速度。如下表所示，我们随机生成包括了15，20，25，30，50，70个顾客的六个算例，使用gurobi在python环境下进行求解。从对比中我们可以看出，采用了lazy cut的DFJ模型要明显好于其他几种模型，即使是用了较低效率进行迭代的DFJ模型也表现相当抢眼。另一方面，用于对比的最差的二次型模型在600秒内甚至无法收敛求得规模最小的15个顾客算例的解（实际上可接受的时间范围内能够解的规模差不多在12~13个左右）。同时我们注意到，另一类常用的MTZ模型的运算速度在添加了时间戳的辅助变量后依然在可接受范围内，这也是众多研究者选择基于该模型构建进行多种TSP变种模型（例如，考虑时间窗的TSP）的原因之一。

最后，本文算例分析所使用gurobi代码的链接如下：

https://github.com/isaac0821/vrpSolver/blob/master/vrpSolver/ipTSP.py

亦可参考以下链接来对比不同的TSP模型：

https://github.com/isaac0821/vrpSolver/blob/master/demo/TSP_IP.ipynb

欢迎感兴趣的读者前往交流探讨。

参考文献：

[1] Dantzig, George, Ray Fulkerson, and Selmer Johnson. "Solution of a large-scale traveling-salesman problem." Journal of the operations research society of America 2.4 (1954): 393-410.

[2] Miller, Clair E., Albert W. Tucker, and Richard A. Zemlin. "Integer programming formulation of traveling salesman problems." Journal of the ACM (JACM) 7.4 (1960): 326-329.

[3] Gavish, Bezalel, and Stephen C. Graves. "The travelling salesman problem and related problems." (1978).

[4] Langevin, André, François Soumis, and Jacques Desrosiers. "Classification of travelling salesman problem formulations." Operations Research Letters 9.2 (1990): 127-132.

[5] Wong, Richard T. "Integer programming formulations of the traveling salesman problem." Proceedings of the IEEE international conference of circuits and computers. IEEE Press Piscataway NJ, 1980.

[6] Finke, Gerd. "A two-commodity network flow approach to the traveling salesman problem." Congresses Numeration 41 (1984): 167-178.

[7]  Deineko , Vladimir G., and Gerhard J. Woeginger. "A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem." Mathematical programming 87.3 (2000): 519-542.