Задача оптимального размещения объектов на плоскости (так называемая 2D Bin Packing Problem или задача о раскрое) является классической проблемой комбинаторной оптимизации. В контексте складской логистики 1С она возникает при необходимости максимально плотно уложить коробки на поддон, чтобы минимизировать количество используемых паллет и транспортные расходы. Проанализируем ситуацию: поскольку задача относится к классу NP-трудных, найти абсолютно идеальное решение за доли секунды при большом количестве коробок невозможно, поэтому мы будем ориентироваться на эффективные эвристические методы.
Это самый популярный и быстрый в реализации подход. Суть метода заключается в том, чтобы на каждом шаге выбирать «лучший» вариант из доступных, не пытаясь пересчитать все возможные комбинации в будущем. Разберем по шагам стандартный алгоритм для решения этой задачи:
Ширина, Длина и Площадь.Рассмотрим подробнее логику выбора места. Одной из эффективных стратегий является Best-Fit: мы ставим коробку туда, где после её установки остается меньше всего свободного места в текущем ряду.
Если специфика вашего склада требует, чтобы коробки стояли ровными рядами (например, для удобства ручного пересчета), проанализируем алгоритм полок. Поддон разбивается на горизонтальные полосы («полки»). Высота каждой полки определяется самой высокой коробкой, установленной в этом ряду первой.
Посмотрим на пример логики работы этого алгоритма:
В некоторых случаях, когда количество типоразмеров коробок невелико, можно использовать механизм запросов 1С для поиска оптимальной комбинации длин объектов в одном ряду. Это помогает решить «одномерную» часть задачи (как заполнить одну строчку на поддоне). Выясним причину эффективности этого метода: SQL-движок очень быстро выполняет декартово произведение небольших наборов данных.
Проанализируем пример кода для поиска комбинации коробок (палочек), которые максимально заполняют заданную длину (например, ширину поддона 1200 мм):
ВЫБРАТЬ
ВТ.Ширина
ПОМЕСТИТЬ ВТ_Коробки
ИЗ
&ТаблицаКоробок КАК ВТ;
////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
ВТ1.Ширина КАК Ш1,
ВТ2.Ширина КАК Ш2,
ВТ3.Ширина КАК Ш3,
ВТ1.Ширина + ВТ2.Ширина + ВТ3.Ширина КАК ОбщаяШирина
ИЗ
ВТ_Коробки КАК ВТ1,
ВТ_Коробки КАК ВТ2,
ВТ_Коробки КАК ВТ3
ГДЕ
ВТ1.Ширина + ВТ2.Ширина + ВТ3.Ширина <= &МаксШиринаПоддона
ОБЪЕДИНИТЬ ВСЕ
// ... можно добавить соединения для 4, 5 и более коробок
После выполнения такого запроса достаточно выбрать строку с максимальным значением поля ОбщаяШирина. Важный момент: этот способ подходит только для малого количества элементов, иначе количество комбинаций приведет к перегрузке памяти.
Если требуется найти действительно оптимальное решение, а количество коробок на одном поддоне не превышает 10–15 штук, мы можем использовать рекурсию. Разберем по шагам принцип работы функции:
Рассмотрим, как можно ускорить процесс: используйте Случайный поиск. Если полный перебор занимает слишком много времени, ограничьте его по времени (например, 2 секунды на расчет) и в каждой итерации выбирайте случайную коробку из списка подходящих. За 2 секунды компьютер успеет проверить тысячи случайных раскладок и выберет лучшую из них.
При написании кода на языке 1С следует учитывать следующие технические аспекты:
100x200 и 200x100 занимают одинаковую площадь, но могут быть решающими для заполнения «пустот».Внешнюю компоненту на языке C++ или Rust, либо использовать готовые библиотеки через HTTP-сервис (например, на Python с библиотекой rectpack).Таким образом, для большинства учетных систем 1С оптимальным выбором будет жадный алгоритм с предварительной сортировкой по убыванию площади и поддержкой поворота объектов на 90 градусов. Это обеспечит заполняемость поддона на уровне 85–95% при практически мгновенном расчете.