linear-programming - CVRP 无需访问每个节点
问题描述
我有一个容量车辆路线模型的线性模型。现在我想限制活动边的最大数量,这将导致并非每个节点都可以访问。但是,每条路线都应在站点(节点 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,即仓库,不再强制访问。任何人都可以进一步帮助我吗?先感谢您!
解决方案
为了强制进入和退出仓库,您不能放松==
对仓库的设置。因此,您必须为 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)
我没有考虑太多,但现在您可能还需要一个约束,要求所有节点的传入选定弧的数量等于传出选定弧的数量。也就是说,如果一条路由进入一个节点,那么它也必须退出该节点。
推荐阅读
- excel - 搜索字符串后出现的Excel提取值
- python - 下载文件硒python后的陈旧元素
- javascript - 如何使用 jquery 获取动态单选按钮的 id?
- python - 给定 3d 函数上的点 f(x,y,z) 和采样点 x,y 找到函数所在的 z
- javascript - 页面加载时引导 4 模式没有 jquery?
- php - 安装微风时 npm install && npm run dev 出错
- python - 机器人框架,DatabaseLibrary 插入 PASS 但没有新条目
- rust - Rust 闭包概念
- jms - 有没有办法通过 ActiveMQ Web 控制台 UI 监控咨询消息?
- android - React-Native Horizontal Scrollview 不起作用但适用于垂直