Бин упаковочный с группировкой

Question

У меня есть список продуктов (i), каждый с заданным весом и объемом.Оптимизация проходит в два этапа, из которых мне не удалось решить второй этап.

Первая оптимизация: минимизировать количество используемых бункеров (решено)

• Минимизировать количество бинов, использованных для упаковки списка продуктов.Я установил контейнеры с максимальными ограничениями по объему и весу.Код 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()`
  

Вторая оптимизация: свести к минимуму количество зон, в которые перемещается корзина (как решить с помощью линейной оптимизации?)

• Каждый продукт поступает из 1 из двух зон (зона 1 или зона 2).У нас есть список этих зон z_i (например, Зона 1 <==> 1, Зона 2 <==> 0).

• При условии, что количество бинов не превышаетминимальное количество бункеров (определяется при первой оптимизации), можно ли разделить продукты по бинам так, чтобы количество зон, в которые перемещается каждый бин, было минимальным?

• Ограничения по объему и весупервой оптимизации все еще применяются.

В идеале корзина никогда не будет перемещаться в две зоны, но в некоторых случаях она вынуждена это делать.(Например, первая оптимизация приводит к 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, поэтому предпочли бы уменьшить количество используемых корзин на 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))