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

Question

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

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

Answer 1

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

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

Удачи!

Answer 2

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

Answer 3

Из Википедия :

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

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

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

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

Answer 6

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

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