3-х мерные алгоритмы упаковки бина

Question

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

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

Answer 1

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

В целом, автономные формулировки MIP (или ветвление и ограничение) не работают хорошо для двумерной или трехмерной задачи, но программирование с ограничениями имело некоторый успех, приводя к точным решениям двумерной задачи. Проверьте это резюме. Не глядя на статью, мне нравится подход декомпозиции для задачи, в которой вы пытаетесь свести к минимуму количество корзин одинакового размера. Я не видел так много результатов для трехмерной задачи, но дайте нам знать, если вы найдете какие-либо выполнимые.

Удачи!

Answer 2

Я написал программу, которая тестирует три различных алгоритма. Также это хороший источник информации: тысяча способов упаковать мусорное ведро - практический подход к упаковке двухмерного прямоугольного мусорного ведра. Это для двумерного прямоугольного бункера, но вы всегда можете преобразовать его в 3D.

Answer 3

Из википедии:

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

Вот два источника, которые они дают для этого:

• Аппроксимационные алгоритмы
• Упаковка бункера может быть решена в течение 1 + ε за линейное время

Answer 4

Лучший точный решатель: используйте динамическое программирование.

Переменные состояния:

1. Предметы, которые вы упаковали и выбросили.
2. Пространство заполнено в контейнере.

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

Лучшие эвристические решатели

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

Готовые решения для проведения экспериментов

Извини, я даже понятия не имею.

Answer 5

https://3dbinpacking.com/ - это коммерческое решение (не алгоритм), позволяющее использовать API с приятной визуализацией. Это предлагает:

• Упаковка для одного контейнера
• Мульти бин упаковка
• Найти третье измерение
• Найти размеры бункера

Answer 6

Ваш вопрос похож на: 3d алгоритм упаковки бин

Хотя, поскольку вы запрещаете вращение, вы можете получить довольно хорошие результаты. Я предлагаю больше взглянуть на ПЕРВЫЕ УСТАНОВЛЕННЫЕ.