规划路径中的子问题——子圈消去的DFJ和MTZ约束

规划路径中的子回路

转自知乎：https://zhuanlan.zhihu.com/p/159270139

TSP问题包含两个重要的约束。约束1：进入点i的次数与从点i出发的次数相等，且次数为1；约束2：消除子回路约束。

对于TSP问题，图1和图2所示路径都满足约束条件1，但只有图1是正确的路径（仅仅有一个回路，TSP问题的特点）；而像图2将一个回路拆成了两个及两个以上的回路情况，将每个回路称为子回路，需要建立合适的约束条件来消除此种情况，即约束条件2。

VRP问题本身存在多条回路，但是对于每一辆车所服务的需求点，也不允许出现子回路现象。

目前，网络上消除子回路的方法有两种。方法一由Dantzig,Fulkerson and Johnson提出，称之为DFJ方法；方法二由Miller Tucker and Zemlin提出，称之为MTZ方法。

1、DFJ方法：

刚刚其中V表示顶点集合；S表示集合V的真子集（即集合S≠V），|S|表示集合S中顶点的数量。上式其含义是：对于任意顶点集合的真子集S来讲，顶点间连通的边数之和小于等于顶点数减1.若路径含有子回路，如图2所示，对于顶点集合V的真子集{1，2，4}，其连通的边数之和等于3，顶点数也等于3，违背了上面的式子。从而证明了上式能有效避免子回路。

2、MTZ方法：

新增变量u，其值不具有任何物理意义（只谈大小）。若经过边（i，j），则xij=1,上式可化成：

即：

因此，上式可确保经过的节点的u值保持增长趋势。对于图2中顶点集合{1，2，4}就有u1<u2<u4<u1，产生了矛盾，因此，可有效避免出现子回路。

3、两种方法优劣比较：

对于方法一来讲，顶点集合的真子集包含了N种组合，从而约束条件的数量随着n的增加而成指数式增加。

对于方法二来讲，新增n个变量，约束条件增加n-1的平方个。

综上，规模越大，方法二的优势越明显。