我正在尝试解决10个客户和5个仓库的多个车辆段路由问题。添加子流约束时,求解器在合理的时间内不再找到最优解。当我在一段时间后停止求解器并检索最佳解决方案时,他返回一个不可行的解决方案(需要整数时的连续变量)。如何检索到目前为止找到的最佳可行解决方案,还是有其他方法可以解决我的问题?我知道堆栈上有一个类似的问题,但它解决了gurobi求解器的问题。
在这里你可以找到代码的一些部分以及他在10秒后给我的输出。
# Definition of the route variables:
route_vars = plp.LpVariable.dicts("Route",(Places,Places,Trucks),0,None,plp.LpInteger)
# constraint 7: No subtours
for i in Places:
for j in Places:
for k in Trucks:
if i != j:
prob += u[i]-u[j] + (15)*route_vars[i][j][k] <= 14
# Solve the problem
prob.solve(plp.PULP_CBC_CMD(maxSeconds=10))
print("status:", plp.LpStatus[prob.status])
print("optimal solution to the problem: ", plp.value(prob.objective))
# Print Results
for i in Places:
for k in Trucks:
for j in Places:
if plp.value(route_vars[i][j][k]) != 0:
print(plp.value(route_vars[i][j][k]), 'Truck ',k + 1, " from Place ",i+1, " to place ",j+1)
运行10秒后输出:
status: Not Solved
optimal solution to the problem: 348.1102769976801
0.066666667 Truck 7 from Place 1 to place 11
0.93333333 Truck 8 from Place 1 to place 11
0.066666667 Truck 4 from Place 2 to place 6
0.93333333 Truck 7 from Place 2 to place 6
0.066666667 Truck 2 from Place 3 to place 7
0.93333333 Truck 8 from Place 3 to place 7
0.93333333 Truck 1 from Place 4 to place 5
0.033333333 Truck 3 from Place 4 to place 5
0.033333333 Truck 3 from Place 4 to place 9
0.93333333 Truck 1 from Place 5 to place 9
0.033333333 Truck 3 from Place 5 to place 4
0.033333333 Truck 4 from Place 5 to place 9
0.066666667 Truck 4 from Place 6 to place 2
0.93333333 Truck 7 from Place 6 to place 2
0.066666667 Truck 2 from Place 7 to place 3
0.93333333 Truck 8 from Place 7 to place 3
0.066666667 Truck 2 from Place 8 to place 10
0.93333333 Truck 8 from Place 8 to place 10
0.93333333 Truck 1 from Place 9 to place 4
0.033333333 Truck 3 from Place 9 to place 4
0.033333333 Truck 4 from Place 9 to place 5
0.066666667 Truck 2 from Place 10 to place 8
0.93333333 Truck 8 from Place 10 to place 8
0.066666667 Truck 7 from Place 11 to place 1
0.93333333 Truck 8 from Place 11 to place 1
如你所见,它给了我一个不可行的解决方案。
错误地定义了没有小计的Miller-Tucker-Zemlin约束。相反,约束应该是这样的,其中N是客户的数量,D是库的数量。
# constraint 8: No subtours (Miller Tucker Zemlin)
for i in range(0,N):
for j in range(0,N):
for k in Trucks:
if j != i:
prob += u[i]-u[j] + (N+D+1)*route_vars[i][j][k] <= N+D