Кто-нибудь знает о существующем программном обеспечении или алгоритмах для расчета размера пакета для доставки нескольких элементов?
У меня есть куча предметов в нашей базе данных инвентаря с определенными размерами длины, ширины и высоты. Учитывая эти размеры, мне нужно рассчитать, сколько из купленных предметов будет вписываться в предопределенные размеры ящиков.
Это проблема Bin Packing, и она NP-hard. Для небольшого количества объектов и пакетов вы можете просто использовать метод грубой силы, чтобы попробовать все возможности. Кроме того, вам нужно будет использовать эвристику. В статье в Википедии есть некоторые подробности, а также ссылки на документы, которые вы, вероятно, захотите проверить.
Альтернативой, конечно же, является запуск с действительно простым алгоритмом (например, просто "укладка" элементов) и вычисление разумной верхней границы при доставке с использованием этого, то, если ваши человеческие упаковщики могут сделать лучше, вы делаете небольшая прибыль. Или немного снижайте ваши расчетные цены в предположении, что ваша упаковка не идеальна.
Литература по упаковке "3D Bin" широко распространена. Вы можете получить хороший обзор, отслеживая публикации профессор Дэвид Писингер. Он также опубликовал одну из немногих высококачественных реализаций упаковки bin с исходным кодом: 3dbpp.c
Мой собственный инструментарий по материально-техническому обеспечению pyShipping поставляется с реализацией 3D-упаковки для приложений Warehousing. Он в основном реализует 4D Bin Packing (3D-размер и вес) и получает приемлемое решение для типичных размеров заказа (несколько десятков пакетов) в течение второй версии. Он используется в производстве (что означает склад) в течение нескольких месяцев, чтобы определить верхнюю границу используемых ящиков для транспортировки. Работники склада часто могут упаковывать несколько более эффективно, но все в порядке со мной.
Pisinger является одним из немногих ученых, которые публикуют рабочий код. В одной из своих работ он упоминает проблему "Минимальная глубина".
Вот практический и эффективный алгоритм php.
Вы пытаетесь увидеть, сколько из одного типа вписывается в пакет определенного размера или вы пытаетесь также смешивать типы?
Если ящики должны быть упакованы вручную, вы можете подумать о написании алгоритма, который сделает то, что сделает разумный человек. Причина, по которой я предлагаю это, заключается в том, что, если вы не хотите распечатывать инструкции по упаковке для каждого заказа, тогда кто бы ни делал вашу упаковку, должен будет тренироваться, как они собираются соответствовать упорядоченным элементам, однако, сколько ящиков было выделено для порядок.
Это может привести к тому, что ваши человеческие упаковщики придут к SO, спрашивая, как программно тренировать, как упаковать n предметов в m-боксы.: -P (они также могут попросить вас сделать это, попросить инструкции и т.д.).
Пока ваш алгоритм делает то, что сделал бы разумный человек, я лично принял бы его оценку доставки.
Возможно, эта вещь, которую я взломала в последние часы, может помочь: http://github.com/yetzt/boxing
Метаэвристика хороша для решения проблем с упаковкой реальных контейнеров, когда есть много пакетов и/или многих ограничений. Одна реализация Java с открытым исходным кодом - Drools Planner.
Возможно, это будет казаться очевидным, но, возможно, стоит вспомнить проблему, а затем сделать некоторые из них вручную. Нахождение наиболее эффективного решения для произвольных входных данных и ящиков в NP-hard, но, ограничивая пространство проблем и принимая некоторую неэффективность, размер NP может быть чем-то разумным, и посредством memoizing вы могли бы привести "обычный случай" "существенно сократилось время.
Это может также помочь подумать о вещах с точки зрения иерархической упаковки.
После многократного поиска я нашел GitHub репозиторий, который может помочь кому-то. Функция PackingService.Pack() принимает список Container и список Item (s), который должен быть упакован как параметр и результат возврата, который содержит много информации, включая
", упакованные в процентах и список упакованных и распакованных товаров
Любой, кто все еще ищет это - https://www.3dbinpacking.com - у него есть 1 месяц бесплатно и это просто потрясающе.