不访问每个节点的CVRP

Question

我有一个容量车辆路径模型的线性模型。现在我想限制活动边的最大数量，这将导致无法访问每个节点。但是，每条路线都应在站点（节点 0）开始和结束。我有以下型号：

输入：

n = Number of Clients
N = List of Nodes
V = List of nodes plus depot
Q = Vehicle Capacity
q = Demands per Client Dictionary

A = All Possible Roads (eg. [(0,1),(1,2),(2,3),(3,0),(2,0)])
c = All Distances Dictionary (eg. {(0, 1): 90, (1,2): 50, …})

型号：

mdl = Model('CVRP')

x = mdl.binary_var_dict(A, name='x')
u = mdl.continuous_var_dict(N, ub=Q, name='u')

# Objective: Maximize Profit (profit - cost)
mdl.maximize(mdl.sum(q[i]*x[i,j] - c[i,j]*x[i,j] for i,j in A))

# (1) Constraints: Make sure end once in each node
mdl.add_constraints(mdl.sum(x[i,j] for j in V if j!=i) == 1 for i in N)

# (2) Constraints: Make sure leave each node once
mdl.add_constraints(mdl.sum(x[i,j] for i in V if i!=j) == 1 for j in N)

# (3) Constraints: Fill of container is waste current contianer + past containers
mdl.add_indicator_constraints(mdl.indicator_constraint(x[i,j], u[i]+q[j]==u[j]) for i,j in A if i!=0 and j!=0)

# (4) Constraints: Have to take all waste from a container
mdl.add_constraints(u[i]>=q[i] for i in N)

solution = mdl.solve(log_output=True)

为了实现最大活动边的约束，我添加了以下约束：

# (5) Constraint: Set maximum of active edges
mdl.add_constraint(mdl.sum(x[i,j] for i,j in A) <= 6)

因此我应该将约束（1）和（2）中的'=='运算符调整为'<='。然而，结果是节点 0，即仓库，也不再是强制访问的。谁能帮我进一步解决这个问题？提前致谢！

Answer 1

为了强制进入和退出仓库，您不能放松仓库的 ==。因此，您必须为仓库和 non-depot 节点拆分约束 (1) 和 (2)：

# Depot
mdl.add_constraints(mdl.sum(x[0,j] for j in V if j!=i))
mdl.add_constraints(mdl.sum(x[i,0] for i in V if i!=j))
# Non-Depot
mdl.add_constraints(mdl.sum(x[i,j] for j in V if j!=i) <= 1 for i in N if N != 0)
mdl.add_constraints(mdl.sum(x[i,j] for i in V if i!=j) <= 1 for j in N if N != 0)

我没有考虑太多，但现在您可能还需要一个约束，要求所有节点的传入选定弧的数量等于传出选定弧的数量。也就是说，如果路由进入一个节点，那么它也必须离开该节点。

不访问每个节点的CVRP

CVRP without visiting each node

linear-programming

cplex

simplex

docplex

vehicle-routing