Как я могу программно определить, как поместить небольшие коробки в большую упаковку?

Question

Кто-нибудь знает о существующем программном обеспечении или алгоритмах для расчета размера пакета для доставки нескольких предметов?

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

Answer 1

Это проблема Bin Packing , и она NP-сложная. Для небольшого количества объектов и пакетов вы можете просто использовать метод грубой силы, пытаясь использовать любую возможность. Кроме того, вам нужно использовать эвристику какого-то рода. В статье Википедии есть некоторые подробности, а также ссылки на статьи, которые вы, вероятно, хотите проверить.

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

Answer 2

Литература по "3D Bin-упаковке" обширна и обширна. Вы можете получить хороший обзор, отслеживая публикации Профессор Дэвид Пизингер . Он также опубликовал одну из немногих высококачественных реализаций упаковки бина с исходным кодом: 3dbpp.c

Мой собственный инструментарий логистики pyShipping поставляется с реализацией 3D Bin Packing для складских приложений. Он в основном реализует 4D Bin Packing (трехмерный размер и вес) и получает приемлемое решение для типичных размеров заказов (несколько десятков пакетов) в течение второго времени выполнения. Он используется в производстве (имеется в виду склад) уже несколько месяцев, чтобы определить верхнюю границу ящиков для транспортировки, которые будут использоваться. Работники склада часто могут упаковывать вещи более эффективно, но у меня все нормально.

Answer 3

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

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

А вот реализация в php .

Answer 4

Вы пытаетесь увидеть, сколько одного типа вписывается в пакет определенного размера, или вы также пытаетесь смешивать типы?

Звучит так, будто вы пытаетесь решить проблему Рюкзак . Вы можете найти некоторые алгоритмы для этого, которые могут быть адаптированы к вашим конкретным требованиям. Просто поймите, что будет трудно найти эффективный алгоритм, так как проблема в NP завершена (хотя в зависимости от ваших конкретных требований вы сможете найти эффективное приближение, или ваши входные данные могут быть достаточно малы это не имеет значения).

Answer 5

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

Это может привести к тому, что ваши люди-упаковщики придут в SO и спросят, как программно тренироваться, как упаковать n предметов в m коробок. :-P (Они могут также попросить вас сделать это, попросить у вас инструкции и т. Д.).

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

Answer 6

Метаэвристика хороша для решения реальных проблем упаковки бинов, когда имеется много пакетов и / или много ограничений. Одной из открытых реализаций Java является Drools Planner .

Answer 7

Возможно, это покажется очевидным, но, возможно, стоит запомнить проблему, а затем сделать некоторые из них вручную. Найти наиболее эффективное решение для произвольных входов и блоков в NP-hard, но, ограничивая пространство проблем и принимая некоторую неэффективность, этот размер NP может быть чем-то разумным, и, запомнив, вы сможете привести «общий случай» "время существенно.

Это также может помочь думать о вещах с точки зрения иерархической упаковки.

Answer 8

После долгих поисков я нашел GitHub репозиторий, который может кому-то помочь. Функция PackingService.Pack() принимает список Container и список Item (s) для упаковки в качестве параметра и возвращает результат, который содержит много информации, включая

«контейнер (ы), упакованные в процентах и ​​список упакованных и неупакованных предметов»