规划路径中的子回路
转自知乎: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方法。
刚刚其中V表示顶点集合;S表示集合V的真子集(即集合S≠V),|S|表示集合S中顶点的数量。上式其含义是:对于任意顶点集合的真子集S来讲,顶点间连通的边数之和小于等于顶点数减1.若路径含有子回路,如图2所示,对于顶点集合V的真子集{1,2,4},其连通的边数之和等于3,顶点数也等于3,违背了上面的式子。从而证明了上式能有效避免子回路。
新增变量u,其值不具有任何物理意义(只谈大小)。若经过边(i,j),则xij=1,上式可化成:
即:
因此,上式可确保经过的节点的u值保持增长趋势。对于图2中顶点集合{1,2,4}就有u1 对于方法一来讲,顶点集合的真子集包含了N种组合,从而约束条件的数量随着n的增加而成指数式增加。 对于方法二来讲,新增n个变量,约束条件增加n-1的平方个。 综上,规模越大,方法二的优势越明显。3、两种方法优劣比较: