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

Ниже приведен один из способов сделать это — не обязательно самый аккуратный или самый эффективный. Подобно тому, что предложил @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))