Размещение товаров 2D

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

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

Особенностью нашего решения является учет возможных поворотов предметов. Однако для сохранения приемлемой производительности вычислений мы ограничимся четырьмя возможными углами поворота: 0°, 90°, 180° и 270°. Это разумный компромисс между гибкостью размещения и сложностью вычислений.

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

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

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

Постановка задачи

• Необходимо разместить нескольких товаров сложной формы на прямоугольной площадке ограниченного размера;
• Каждый товар состоит из нескольких квадратных блоков, которые должны полностью помещаться на площадке;
• Товары могут поворачиваться на углы, кратные 90°;
• Форма товаров задается относительными координатами блоков;
• Площадка также состоит из квадратных блоков и имеет фиксированные размеры (ширину и высоту);
• Все блоки всех товаров должны размещаться без перекрытия.

Решение задачи

1. Выбор модели

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

• Необходимость работы с целочисленными координатами позиций фигур;
• Использование булевых переменных для моделирования поворотов;
• Сложные геометрические ограничения на непересечение фигур;
• Условные ограничения, зависящие от угла поворота фигур.

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

2. Создание модели

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

// Создаем объект модели
Модель = О2
    .Модели()
    .МодельОграничений()
    .СоздатьМодель();

3. Ввод данных

Зададим размеры площадки и список фигур для размещения:

// Размеры площадки
ШиринаПлощадки = 6;
ВысотаПлощадки = 5;

Фигуры = Новый Массив;
Фигуры.Добавить(Фигура_I());
Фигуры.Добавить(Фигура_O());
// ... добавление остальных фигур (см. полный пример)

Каждая фигура описывается массивом точек (относительных координат блоков), например:

Функция Фигура_I()
    Возврат О2.Утилиты().Массив(
        Точка2D(0, 0),
        Точка2D(0, 1),
        Точка2D(0, 2),
        Точка2D(0, 3)
    );
КонецФункции

Функция Точка2D(X, Y)  
    Возврат Новый Структура("X, Y", X, Y);
КонецФункции

4. Регистрация переменных

Для каждого товара создадим переменные:

• Координаты размещения (X, Y);
• Угол поворота;
• Флаги поворота (для каждого возможного угла);

Товар_X         = Модель.ПеременнаяДиапазона(0, ШиринаПлощадки - 1);
Товар_Y         = Модель.ПеременнаяДиапазона(0, ВысотаПлощадки - 1);

УголПоворота    = Модель.ПеременнаяДиапазона(0, 3);
ФлагиПоворота   = Модель.МассивБулевыхПеременных(4);

Важное понятие: позиция блока. Каждый блок товара имеет свою позицию на площадке, которая вычисляется по формуле: Позиция = X + Y * ШиринаПлощадки.

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

Добавим для каждого блока товара переменную позиции:

ПозицииБлоковТовара = Модель.МассивПеременныхДиапазона(
    Фигура.Количество(), 
    0, 
    ШиринаПлощадки * ВысотаПлощадки - 1
);

5. Установка ограничений

Ограничения на повороты. Свяжем переменную угла поворота с флагами поворота:

Модель.ДобавитьСловарь(УголПоворота, ФлагиПоворота);

Метод ДобавитьСловарь однозначно связывает значение переменной с активацией ровно одного флага из указанного массива.

Ограничения на границы площадки. Для каждого блока каждого товара проверяем, что он не выходит за границы площадки:

Модель.Ограничения().ЗначениеБольшеИлиРавно(Блок_X, 0, ФлагПоворота);
Модель.Ограничения().ЗначениеМеньше(Блок_X, ШиринаПлощадки, ФлагПоворота);

Модель.Ограничения().ЗначениеБольшеИлиРавно(Блок_Y, 0, ФлагПоворота);
Модель.Ограничения().ЗначениеМеньше(Блок_Y, ВысотаПлощадки, ФлагПоворота);

Данные ограничения необходимо установить для каждого блока и для каждого угла поворота.

Связь координат и позиций. Для каждого блока свяжем его координаты (X, Y) с позицией:

// ПозицияБлока = Блок_X + Блок_Y * ШиринаПлощадки
Модель.Ограничения().ЗначениеРавно(
    ПозицияБлока, 
    Модель.Выражения().Сумма(Блок_X, Модель.Выражения().Терм(Блок_Y, ШиринаПлощадки)), 
    ФлагПоворота
);

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

Ограничение на непересечение. Все блоки всех товаров должны занимать разные позиции, укажем это:

Модель.Ограничения().ВсеРазличные(ПозицииВсехБлоков);

Здесь ПозицииВсехБлоков - это массив, куда мы предварительно поместили все позиционные переменные всех блоков всех товаров.

6. Решение модели

Запускаем процесс поиска решения:

// Выполняем поиск решения
Решение = Модель.Решить(); 

7. Вывод результатов

Выведем найденное решение в удобном формате, показывая для каждого товара его координаты и угол поворота:

Если Решение.РешениеНайдено() Тогда      
    Сообщение = "Размещение товаров: " + Символы.ПС;
    Для К_товар = 0 По Товары.ВГраница() Цикл
        Товар = Товары[К_товар];
        УголПоворота = Решение.ЗначениеПеременной(Товар.УголПоворота);	
        Товар_X = Решение.ЗначениеПеременной(Товар.X);
        Товар_Y = Решение.ЗначениеПеременной(Товар.Y);
        
        Сообщение = Сообщение + СтрШаблон(
            "  - Товар №%1: X=%2, Y=%3, Поворот=%4°%5",
            К_товар + 1,
            Товар_X,
            Товар_Y,
            УголПоворота * 90,
            Символы.ПС
        );
    КонецЦикла;
    
    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено. Статус: " + Решение.Статус());
КонецЕсли;

Полный код решения задачи

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

Данный пример демонстрирует 2D расстановку плоских фигур, однако вы без труда сможете доработать его для варианта упаковки 3D объектов, состоящих из кубов, в контейнер с заданными габаритами.

Процедура РешитьНаСервере()
	// Создаем объект модели
    Модель = О2
        .Модели()
        .МодельОграничений()
        .СоздатьМодель();

    // Указываем размеры площадки
    ШиринаПлощадки = 6;
    ВысотаПлощадки = 5;

    // Указываем список фигур для размещения
    Фигуры = Новый Массив;
    Фигуры.Добавить(Фигура_I());
    Фигуры.Добавить(Фигура_O());
    Фигуры.Добавить(Фигура_T());
    Фигуры.Добавить(Фигура_S());
    Фигуры.Добавить(Фигура_Z());
    Фигуры.Добавить(Фигура_J());
    Фигуры.Добавить(Фигура_L());

    // Создаем массив для хранения переменных с позициями
    // каждого блока каждого товара
    ПозицииВсехБлоков = Новый Массив();
	
    // Формируем модель
    Товары = Новый Массив;                  
    Для Каждого Фигура Из Фигуры Цикл
        Товар = Новый Структура;

        // Создаем переменные координат X и Y
        Товар_X = Модель.ПеременнаяДиапазона(0, ШиринаПлощадки - 1);
        Товар_Y = Модель.ПеременнаяДиапазона(0, ВысотаПлощадки - 1);

        // Создаем переменную для угла поворота и словарь флагов
        УголПоворота 	= Модель.ПеременнаяДиапазона(0, 3);
        ФлагиПоворота 	= Модель.МассивБулевыхПеременных(4);

        Модель.ДобавитьСловарь(УголПоворота, ФлагиПоворота);

        // Добавляем переменные глобальных координат для каждого блока фигуры
        // и добавляем их в общий массив координат всех блоков всех фигур
        ПозицииБлоковТовара = Модель.МассивПеременныхДиапазона(
            Фигура.Количество(), 
            0, 
            ШиринаПлощадки * ВысотаПлощадки - 1
        );

        Для Каждого ПозицияБлока Из ПозицииБлоковТовара Цикл
            ПозицииВсехБлоков.Добавить(ПозицияБлока);
        КонецЦикла;

        // Добавляем ограничения для каждого возможного поворота
        Для К_поворот = 0 по 3 Цикл
            ФлагПоворота		= ФлагиПоворота[К_поворот];
            ПовернутаяФигура 	= ПовернутьФигуру(Фигура, К_поворот);
            
            Для К_блок = 0 По ПовернутаяФигура.ВГраница() Цикл
                Блок 	= ПовернутаяФигура[К_блок];
                
                Сдвиг_X = Блок.X;
                Сдвиг_Y = Блок.Y;
                
                // Получаем выражения для координат блоков
                Блок_X = Модель.Выражения().Сумма(Товар_X, Сдвиг_X);
                Блок_Y = Модель.Выражения().Сумма(Товар_Y, Сдвиг_Y);
                
                // Ограничение: Координата X не должна выходить за границы площадки
                // Ограничение действует только при указанном повороте
                Модель.Ограничения().ЗначениеБольшеИлиРавно(Блок_X, 0, ФлагПоворота);
                Модель.Ограничения().ЗначениеМеньше(Блок_X, ШиринаПлощадки, ФлагПоворота);
                
                // Ограничение: Координата Y не должна выходить за границы площадки
                // Ограничение действует только при указанном повороте
                Модель.Ограничения().ЗначениеБольшеИлиРавно(Блок_Y, 0, ФлагПоворота);
                Модель.Ограничения().ЗначениеМеньше(Блок_Y, ВысотаПлощадки, ФлагПоворота);
                
                // Связываем позицию блока с его координатми X и Y (Позиция = X + Y * Ширина);
                // Связь работает только при укзанном повороте
                ПозицияБлока = ПозицииБлоковТовара[К_блок];
                
                Модель.Ограничения().ЗначениеРавно(
                    ПозицияБлока, 
                    Модель.Выражения().Сумма(Блок_X, Модель.Выражения().Терм(Блок_Y, ШиринаПлощадки)), 
                    ФлагПоворота
                );
            КонецЦикла;
        КонецЦикла;

        // Сохраняем важные данные товара для последующего вывода результатов
        Товар.Вставить("Фигура",        Фигура);
        Товар.Вставить("X",             Товар_X);
        Товар.Вставить("Y",             Товар_Y);
        Товар.Вставить("УголПоворота",  УголПоворота);

        Товары.Добавить(Товар);
    КонецЦикла; 

    // Ограничение: позиции всех блоков должны быть различны
    Модель.Ограничения().ВсеРазличные(ПозицииВсехБлоков);


    // Решение модели
    ПараметрыПоиска = О2_Демо.ПолучитьПараметрыПоиска(ЭтаФорма);	
    Решение 		= Модель.Решить(ПараметрыПоиска); 
	
	
    // Выводим результаты
    Если Решение.РешениеНайдено() Тогда      
        Сообщение = "Размещение товаров: " + Символы.ПС;
        Для К_товар = 0 По Товары.ВГраница() Цикл
            Товар           = Товары[К_товар];
            
            УголПоворота    = Решение.ЗначениеПеременной(Товар.УголПоворота);	
            Товар_X         = Решение.ЗначениеПеременной(Товар.X);
            Товар_Y         = Решение.ЗначениеПеременной(Товар.Y);
            
            Сообщение = Сообщение + СтрШаблон(
                "  - Товар №%1: X=%2, Y=%3, Поворот=%4°%5",
                К_товар + 1,
                Товар_X,
                Товар_Y,
                УголПоворота * 90,
                Символы.ПС
            );
        КонецЦикла;

        Сообщить(Сообщение);
    Иначе
        Сообщить("Решение не найдено. Статус: " + Решение.Статус());
    КонецЕсли;
КонецПроцедуры

Функция Фигура_I()
    Возврат О2.Утилиты().Массив(
        Точка2D(0, 0),
        Точка2D(0, 1),
        Точка2D(0, 2),
        Точка2D(0, 3)
    );
КонецФункции 

Функция Фигура_O()
    Возврат О2.Утилиты().Массив(
        Точка2D(0, 0),
        Точка2D(1, 0),
        Точка2D(0, 1),
        Точка2D(1, 1)
    );
КонецФункции

Функция Фигура_T()
    Возврат О2.Утилиты().Массив(
        Точка2D(0, 0),
        Точка2D(1, 0),
        Точка2D(2, 0),
        Точка2D(1, -1)
    );
КонецФункции

Функция Фигура_S()
    Возврат О2.Утилиты().Массив(
        Точка2D(0, 0),
        Точка2D(1, 0),
        Точка2D(1, 1),
        Точка2D(2, 1)
    );
КонецФункции

Функция Фигура_Z()
    Возврат О2.Утилиты().Массив(
        Точка2D(0, 0),
        Точка2D(1, 0),
        Точка2D(1, -1),
        Точка2D(2, -1)
    );
КонецФункции  

Функция Фигура_J()
    Возврат О2.Утилиты().Массив(
        Точка2D(0, 0),
        Точка2D(0, -1),
        Точка2D(0, -2),
        Точка2D(-1, -2)
    );
КонецФункции

Функция Фигура_L()
    Возврат О2.Утилиты().Массив(
        Точка2D(0, 0),
        Точка2D(0, -1),
        Точка2D(0, -2),
        Точка2D(1, -2)
    );
КонецФункции

Функция ПовернутьФигуру(ИсходнаяФигура, УголПоворота)
    Если УголПоворота = 0 Тогда
        Возврат ИсходнаяФигура;
    КонецЕсли;

    ПовернутаяФигура = Новый Массив;
    Для Каждого Точка Из ИсходнаяФигура Цикл
        X = Точка.X;
        Y = Точка.Y;
        
        Если УголПоворота = 1 Тогда
            НоваяТочка = Точка2D(Y, -X);        // Поворот на 90°
        ИначеЕсли УголПоворота = 2 Тогда
            НоваяТочка = Точка2D(-X, -Y);       // Поворот на 180°
        ИначеЕсли УголПоворота = 3 Тогда
            НоваяТочка = Точка2D(-Y, X);        // Поворот на 270°
        КонецЕсли;
        
        ПовернутаяФигура.Добавить(НоваяТочка);
    КонецЦикла;

    Возврат ПовернутаяФигура;        
КонецФункции

Функция Точка2D(X, Y)  
    Возврат Новый Структура("X, Y", X, Y);
КонецФункции

  Скачать пример