Добрый день

Может кто сталкивался или сам писал wms системы и в частности алгоритм оптимального заполнения объема ячейки. Поделитесь примером или где можно почитать/посмотреть.
Задача простая. Есть объем ячейки -ш/д/в. Есть несколько товаров каждый из которых имеет свой объем - ш/д/в. Как оптимально заполнить ячейку имеющимся товаром?

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

https://yandex.ru/search/?text=задача%20о%20рюкзаке&lr=213&clid=2186621

(1) Cкорее
https://www.google.com/search?q=оптимальное+заполнение+объема

спасибо, почитаю

Мой опыт показывает что практической пользы от реализации оптимального заполнения - практически никакой. В wms системах приходится обсчитывать много при ограниченных ресурсах. Поиск оптимальности сжимает.
Для практической работы вполне хватает
- расчёт вместимости по заданным количествами в типоразмер ячейки
- или считаем снежным комом с поправочным коэффициентом
- при размещении кладем в указанную ячейку, если не лезет то системой ставим временную блокировку на вход в ячейку и кладем в следующую подходящую.

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

Если надо действительно реализовать то имхо лучше стучаться в packer3d - с его помощью у меня оператор обсчитывал вместимость товара в моноячейки. В нем модно и мультиукладку считать

Есть классическая задача заполнения куба (неограниченного размера) шарами.
Известно 2 укладки с одинаковым коэфф. заполнения, но не доказано, что они оптимальны.
Это я к тому, что строгого результата ожидать не нужно. Попробуйте поискать что-то "практическое".

Задача у автора имеет имхо только академический интерес.
Следует например учитывать разрешенные ориентации, допустимые нагрузки
Опять же если с практической точки зрения то обычно в одной ячейке ДЛЯ ХРАНЕНИЯ больше 2-3 товаров делать очень проблематично. А в рабочих ячейках мульти размещение очень быстро скатывается к хаосу.

(7) Зависит от специфики, если товар мелкий, то можно и больше 2-3.
(0) Смотри задачу о рюкзаке. Теоритичней просто некуда)))

(8) Рюкзак одномерный и здесь не годится.

(9) https://ru.wikipedia.org/wiki/Задача_о_рюкзаке#Варианты_задачи_о_рюкзаке

см № 6

(0) тебе эту задачу решат два Дшамшута с опытом работы на складе, причем без регистрации и смс. В ПЭК-е, например, таких видел.

1. Если ты хочешь с точностью 100% найти оптимальный вариант, то это одна задача (чисто академическая)
2. Если достаточно точности 95% (т.е. в 95% случаев ячейка будет заполнена оптимально) тогда достаточно проверять ШхВхГ товара, чтобы помещался в ячейку и контролировать, чтобы объем товаров в ячейке не превышал объем ячейки.
  Если ячеек много, то разницу между 1 и 2 вариантом не заметишь

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

Товар поступает не одновременно, а по порядку. В момент поступления очередной партии-впихивай в минимально возможную.
©Ваш Джамшут

А можно вообще весь склад одной ячейкой считать и задача отпадает

(10) Вы ошибатесь: 3-х мерный рюкзак - не "упаковка" 3-х мерных объектов.

(16) э...что? Почему это?

(17) Многомерный ранец, это несколько ограничений, а не одно, как в одномерном.
Например (2 измерения), рюкзак ограничен по весу и по объему.
Нужно его наполнить, так чтобы "калорийность" была максимальной (каждый предмет имеет вес, объем и калорийность).
При упаковке 2-мерных предметов (прямоугольники с шириной и высотой) ограничения на суммарную ширину и суммарную высоту не адекватны задаче.

(18) Один фиг задача из (0) - это частный случай задачи о рюкзаке.
И как раз таки суммарная ширина и высота вполне себе адекватны задаче (просто у 2-х мерных предметов ширина и высота могут меняться местами, если это для них разрешено).

(19) Вы упорно ошибаетесь.

(19) трехмерная укладка имхо неэквивалентна задаче о рюкзаке. "Рюкзак" считает кучей. Трехмерная укладка - зависит от ориентации, порядка укладки. можно наверное и трехмерную укладку свести к задаче о рюкзаке - но внутри функции расчета в рюкзаке тогда д.б. расчет получившегося занятого объема (в т.ч. возможно с пустотами внутри) с учетом реальнйо трехмерной укладки...

(20) так?

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

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

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

(23) "в какую коробку все войдет" - ну это совсем уже вылом мозга/клиента.
прекрасно работает упаковка в коробку по факту. заполнилась - закрываем коробку. и пакуем новую. если совсем красиво - паковать можно одновременно в несколько незакрытых коробок.

(23) для загрузки машин - если паллетами - то длятиповых фур растановка типовых паллет давно просчитана и известна. Если набивка машины валом - то просчет через packer3d

(21) >>можно наверное и трехмерную укладку свести к задаче о рюкзаке - но внутри функции расчета в рюкзаке тогда д.б. расчет получившегося занятого объема (в т.ч. возможно с пустотами внутри) с учетом реальнйо трехмерной укладки...

Именно это и имел ввиду, когда говорил, что это частный случай задачи о рюкзаке. С доп. условиями, ограничениями, в т.ч. и учет пустот. Да, условия получаются более сложные, но на то этот случай и "частный"

(20) неплохо было бы свое мнение аргументировать, а не голословно утверждать, что оппонент ошибается)

(21) Не так: это совсем разные задачи.
(26) Давайте формально: Вы утверждаете, что укладка 3-мерных объектов - частный случай многомерного ранца.
Тогда это утверждение нужно доказать, т.е. показать (можно для 2 мерного случая), что любую задачу укладки прямоугольников можно записать как многомерный ранец (т.е. систему линейных неравенств с булевыми переменными (могут принимать значения 0 и 1)).
Для простоты можно считать, что прямоугольники не вращаются (т.е. ширина прямоугольника - по ширине ячейки).
Доказывать же противоположное утверждение (что нельзя свести) у меня нет никакого желания, т.к. для меня это совершенно очевидно, а Фалкерсоновскую премию все равно не дадут.

(27) Пожалуйста:
https://ru.wikipedia.org/wiki/Задача_об_упаковке_в_контейнеры

Вроде оно?

http://catalog.mista.ru/public/267268/

(28) Оно. Но к многомерному ранцу отношения (кроме одномерных контейнеров) не имеет.
Вы можете из статьи увидеть, что хоть какие-то результаты (ε -оптимальные полиномиальные алгоритмы и пр.) относятся только к одномерному случаю.

(29) Перебором можно, но долго (а значительно сократить его вряд ли удастся).
В свое время (лет 20 назад) пытался схемой неявного перебора (ветви и границы) делать раскрой (нестандартные элементы для кровли).
Не утверждаю, что сделал лучшим образом: выход получался примерно 75%.

(29) Я с автором стыковался ранее по этой разработке. Вариант опубликованный чисто какпоиграться, для промприменения непригоден. Он простейшие укладки из нескольких коробок не мог уложить. Если будете играться то проверять можно упомянутым выше пакором3д

(30) Так я и не утверждал, что задача имеет решение за полиномиальное время.
И чем же контейнеры принципиально отличаются от ранцев?

(33) Одномерные контейнеры - ничем. Изначально речь шла об упаковке 3-х мерных предметов.
Вы предложили в качестве модели использовать многомерный ранец, я утверждаю, что задачу (0) к многомерному ранцу свести не удастся.
Вы дали ссылку на статью в Википедия, я обратил Ваше внимание, что в этой статье есть результаты ТОЛЬКО об одномерных контейнерах.
Если Вы считаете, что (0) можно свести к многомерному ранцу - оставайтесь в этом приятном заблуждении.
На этом позвольте попрощаться.