规划路径中的子回路
转自知乎：https://zhuanlan.zhihu.com/p/
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的平方个。
综上，规模越大，方法二的优势越明显。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/42040.html