python - 如何修复不满足 biner 约束的 PuLP VRP 模型
问题描述
我创建了一个 VRP(使用 python PuLP 的车辆路由问题模型,但它找不到满足所有约束的最佳解决方案。
使用这个 xls 文件:https ://drive.google.com/file/d/1s7rOQCULynGxQk8_IMlvHl286d4WfdPt/view?usp=sharing
import pulp, pandas, itertools
import numpy as np
xls =pandas.ExcelFile('data node VRP 2.xls')
weight = pandas.read_excel(xls,'Sheet1')
sheet2 = pandas.read_excel(xls, 'Sheet2')
matrixjarak = pandas.read_excel(xls, 'matrixjarak')
#weight=sheet1.as_matrix()
vehicle=sheet2.as_matrix() #vehicle
matrixjarak=matrixjarak.as_matrix()
model = pulp.LpProblem("VRP Problem", pulp.LpMinimize)
d = weight['demand']
c = matrixjarak
J = np.arange(len(c)-5) #create array 0..
p = np.arange(len(vehicle))
C = vehicle
x = pulp.LpVariable.dicts("nodes to nodes",
((r,i,j) for i in J for j in J for r in p),
lowBound=0,
cat='Biner')
model += (
pulp.lpSum([
c[i][j]*x[(r,i,j)]
for i in J for j in J for r in p if i != j])
)
#1 in out always 1
for i in range(1,len(J)-1):
model += pulp.lpSum([x[r,i,j] for j in range(1,len(J)-1) for r in p if i != j]) == 1
#model += pulp.lpSum([x[r,i,j] for j in range(1,len(J)-1) for r in p if i != j]) == 1
for j in range(1,len(J)-1):
model += pulp.lpSum([x[r,i,j] for i in range(1,len(J)-1) for r in p if j != i]) == 1
#model += pulp.lpSum([x[r,i,j] for j in range(1,len(J)-1) for r in p if i != j]) == 1
#2 capacity
for r in p:
model += pulp.lpSum([d[i]*x[r,i,j] for i in J for j in J if i != j]) <= 70 #l[v]
#3 go from depot
for r in p:
model += pulp.lpSum([x[r,0,j] for j in J for r in p]) == 1
#4 back to depot
for r in p:
model += pulp.lpSum([x[r,i,0] for j in J for r in p]) == 1
#5
for r in p:
for h in J:
model += pulp.lpSum([x[r,i,h] for i in J if i != h]) - pulp.lpSum([x[r,h,j] for j in J if h != j]) == 0
model.solve()
pulp.LpStatus[model.status]
for var in x:
var_value = x[var].varValue
print("nodes", var[1]," move to nodes ",var[2],"with vehicle ",var[0],"adalah", var_value)
print("cost optimal",pulp.value(model.objective))
我希望它会为 x[r,i,j] (决策变量)产生 0 和 1 输出。但它会导致十进制输出:
nodes 0 go to nodes 0 with vehicle 0 are 0.875
nodes 0 go to nodes 6 with vehicle 0 are 0.125
nodes 1 go to nodes 2 with vehicle 1 are 1.0
nodes 2 go to nodes 1 with vehicle 1 are 1.0
nodes 3 go to nodes 6 with vehicle 1 are 0.23333333
nodes 3 go to nodes 6 with vehicle 2 are 0.76666667
nodes 4 go to nodes 5 with vehicle 2 are 1.0
nodes 5 go to nodes 4 with vehicle 2 are 1.0
nodes 6 go to nodes 0 with vehicle 0 are 0.125
nodes 6 go to nodes 3 with vehicle 1 are 0.23333333
nodes 6 go to nodes 3 with vehicle 2 are 0.76666667
cost optimal adalah 2.8
有什么线索可以解决这个问题吗?
解决方案
类class pulp.LpVariable
定义为:
pulp.LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)
with:
cat – The category this variable is in, Integer, Binary or Continuous(default)
进一步src/pulp/constants.py
定义:
LpCategories = {LpContinuous: "Continuous", LpInteger: "Integer",
LpBinary: "Binary"}
含义:
- 你要求
cat='Biner'
- 纸浆想要被要求
cat='Binary'
- 否则将生成一个连续变量,导致您观察到的结果
- 查看有关该选择的原始资料
- (我想我会在该例程中引入更“激进”的检查)
推荐阅读
- angular - 订阅内的功能 - Angular 4
- c# - 如何搜索导航属性的属性
- gcc - 未找到 GNU 汇编器,安装/更新气体预处理器
- javascript - 如何在 HTML 表格排序中保持序列号不变
- fiware - Orion 响应 RequestEntityTooLarge 的问题
- c - 使用 Park&Miller RNG 制作大样本?
- python-3.x - python将set.result块插入文本框
- iis-8 - IIS 8.5 和 Tomcat,重写条件不起作用
- sequelize.js - Sequelize:我怎样才能得到我用 Create 保存的实体
- file - 使用命令行移动特定名称的所有文件