Как рассчитать оптимальную погрузку груза в автомобиль?

Question

[vista1x]

Что имеем:

• Грузовой автомобиль с кузовом определенных размеров (ШхДхВ)
  
• Груз (коробки), которые нужно погрузить в этот автомобиль. У коробок есть ширина, длина, высота. Все коробки прямоугольные
  

Что нужно получить

• Схему оптимального расположения коробок в кузове автомобиля (в 2д, с указанием номера каждой коробки)
  

Какие условия

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

Интересует именно алгоритм поиска оптимального расположения груза. Буду рад любым подсказкам, в какую сторону смотреть, куда копать. Спасибо!

Comments

[Wataru]

в 2д, с указанием номера каждой коробки)

Можно ли их крутить, класть на бок, например? Много ли у вас коробок?

[vista1x]

Wataru, да, можно крутить на 90 градусов, коробок может быть много.

[Wataru]

vista1x, Много - это Тысячи? Десятки? Дюжина? Миллиарды?

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

[vista1x]

Wataru, давайте ограничимся одной тысячей. По диагонали ничего класть нельзя. На бок класть можно.

[Василий Банников]

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

ЗЫ: В реальном мире не все коробки можно переворачивать. Некоторые вещи можно транспортировать только вертикально. А также не любые коробки можно штабелировать. Некоторые хрупкие товары (например телевизоры) не терпят, когда их много штук в стопку кладут - самый нижний будет раздавлен под весом верхних.

[Adamos]

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

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

[mayton2019]

А все понимают что такое "схема оптимального расположения в 2д" ?

Это вообще возможно изобразить?

[vista1x]

mayton2019, можно если рассматривать простейший вариант, где коробки не нужно класть друг на друга (вид сверху)

[mayton2019]

vista1x, это же фигня полная. Ты согласен? Мы не загрузим машину.

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

Вообще в науке и технкие эта задача решена. Она называется "оптимальный раскрой" материала. Ее обычно решают суб-оптимально. Тоесть дают алгоритму поработать пару минут и с читают что оптимум найден. И это хорошо. При произвольных размерах (не кратных ничему) - задачу можно считать транс-вычислительной и решать до скончания времен. Но мы не будем.

Поэтому ищи "раскрой" - и бери и используй.

Answer 1

[Wataru]

Это называется "задача упаковки" (packing problem). В простейшем случае - прямоугольников в прямоугольник. Нашласть статья на хабре и какая-то научная статья. Дальше вам придется гуглить самостоятельно.

Вообще, это NP-полная задача, поэтому для решения скорее всего придется использоваать метод ветвей и границ или какие-то переборы с отсечениями. Если коробки занимают почти все место в машине и решение есть, но оно редкое, то найти его за разумное время вы сможете, скорее всего, лишь для относительно небольшого количества коробок (штук 40-50).

А разрешение класть на бок вообще усложняет задачу кардинально. Это вам придется еще для каждой коробки перебирать, а каким боком ее класть на пол.

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

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