1

我有一个容量车辆路线模型的线性模型。现在我想限制活动边的最大数量，这将导致并非每个节点都可以访问。但是，每条路线都应在站点（节点 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，即仓库，不再强制访问。任何人都可以进一步帮助我吗？先感谢您！

4

1 回答 1

3

为了强制进入和退出仓库，您不能放松==对仓库的设置。因此，您必须为 depot 和 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)

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

于 2019-05-08T14:00:01.617 回答