игрушка коробка задача - Электронная коммерция Пересылка/Контейнер Расщепление

Question

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

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

Дано:

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

Проблема:

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

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

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

Заранее благодарен!

Answer 1

Это точно 3D bin-packing problem.

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

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

Эта проблема неудовлетворительно. NP-Hard, так что отличие от рюкзака - для него нет известного полиномиального оптимального решения.

В данной статье рассматривается проблема: The Three-Dimensional Bin Packing Problem (Martello et al)