Умная группировка товара, количество товара

Question

У меня есть ситуация, когда я получаю заказы из нескольких продуктов различного количества, которые необходимо отправить на несколько грузовиков.Цель состоит в том, чтобы свести к минимуму количество товаров на одну партию, чтобы сделать сбор продукции более эффективным.

В идеале я не хочу, чтобы на один грузовик приходилось 6 разных предметов.То, что я могу довольно легко сделать, и мне не нужна помощь, это просто упорядочить предметы по количеству по убыванию и распределить их по группам по 24 (лимит грузовика).Я изо всех сил пытаюсь найти алгоритм, чтобы разумно разбить количество на «умные группы».Моя первая мысль - я действительно смотрю на разработку своего рода ИИ для этого и не совсем уверен, с чего начать.У кого-нибудь есть мысли или предложения о том, как этого добиться?

Answer 1

Один из способов получить минимальное количество различных предметов на грузовик - это свести к минимуму максимальное количество различных предметов.Я не думаю, что это соответствует стандартной проблеме ранцев или упаковки, но мы можем легко сформулировать это как смешанное целочисленное программирование задача.Чтобы разработать математическую модель, мы можем определить следующие переменные решения:

x(i,j) >= 0     : quantity of item i placed in truck j 

y(i,j) in {0,1} : 1 if any item i is placed in truck j
                  0 otherwise

x - неотрицательная переменная, а y - двоичная переменная.При этом мы можем сформулировать нашу модель как:

Результаты могут выглядеть следующим образом:

----     56 PARAMETER results  solution

                truck1      truck2      truck3      truck4

A                                                   20.000
B                                       20.000
C                           20.000
D               14.000
E                            4.000
F                4.000
G                6.000
H                                        1.000       2.000
I                                        3.000
J                                                    2.000
total           24.000      24.000      24.000      24.000
diff.items       3.000       2.000       3.000       3.000

Эту модель можно кормитьв любой решатель MIP.

На практике вы можете сделать задачу немного более сложной: сначала минимизируйте максимум, а затем минимизируйте сумму у.Это сделано для того, чтобы обеспечить правильное решение для грузовых автомобилей, которые не достигли максимального значения y.Во многих практических моделях нам необходимо добавить такие термины «регуляризации».Это остается линейной моделью MIP.