python - 分组装箱

Question

我有一个产品 list (i)，每个产品都有给定的重量和体积。优化分为两步，其中我一直无法解决第二步。

第一个优化:最小化使用的 bin 数量(已解决)

• 尽量减少用于包装产品 list 的箱子数量。我有固定的垃圾箱，具有最大体积和重量限制。 Python代码:

  prob = pp.LpProblem("algorithm",pp.LpMinimize) #pp=pulp solver
  
  Y_max=10  #bins will not exceed this number
  #Y_min = minimum number of bins (calculated)
  # j = index of jth bin
  # i = index of ith product
  
  w=weights #list of weights w_i for product i
  v=volumes #list of volumes v_i for product i
  W=W_max #maximum weight of a bin
  V=V_max #maximum volume of a bin
  #len(order) = number of products
  
  x=pp.LpVariable.dicts("x_i,j", ((i, j) for i in range(len(order)) for j in range(Y_max)),0,1,pp.LpBinary) #variable indicating if product i is placed in bin j
  y=pp.LpVariable.dicts("y_j", ((j,0) for j in range(Y_max)),0,1,pp.LpBinary) #variable indicating if bin j is used or unused
  Y=pp.LpVariable('Y')
  
  prob +=Y , 'objective function'    
  prob += pp.lpSum([y[j,0] for j in range(Y_max)]) == Y, ""
  
  for i in range(len(order)):
      prob += pp.lpSum([x[i,j] for j in range(Y_max)]) == 1,''  #product i can only be placed in 1 bin
  
  for j in range(Y_max):
      prob += pp.lpSum([x[i,j]*w[i] for i in range(len(order))]) <= W*y[j,0],""  #weight constraint
  
  for j in range(Y_max):
      prob += pp.lpSum([x[i,j]*v[i] for i in range(len(order))]) <= V*y[j,0],""  #volume constraint
  
  for j in range(Y_max):
      for i in range(len(order)):
          prob += x[i,j] <= y[j,0],"" #products i may not be placed in bin j if bin j is unnused. 
  
  prob += pp.lpSum([y[j,0] for i in range(len(order))]) >=Y_min,""
  pp.LpSolverDefault.msg = 1
  prob.solve()`
  

第二次优化:最小化bin行进的区域数(线性优化如何解决？)

• 每种产品都来自两个区域中的一个(区域 1 或区域 2)。我们有这些区域 z_i 的列表(例如区域 1 <==> 1，区域 2 <==> 0)。

• 在 bin 数量不超过最小 bin 数量(在第一次优化中确定)的约束下，我能否将产品拆分到 bin 上，以使每个 bin 行进的区域数量最小化?

• 第一次优化的体积和重量限制仍然适用。

理想情况下，垃圾箱永远不会移动到两个区域，但在某些情况下它被迫这样做。 (例如，第一次优化导致 1 个容器包含区域 1 和区域 2 的产品)。

Answer 1

下面是一种实现方法 - 不一定是最简洁或最有效的。类似于@juvian 的建议

如果您慢慢减少每个箱子的体积，您会发现虽然它很大，但您可以放入少量箱子，每个箱子只访问一个区域。随着垃圾箱变小，您不得不让垃圾箱移动到多个区域，并且随着垃圾箱再次变小，您不得不使用更多垃圾箱。

目标函数中注意:prob += Y + pp.lpSum([two_zones[j] for j in range(Y_max)])/(Y_max+1)

我们将我们的次要目标(有来自两个区域的产品的箱子数量)除以最大箱子数量 + 1。这样我们总是优先考虑箱子数量的主要目标 - 即使每个箱子都有来自不同的区域，第二个总和最多可以是 Y_max，所以如果我们将它除以 Y_max + 1，我们得到的值小于 1.0，所以最好减少数量已用 bin 的数量减 1。当您想要确定目标的优先级时，这是一种常用技术。

import numpy as np 
import pulp as pp

prob = pp.LpProblem("algorithm",pp.LpMinimize) #pp=pulp solver

Y_max = 5 #bins will not exceed this number
#Y_min = minimum number of bins (calculated)
# j = index of jth bin
# i = index of ith product

# Some dummy data
n_prod = 10

np.random.seed(0)
w = np.random.uniform(2.5, 10, n_prod)  # product weights
v = np.random.uniform(0.1, 1, n_prod) # product volumes
W = 25 #maximum weight of a bin
V = 1.5  #maximum volume of a bin
z = np.random.randint(0, 2, n_prod) # product zones

x=pp.LpVariable.dicts("x_i,j", ((i, j) for i in range(n_prod) for j in range(Y_max)), cat='Binary') #variable indicating if product i is placed in bin j
y=pp.LpVariable.dicts("y_j", range(Y_max), cat='Binary') #variable indicating if bin j is used or unused
Y=pp.LpVariable('Y') # No. bins used
two_zones = pp.LpVariable.dicts("two_zones,j", range(Y_max), cat='Binary')
has_zone_0 = pp.LpVariable.dicts("has_zone_0,j", range(Y_max), cat='Binary')
has_zone_1 = pp.LpVariable.dicts("has_zone_1,j", range(Y_max), cat='Binary')

# Primary objective: minm No. bins, Secondary minimize bins that visit two zones
prob += Y + pp.lpSum([two_zones[j] for j in range(Y_max)])/(Y_max+1), 'objective function'    

prob += pp.lpSum([y[j] for j in range(Y_max)]) == Y, 'set Y to No. bins'

for i in range(n_prod):
    prob += pp.lpSum([x[i,j] for j in range(Y_max)]) == 1,'each product in 1 bin %s' % i

for j in range(Y_max):
    prob += pp.lpSum([x[i,j]*w[i] for i in range(n_prod)]) <= W*y[j], 'weight constraint %s' % j

    prob += pp.lpSum([x[i,j]*v[i] for i in range(n_prod)]) <= V*y[j], 'volume constraint %s' % j

    for i in range(n_prod):
        prob += x[i,j] <= y[j], 'products only placed in used bin  %s_%s' % (j, i)

        prob += has_zone_0[j] >= x[i,j]*(z[i] == 0), 'set has_zone_0 flag %s_%s' % (j, i)
        prob += has_zone_1[j] >= x[i,j]*(z[i] == 1), 'set has_zone_1 flag %s_%s' % (j, i)

    prob += two_zones[j] >= has_zone_0[j] + has_zone_1[j] - 1, 'set two_zones flag %s' % j

prob.solve()

has_zone_0_soln = np.array([has_zone_0[j].varValue for j in range(Y_max)])
has_zone_1_soln = np.array([has_zone_1[j].varValue for j in range(Y_max)])
two_zones_soln = np.array([two_zones[j].varValue for j in range(Y_max)])
y_soln = np.array([y[j].varValue for j in range(Y_max)])

# Print some output:
print("Status:" + str(pp.LpStatus[prob.status]))
print('z: ' + str(z))
print('Y: ' + str(Y.varValue))
print('y_soln: ' + str(y_soln))
print('Objective: ' + str(pp.value(prob.objective)))
print('has_zone_0_soln: ' + str(has_zone_0_soln))
print('has_zone_1_soln: ' + str(has_zone_1_soln))
print('two_zones_soln: ' + str(two_zones_soln))