Есть ли алгоритм определения оптимального размера посылки?

Question

[Антон Шаманов]

У товаров заданы ширина\длина\высота, как вычислить оптимальный (т.е. наиболее компактный) размер посылки?

Comments

[GavriKos]

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

[Антон Шаманов]

GavriKos: да, минимальный объем

[Антон Шаманов]

GavriKos: "минимальным объемом - решается простым перебором" а пример не приведете? "Но я так понимаю есть какие то ограничения на то, куда эта посылка должна потом попасть." - чем меньше габариты тем ниже стоимость доставки

[GavriKos]

Антон Шаманов Эээ, если у вас задана высота, длина и ширина - то минимальный объем равен произведению этих величин. Или у вас посылки стандартизированы и кастомить их нельзя?

[Антон Шаманов]

GavriKos: " задана высота, длина и ширина" - для каждого товара, но нам надо вычислить не объем, а габариты посылки т.е. ширину\длину\высоту

[GavriKos]

Антон Шаманов габариты посылки равны габариту товара, плюс поправка на толщину картона. Почему габариты посылки должны быть другими? Ну вот хоть убейте не пойму ) Единственный вариант - это если у вас посылки четко стандартизированы, и надо выбрать оптимальную из существующих - в вопросе этого нет.

[Антон Шаманов]

GavriKos: в посылке несколько товаров, от расположения товаров зависит итоговый объем посылки - он не всегда равен объему товаров. пример: товар1 ш-3 д-1 в-1, товар2 ш-3 д-1 в-1, товар3 ш-1 д-1 в-2.

[Антон Шаманов]

GavriKos: попробуй сложить эти товары один на другой, а потом потом вариант 2 на 1 и сбоку 3 - объем посылки будет отличатся, во втором случае пустот не будет

[GavriKos]

Антон Шаманов воо, теперь понятно - в 1 посылке > 1 товара. Задача об укладке рюкзака, с модификациями. Ну это так, на вскидку, мне больше пояснение интересовало.

[Антон Шаманов]

GavriKos: само собой больше, написано же у товарОВ, иначе бы и вопросов не было.

[Антон Шаманов]

GavriKos: рюкзак тут не подходит - т.к. его размер заранее не известен.

Answer 1

[Philipp]

Почитайте тут engsi.ru/doc/781936.html
Эта задача из разряда труднорешаемых, поэтому в большинстве случаев идеальных решений нет.

Т.к. вам нужно решать задачу для интернет-магазина, то в большинстве случаев достаточно грубой оценки.
Обычно люди покупают относительно немного вещей (до 10), поэтому можно поступить методом тетриса в один слой.
Отсортируете посылки по длине. Получите сумму длин. Возьмите 1/3 от суммарной длины, начните выкладывать посылки по длине. Если одна вышла за 1/3 длины, увеличьте длину до последней посылки.
Все, вы получили дно тетриса. Дальше просто кладите слоями по максимальной ширине.
В итоге у вас получится большая плоская коробка с максимальной высотой товара.
Это простое неоптимально решение, но оно будет работать быстро, что важно для интернет-магазина.
Переплату за доставку можно возращать ввиде кредита покупателю на следующую покупку.

Comments

[Tereverda]

ссылка уже не рабочая, интересно почитать, как называлась работа?

[Philipp]

Tereverda, https://web.archive.org/web/20181219045723/http://...

На случай протухания веб-архива:

Задача о трехмерной упаковке и методы ее решения. Обзор

Инженерный вестник # 06, июнь 2015
УДК: 658.7

Answer 2

[sim3x]

Задача_о_ранце

Comments

[Антон Шаманов]

не то

[sim3x]

Антон Шаманов:
то
В реальных условиях, ты ограничен стандартными коробками и размерами машин для перевозки
Так что задача вырождается в задачу о рюкзаке для 3-10 типов коробок

[Антон Шаманов]

sim3x: коробка может быть любая и посылка всегда заведомо меньше кузова.

Answer 3

[xmoonlight]

Попарно убираем товары с одной площадью в основании (так, чтобы одна из сторон была равна или меньше, но минимум разницы) и дающие в сумме нужную высоту блока размещения. Начинаем без пары с самого габаритного.
Как будет готово - размещаем площади оснований на заданной плоскости тем же методом.
Блоки размещения - можно также комбинировать той же схемой алгоритма, начиная с самого габаритного.
Товары и блоки размещения - можно крутить во все стороны.
UPD:
Изначально - нужно определиться с размерами одной из сторон посылки: пропорции размеров или чётко заданные размеры, чтобы можно было определить оптимальный размер начального блока размещения.
Или должны быть заранее известны условия компактности:
1. минимально занимаемый объём пространства без ограничений на любой из размеров
2. минимальное удаление углов параллелепипеда от центра фигуры, т.е. идеальный вариант - куб.

Comments

[Антон Шаманов]

Мне это ни о чем не говорит.

[xmoonlight]

Антон Шаманов: по 3% от каждой длины прибавляете и получаете результат.

[Антон Шаманов]

xmoonlight: у них и высота есть, приведите пример.

[Алексей]

xmoonlight: Наверное тут ключевое слово "товаров", то есть много мелких товаров и размещение их в большой коробке. Что-то типа олимпиадной задачи.

[xmoonlight]

Антон Шаманов: 30x60x90 => 31x62x93

[xmoonlight]

Алексей: а-а...... 3D-рюкзак! Я понял..)))

[Антон Шаманов]

xmoonlight: нет, с рюкзаком все понятно давно - там фиксированный размер рюкзака, а тут размер посылки не задан

[Антон Шаманов]

Алексей: что-то вроде того: определяем размер коробки в которую должны поместится все товары. причем не забываем про компактность.

[Алексей]

Антон Шаманов: Я не спец по этому классу задач, но мне интересно - какой критерий компактности? Минимальный объем, минимальная сумма Д+Ш+В, или иное?

[Антон Шаманов]

Алексей: да, минимальный объем.

[xmoonlight]

Антон Шаманов: я описал алгоритм в ответе.

[Антон Шаманов]

xmoonlight: а можете пример привести? сложно понять

[xmoonlight]

Антон Шаманов: слишком затратно всё описывать.

[Антон Шаманов]

xmoonlight: мне кажется Ваш метод не оптимален т.к. не учитывает что товары можно и нужно вращать, пример: товар1 ш-3 д-1 в-1, товар2 ш-3 д-1 в-1, товар3 ш-1 д-1 в-2.

[xmoonlight]

Антон Шаманов: это Вы сами уже придумали - ДОМЫСЛИЛИ, что товары в моём методе нельзя вращать.

[Антон Шаманов]

xmoonlight: а где это учитывается? в описании этого нет.

[xmoonlight]

Антон Шаманов: а-а. я понял. ок. Чего там ещё нет?

Answer 4

[Mercury13]

Упаковка параллелепипедов. NP-полная задача, точное решение — перебор. Сам решал упаковку прямоугольников (т.е. в 2D) генетическим алгоритмом с переменным успехом.
Скорее всего, у вашей службы доставки есть ящики стандартного размера — потому стоило бы приспосабливаться к этим ящикам.

Comments

[Антон Шаманов]

До этого еще дойти надо - яндекс.доставка требует габариты посылки чтобы рассчитать стоимость доставки.

Answer 5

[polifill]

НИКАК.
Если бы упаковка была универсального размера, учитывающего все впадины и выпуклости.....

А по факту упаковка - стандартна (ну или выбор из нескольких)
Максимум что можно - попытаться подогнать под ближайшую бОльшую коробку.

Answer 6

[Tereverda]

Вот калькулятор