3d алгоритм упаковки для доставки товара

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

1. Существует конечный набор известных размеров прямоугольных коробок.

2. Внутри коробок должно быть много произвольных прямоугольных предметов

3. Меньше коробок следует использовать лучше всего. Потому что доставка двух коробок 1x1x1 намного дороже, чем одна коробка 1x2x1. Это должно быть приоритетом здесь.

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

5. Элементы можно поворачивать, чтобы они соответствовали размеру коробки, но поворот должен быть ограничен с шагом не менее 45 ° (в моих исследованиях кажется, что в некоторых конфигурациях допускается поворот на 45 градусов для лучшего размещения прямоугольных прямоугольников внутри большего прямоугольного прямоугольника) при поворотах на 90 ° принятый стандарт

6. Коробки имеют ограничение по весу, а предметы имеют произвольный вес (например: предмет размером 1x1x1 может быть более тяжелым, чем другой предмет 2x2x2)

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

1. Сортировка предметов в порядке убывания объема (сначала больше) в списке «товары для упаковки»

2. Для каждого элемента в этом списке:

   1. Выберите меньший ящик, который находится в списке «использованных ящиков» и имеет достаточный предел объема и веса, чтобы соответствовать предмету (я буду использовать здесь, чтобы означать подгонку размеров и веса)

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

   3. Если блок соответствует элементу (с помощью функции подгонки ниже), добавьте его в список «элементов этого блока» и удалите его из списка «элементов для подгонки», отметив его относительное 3d-положение внутри блока.

   4. Повторяйте от 2.1 до тех пор, пока в списке «товары для упаковки» не будет предмета для размещения

Функция проверки соответствия, использованная на шаге 2 выше:

1. Проверьте, соответствует ли оставшийся объем коробки объему предмета. Если нет, верните false.

2. Проверьте, является ли сумма веса «предметов в ящике» плюс вес текущего предмета меньше или равна пределу веса ящика. Если нет, верните false.

3. Проверьте список «элементов блока», чтобы выбрать первую координату блока, которая имеет наименьший компонент Y и в которой достаточно места для ширины, глубины и высоты элемента, учитывая, что другие элементы размещены как недоступное пространство.

4. Если элемент не соответствует текущей ориентации, поверните его на одно из 6 возможных поворотов, не предполагая поворота на 45 ° для простоты. (Вращения, приводящие к размерам, которые уже были проверены, могут быть пропущены. Например: поворот рамки на 180 ° дает те же размеры, что и исходное положение, поскольку все коробки и элементы имеют одинаковый размер для противоположных граней и поэтому могут быть пропущены.)

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

6. Если все повороты были выполнены, и подгонка не найдена, считайте текущую координату недоступным пространством.

7. Если для проверки нет свободного места, верните false. В противном случае попробуйте еще раз с шага 3.

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

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

Ссылки были бы отличными.

Редактировать:

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

Вот некоторые примеры:

• http://v2.3dbinpacking.com/demo/main
• http://www.packit4me.com/api

Изменить 2:

Реальный пример проблемы, которую нужно решить:

• У меня есть 4 размера коробки WxHxD: 10x12x18, 12x16x24, 16x20x30, 24x32x40
• У меня порядка 4 предметов: 1 размером 6x8x10, 2x 22x14x30 и 1x 22x4x20

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

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

Теперь вам просто нужно собрать все коробки на грузовике без потерь. Мой друг делает свою вторую невозможную вещь и дает вам решение. К сожалению, с размерами ящиков, которые вы выбрали выше, в грузовике есть свободное пространство, которое можно уменьшить, если вы выбрали разные (большие или меньшие) коробки в первой задаче. Если вы измените размер одной коробки, в лучшем случае вам придется заново упаковать грузовик; в худшем случае вам, возможно, придется упаковать все коробки, что так же сложно, как проблема, с которой мы начали. И, как и на первом этапе, вам придется попробовать все возможные 3D-аранжировки.

Я обнаружил, что « Руководство по разработке алгоритмов», разработанное Скиеной, полезно для размышлений о том, какой класс алгоритмов подходит для каких-либо проблем, но в основном я узнал, что хорошие решения даже для обыденных проблем взрываются перед вами с вычислительными трудностями. Большая часть того, что вам нужно, вписывается в класс проблем упаковки мусора, и эта статья является хорошей отправной точкой. Стоит отметить, что некоторые из лучших алгоритмов для этого - коммерческие продукты, потому что эта задача встречается повсюду в логистике (в какое наименьшее количество железнодорожных вагонов я могу доставить свои товары? И тому подобное). Можно заработать немалые деньги, если правильная эвристика может сэкономить производителю 100 вагонов в месяц.

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

Спасибо @JTrana за прекрасное расширение моего комментария.

При создании новых алгоритмов, а я недавно только что сам сделал алгоритм упаковки (я знаю, что он все еще имеет некоторый потенциал оптимизации), я всегда делаю самый простой подход:

Как бы я, как человек, сделал это и попытался бы перевести это в алгоритм: от моего (робототехнического) учителя ИИ Рольфа Пфайфера я до сих пор имею в виду, что кажущийся интеллект иногда может создаваться по очень простым правилам, поэтому вместо чрезмерного повышения квалификации Я стараюсь не тренироваться

1. Определите слишком большие предметы (предметы, которые не помещаются в какую-либо данную коробку)
2. Попробуйте найти наилучшую возможную коробку (сравнив общий объем и размеры предмета)
3. Заказывайте предметы от больших до маленьких и коробки (пробелы) от маленьких до больших
4. Поместите самый большой предмет в наименьшее возможное пространство
5. Если самый большой предмет не найден, перепрыгните через него и попробуйте следующий, пока ничего не подойдет

6. Для остальных предметов, найдите новый лучший ящик. ...

   X. всегда думайте об исключительных событиях (негабаритные элементы, странные формы, если в коробке содержится только 1 элемент, не лучше ли отправить элемент без коробки? И т. Д.), Но вы можете сделать эвристику также в форме решения дерево.

Конечно, чем дальше, тем больше предостережений, я просто приведу эти идеи в качестве отправной точки. Оттуда есть много возможных способов. Одна из альтернатив - разделить коробку на маленькие кубики (например, 5 см х 5 см х 5 см) и отследить их как занятые / свободные, другой подход можно назвать 3d тетрис и т. Д.

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

По крайней мере, именно так я, как человек, справлялся с задачей, получал лучшее поле и затем помещал самый большой элемент один за другим в наименьшее доступное пространство (и добавлял немного предварительного просмотра).

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

Иногда легче начать с первого шага и устранить проблемы на своем пути, в отличном от курса, в идеале это не какой-то шаг за крайний шаг, но немного умнее ... иногда вы можете быть вынуждены изучить альтернативы и выбрать лучший или реализовать «шаг назад».

Но, как я узнал от своего учителя по искусственному интеллекту (Рольф Пфайфер, извините, что беспокоюсь об этом снова): иногда вы можете создать очевидное интеллектуальное поведение с некоторыми очень простыми и немногочисленными наборами правил> возникающее поведение в упомянутом примере, они запрограммировали маленькие удаленные машины поворачивать налево, если они обнаруживают препятствие на правой стороне, поворачивают направо, если есть препятствие на левой стороне, и идут прямо, если нет препятствия или если препятствие находится впереди. 3 или 4 робота, помещенные в квадрат 3 х 3 м с множеством шаров для пинг-понга, приводят к удивительному факту, что роботы, кажется, убираются, толкая шары для пинг-понга по углам, даже если роботы только запрограммировано, чтобы избежать препятствий.

П.Д .: Единственное реальное отклонение, которое я обнаружил в этом подходе, это то, что я работал неполный рабочий день в качестве рабочей сцены для больших концертов, таких как «Металлика», «Железная дева», «Бритни Спирс», Пол МакКартни, назовите это… Водители, работающие над международные туры имеют точные упаковочные листы по пунктам. Расчеты выполняются один раз (я не знаю людей или машин), а затем копируются. Иногда, когда они упаковывают вещи в первый раз, они даже делают послойные фотографии и вставляют их в грузовик, чтобы местные команды точно знали, какую коробку нужно заряжать, когда и где. Но это также особая потребность в упаковке, так как в одном туре они всегда работают с одинаковыми коробками и грузовиками.

Эвристика, которую вы упоминаете в своем посте, кажется интересной.

Я бы предложил пару модификаций, чтобы улучшить окончательное решение.

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

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

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