Как разработать или внедрить алгоритм оптимального заполнения объема ячейки (3D Bin Packing) в WMS-системах на 1С?

← На главную

Разработка и внедрение складских систем управления (WMS) неизбежно сталкивает разработчика с задачей автоматического размещения товаров по ячейкам хранения. На первый взгляд задача кажется тривиальной: сопоставить свободный объем ячейки с объемом поступающих товаров. Однако при попытке реализовать это на практике мы сталкиваемся со сложнейшей математической проблемой трехмерной упаковки (3D Bin Packing Problem). В этой статье мы подробно разберем теоретическую подоплеку этой задачи, разрешим популярные заблуждения, рассмотрим практические эвристические методы и напишем пример алгоритма на языке 1С.

Теоретический спор: почему «Рюкзак» — это не «3D-упаковка»

В кругах разработчиков часто возникает путаница между классической задачей о рюкзаке (Knapsack Problem) и задачей геометрической упаковки в контейнеры (Bin Packing Problem). Давайте разберем, в чем заключается принципиальная разница между ними, и почему математический аппарат классического рюкзака здесь не работает.

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

При решении задачи 3D-упаковки (3D-BPP) ключевым является геометрическое (ортогональное) ограничение. Объекты представляют собой жесткие параллелепипеды с фиксированными размерами по ширине, длине и высоте. Они не должны пересекаться в трехмерном пространстве, а их ребра должны быть параллельны осям контейнера (ячейки). Свести геометрическую укладку к задаче рюкзака без ввода сотен тысяч булевых переменных, описывающих каждую координату каждого угла коробки, невозможно. Задача 3D-BPP относится к классу NP-трудных задач, и ее точное решение методом полного перебора для большого количества коробок требует колоссальных вычислительных мощностей, что неприемлемо в реальном времени работы WMS-системы.

Практический подход: эвристические алгоритмы укладки

Поскольку точный расчет геометрии «на лету» может заставить сервер 1С зависнуть при обработке крупной поставки, на практике используют эвристические (приближенные) алгоритмы. Они позволяют получить точность укладки в районе 90–95%, выполняя расчет за доли секунды. Рассмотрим наиболее популярные из них:

Алгоритм «Первый подходящий» с сортировкой (First Fit Decreasing - FFD): все товары предварительно сортируются по убыванию их объема (или максимального габарита). Затем система последовательно пытается разместить каждый товар в первую ячейку, куда он проходит по физическим габаритам и доступному объему.
Метод крайних точек (Extreme Points): при размещении первой коробки в углу ячейки (координаты 0,0,0) генерируются новые потенциальные точки для укладки последующих коробок (вдоль осей X, Y, Z). Алгоритм динамически оценивает эти точки и укладывает следующую коробку туда, где минимизируется появление неиспользуемых пустот.
Уровневая (слоистая) эвристика: трехмерное пространство ячейки разбивается по высоте на виртуальные слои. Внутри каждого слоя задача сводится к двухмерной укладке (2D Bin Packing) прямоугольников на плоскости. Это значительно упрощает расчеты и гарантирует ровные ярусы, что облегчает работу кладовщикам.

Реальные физические ограничения WMS-систем

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

Допустимые ориентации (кантование): далеко не каждый товар можно вращать по всем трем осям. На коробках часто присутствуют знаки «Верх», указывающие на то, что товар (например, бытовую технику или жидкости) нельзя класть на бок или переворачивать.

Грузоподъемность и прочность (штабелирование): тяжелые грузы должны располагаться строго на полу ячейки, а легкие и хрупкие — сверху. В WMS-системе для каждого товара должен быть задан параметр максимальной нагрузки сверху (параметр штабелирования).

Статическая устойчивость: коробки не могут висеть в воздухе или опираться на нижележащие коробки лишь малым краем. Алгоритм должен отслеживать, чтобы площадь опоры коробки составляла не менее 60–80% от ее основания.

Очередь доступности (LIFO/FIFO): если в ячейку помещается несколько разных SKU, мы должны учитывать удобство их извлечения. Товар, который потребуется отгрузить в первую очередь, не должен быть заблокирован в глубине или в самом низу ячейки тяжелыми коробками других артикулов.

Реализация упрощенного алгоритма контроля вместимости на 1С

Рассмотрим практическую реализацию эвристического алгоритма на языке 1С. Этот алгоритм решает задачу с точностью до 95%. Мы выполним проверку возможности размещения по следующим правилам:

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

Ниже представлен пример функции на языке 1С, выполняющей базовую проверку возможности размещения списка товаров в ячейку с учетом габаритов и поправочного коэффициента полезного объема ячейки.


Функция ПроверитьВместимостьТоваровВЯчейку(СтруктураЯчейки, ТаблицаТоваров, КоэффициентЗаполнения = 0.8) Экспорт

    // СтруктураЯчейки содержит свойства: Ширина, Высота, Глубина, Объем
    // ТаблицаТоваров содержит колонки: Ширина, Высота, Глубина, Объем, Количество
    
    ОбъемЯчейки = СтруктураЯчейки.Ширина * СтруктураЯчейки.Высота * СтруктураЯчейки.Глубина;
    ЭффективныйОбъемЯчейки = ОбъемЯчейки * КоэффициентЗаполнения;
    
    // Шаг 1. Быстрая проверка по суммарному объему
    СуммарныйОбъемТоваров = 0;
    Для Каждого СтрокаТовара Из ТаблицаТоваров Цикл
        СуммарныйОбъемТоваров = СуммарныйОбъемТоваров + (СтрокаТовара.Объем * СтрокаТовара.Количество);
    КонецЦикла;
    
    Если СуммарныйОбъемТоваров > ЭффективныйОбъемЯчейки Тогда
        Возврат Ложь; // Однозначно не поместится по объему
    КонецЕсли;
    
    // Шаг 2. Геометрическая проверка возможности размещения самого крупного неделимого объекта
    // Проверим, помещается ли хотя бы один экземпляр каждого товара в габариты ячейки с учетом вращения
    Для Каждого СтрокаТовара Из ТаблицаТоваров Цикл
        Если СтрокаТовара.Количество > 0 Тогда
            Если Не ТоварПомещаетсяВГабариты(СтрокаТовара, СтруктураЯчейки) Тогда
                Возврат Ложь; // Товар физически шире/выше/длиннее ячейки
            КонецЕсли;
        КонецЕсли;
    КонецЦикла;
    
    // Шаг 3. Упрощенная эвристическая "жадная" укладка по уровням
    // Сортируем таблицу товаров по убыванию объема для первоочередной укладки крупных объектов
    ТаблицаТоваров.Сортировать("Объем Убыв");
    
    ОставшаясяШирина  = СтруктураЯчейки.Ширина;
    ОставшаясяВысота  = СтруктураЯчейки.Высота;
    ОставшаясяГлубина = СтруктураЯчейки.Глубина;
    
    // Простейшая проверка линейного заполнения по одной из ключевых осей
    Для Каждого СтрокаТовара Из ТаблицаТоваров Цикл
        Для Счетчик = 1 По СтрокаТовара.Количество Цикл
            // Пытаемся "откусить" пространство ячейки по наиболее оптимальному измерению
            Если СтрокаТовара.Глубина <= ОставшаясяГлубина Тогда
                ОставшаясяГлубина = ОставшаясяГлубина - СтрокаТовара.Глубина;
            ИначеЕсли СтрокаТовара.Ширина <= ОставшаясяШирина Тогда
                ОставшаясяШирина = ОставшаясяШирина - СтрокаТовара.Ширина;
            ИначеЕсли СтрокаТовара.Высота <= ОставшаясяВысота Тогда
                ОставшаясяВысота = ОставшаясяВысота - СтрокаТовара.Высота;
            Иначе
                // Если не удалось разместить даже линейно - возвращаем Ложь
                Возврат Ложь;
            EndIf;
        КонецЦикла;
    КонецЦикла;
    
    Возврат Истина;

КонецФункции

Функция ТоварПомещаетсяВГабариты(Товар, Ячейка)
    
    // Массив измерений товара
    ИзмТовара = Новый Массив;
    ИзмТовара.Добавить(Товар.Ширина);
    ИзмТовара.Добавить(Товар.Высота);
    ИзмТовара.Добавить(Товар.Глубина);
    
    // Массив измерений ячейки
    ИзмЯчейки = Новый Массив;
    ИзмЯчейки.Добавить(Ячейка.Ширина);
    ИзмЯчейки.Добавить(Ячейка.Высота);
    ИзмЯчейки.Добавить(Ячейка.Глубина);
    
    // Сортируем оба массива, чтобы сопоставить минимальные и максимальные стороны
    // Это автоматически учитывает возможность вращения товара на 3D-плоскости
    ИзмТовара.Сортировать();
    ИзмЯчейки.Сортировать();
    
    Если ИзмТовара[0] > ИзмЯчейки[0] 
       Или ИзмТовара[1] > ИзмЯчейки[1] 
       Или ИзмТовара[2] > ИзмЯчейки[2] Тогда
        Возврат Ложь;
    КонецЕсли;
    
    Возврат Истина;
    
КонецФункции

Интеграция со специализированным ПО (Packer3d)

Если перед вашей WMS-системой стоит задача не просто оценить, влезет ли товар, а построить точную трехмерную карту укладки паллеты или кузова автомобиля с визуализацией для кладовщика, писать собственный геометрический движок на 1С не имеет практического смысла. Платформа 1С плохо подходит для сложных трехмерных расчетов в реальном времени.

Для этих целей рекомендуется использовать специализированные внешние библиотеки и сервисы, такие как Packer3d. Интеграция с ними реализуется по следующей схеме:

WMS-система на 1С собирает данные о заказе (габариты и вес каждой коробки, правила штабелирования и кантования).
Через HTTP-сервис или COM-соединение эти данные передаются в Packer3d.
Ядро оптимизации Packer3d за миллисекунды просчитывает идеальную схему укладки.
В 1С возвращаются координаты укладки каждого SKU (X, Y, Z, угол поворота) и графическая картинка-инструкция для сборщика.

Такой гибридный подход позволяет сохранить высокую скорость работы бизнес-логики в 1С и делегировать тяжелые математические расчеты оптимизированному С++ ядру внешней библиотеки.