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

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

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

Ответ 1

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

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

Удачи!

Ответ 2

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

Ответ 3

От wikipedia:

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

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

Ответ 4

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

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

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

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

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

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

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

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

Ответ 5

Вы задаете вопрос, похожий на: алгоритм упаковки 3d-бинов

Хотя, поскольку вы не разрешаете ротацию, вы можете получить довольно хорошие результаты. Я предлагаю больше взглянуть на решение FIRST-FIT-DECREASING.

Ответ 6

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

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