Вызов ящика для игрушек — отправка электронной коммерции / разделение контейнеров

Изменить: мне нужна эффективная реализация 3D-упаковки на Ruby, JavaScript, Java или Python с указанными ниже ограничениями

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

Дано:

  • Предметы имеют известную ширину, длину, глубину и вес
  • Предметы имеют тип упаковки, указывающий, что они могут быть объединены с другими предметами в одном контейнере («сверхупаковка») или должны быть отправлены в отдельном контейнере («отдельно на корабле»).
  • Контейнеры имеют известную ширину, длину, глубину и грузоподъемность.
  • Доступно несколько контейнеров разного размера и вместимости.

Проблема:

  • Существует список предметов, возможно, различных размеров и типов упаковки, а также, возможно, в нескольких количествах. Разделите список предметов так, чтобы их можно было хранить в минимально возможном количестве контейнеров.

Я полагаю, что это интересная объемная математическая задача, которая может понравиться некоторым из вас. Я ищу лучшее программное решение для этого.

Благодарен за решения на любом языке с предпочтением Java, JavaScript, Python или Ruby.

Заранее спасибо!


javascript e-commerce algorithm math bin-packing
person Alex Norcliffe    schedule 20.07.2016    source источник
comment
Это разновидность en.wikipedia.org/wiki/Knapsack_problem, но с дополнительными сложностями. учитывать тот факт, что для некоторых предметов требуется собственный контейнер (только корабль)   -  person Alex Norcliffe    schedule 20.07.2016

Ответы (1)


arrow_upward
1
arrow_downward

Это в точности проблема трехмерной упаковки в корзину.

Требование «корабль в одиночку» просто уменьшается, если выложить эти элементы и отправить их в одиночку, что оставляет вас с остальными.

Поиск минимального количества контейнеров, необходимых для их упаковки, теперь является задачей упаковки в контейнеры в трехмерном пространстве.

К сожалению, эта задача является сильно NP-трудной, поэтому, в отличие от рюкзака, для нее не существует известного псевдополиномиального оптимального решения.

В этой статье обсуждается проблема: трехмерная корзина Проблема упаковки (Мартелло и др.)

person amit    schedule 20.07.2016
comment
В конце концов я на самом деле решил это гораздо проще (и наивнее). Я использую справочную таблицу типов контейнеров с несколькими примерами комбинаций единиц упаковки, которые они могут содержать. Каждый продукт измеряется размером требуемой упаковочной единицы (а не точными размерами). Затем, начиная с самых больших упаковочных единиц в заказе, я выбираю типы контейнеров на основе примера вместимости в справочной таблице и уменьшаю количество оставшихся малых/средних/крупных единиц, которые необходимо упаковать. Писал несколько часов. Знаете ли вы, есть ли название для такого решения? (Кроме ленивых..) - person Alex Norcliffe; 22.07.2016
comment
Спасибо за ваше время, кстати! - person Alex Norcliffe; 22.07.2016