什么是子回路

在不同的问题中子回路的定义略有不同，例如在TSP中子回路是不包含所有节点的闭环，而在VRP中则是指起点和终点都不是depot的环，如图（B）所示。尽管定义有所不同，但是他们消除子回路的方式是相同的。本文介绍两种最常见的子环路消除约束：MTZ和DFJ约束。

DFJ约束

DFJ约束的原理

DFJ约束来源于一个非常直观的认识，即对于任意一个子回路来说，一定满足该回路中所包含的弧的数量等于该回路中所包含的点的数量，其中表示的是这个子环路中所包含的点的集合，它是图中所有点的集合的一个真子集。

于是，想要破除子回路，我们只需要破坏上述条件就可以了，这样就得到了DFJ约束。

注：这里为什么有，因为只有只有一个点的话是绝对不可能形成子回路的，而当时，实际上就是，这个时候满足的就是我们想要刻画的那个回路，当然不能删掉了。

DFJ约束的实现

我们知道任何一个集合的真子集个数为个，所以DFJ约束是一个指数数量级的约束，想要在建模初期就把所有的DFJ约束全部写出来时非常不现实的。在实现上我们一般是将它作为惰性约束处理，在求解过程中通过一定的方法逐步加入。以VRP问题中设置DFJ约束为例，首先我们要设计一个子回路的检测算法，将所有子回路检测出来，然后再设计一个回调函数，根据我们检测到的子回路添加惰性约束。

子回路检测算法
def findAllSubroutes(solution:ndarray)->Dict[int,List[List]]:
	route_dict = {} # subtours of each car
	for k in range(solution.shape[2]):
		subtour_kcars = [] # subtours of car k
		# check subtours of car k 
		for i in range(1,solution.shape[1]-1):
			flag = False 
			subtour_kcars_start_i = [] # subtours of car k that starts from point i 
			for j in range(1,solution.shape[1]-1):
				# car k moved from point i to j
				if solution[i,j,k] > 0.9:
					subtour_kcars_start_i.append(i)
					subtour_kcars_start_i.append(j)
					current_point = j 
					# cheack whether i->j formed a subtour
					while not flag:
						for next_point in range(1,solution.shape[1]):
							if solution[current_point,next_point,k] >  0.9:
								subtour_kcars_start_i.append(next_point)
								current_point = next_point
							# we find a subtour start from ponstallint i
							if subtour_kcars_start_i[0] == subtour_kcars_start_i[-1]:
								flag = True
								subtour_kcars.append(subtour_kcars_start_i)
								break
							# car k finally arrived point (solution.shape[2]-1) means i->j didn't form a subtour
							if current_point == solution.shape[1]-1:
								flag = True
								break
				else:
					continue
		route_dict[k] = subtour_kcars
	return route_dict

回调函数
def generateDFJConstraint(model,where):
	# each time when gurobi find a feasible solution,we check whether we should add some DFJ constraints
	if where ==  GRB.Callback.MIPSOL:
		solution = zeros((len(_data.V),len(_data.V),len(_data.K))) # save the solution results in matrix format
		for key,value in x.items():
			idx1,idx2,idx3 = key
			solution[idx1,idx2,idx3] = _model.cbGetSolution(value)
		route_dict = findAllSubroutes(solution) # 找到当前解对应的所有子回路
		for k in _data.K:
			for subtour_kcars_start_i in route_dict[k]:
				# Now we get the set S(subtour_kcars_start_i[:-1])
				_model.cbLazy(
					quicksum(x[i,j,k] for i,j in _data.A if (i in subtour_kcars_start_i[:-1] and j in subtour_kcars_start_i[:-1])) 
					<= len(subtour_kcars_start_i[:-1])-1
					)

MTZ约束

MTZ约束我觉得是一个更加巧妙的消除子回路的方法，并且实现上非常简单。它消除子回路的思想是：赋予每个节点一个变量，恰当的定义变量的含义，使得该变量取值随着节点的访问次序单调增加或单调减小。例如，我们假设是基地及其复制点，是网络中的卸货港，那么就是一条子回路，在当前定义下应该大于同时又小于，这显然是矛盾的，从而这样的环路就被排除掉了。而对于我们预期的环路则完全满足MTZ约束而不会被排除。一种典型形式的MTZ约束是将定义为节点的访问次序，于是MTZ约束可以使用下式表示。