В процессе автоматизации складской логистики и служб доставки перед разработчиком 1С часто возникает задача: эффективно распределить перечень товаров по грузовым местам (коробкам, пакетам, паллетам). При этом на каждое грузовое место накладываются ограничения по объему или весу, а количество самих коробок необходимо минимизировать.
В этой статье мы подробно разберем математическую суть этой задачи, проанализируем, почему стандартный перебор комбинаций «в лоб» не подходит для реальной работы, и рассмотрим готовые программные решения для платформы 1С:Предприятие — от классической рекурсии до быстрых эвристических алгоритмов.
Разработчики часто путают эту задачу с классической «задачей о рюкзаке» (Knapsack Problem). Давайте разберем разницу между ними:
Очевидно, что задача распределения товаров клиента по пакетам относится именно к категории Bin Packing Problem. Это NP-трудная задача. Это означает, что не существует быстрого алгоритма, гарантирующего поиск абсолютно идеального решения за короткое время при большом числе элементов.
Если мы попытаемся решить задачу методом полного перебора всех возможных вариантов комбинаций распределения, то столкнемся с математическим понятием чисел Белла и чисел Стирлинга второго рода:
Давайте посмотрим, как быстро растет количество комбинаций с ростом числа товаров $n$:
Если в заказе покупателя будет хотя бы 15–20 позиций, попытка полного перебора всех вариантов «в лоб» приведет к полному зависанию сессии 1С и перегрузке процессора сервера.
---
Рассмотрим ситуацию, когда количество товаров гарантированно мало (не более 6–8 штук) и нам действительно необходимо перебрать все возможные комбинации размещения, чтобы выбрать наиболее плотную упаковку. Для этого можно применить рекурсивный алгоритм.
Проанализируем пример кода на встроенном языке 1С, который генерирует распределение предметов по доступным местам. Обратите внимание, что мы адаптировали алгоритм, избегая избыточного дублирования симметричных вариантов (когда пустые коробки просто меняются местами).
Ниже представлен пример процедуры, реализующей полный перебор через дерево рекурсивных вызовов:
Перем мТовары; // Массив с объемами товаров
Перем мМеста; // Массив текущего заполнения грузовых мест
Перем МаксОбъемМеста; // Ограничение на одно грузовое место
Перем ЛучшееРешение; // Сюда сохраним самый оптимальный вариант
// Инициализация и запуск алгоритма
Процедура РаспределитьТоварыРекурсивно()
// Исходные данные для примера
мТовары = Новый Массив;
мТовары.Добавить(10); // Объем 1-го товара
мТовары.Добавить(20); // Объем 2-го товара
мТовары.Добавить(15); // Объем 3-го товара
мТовары.Добавить(5); // Объем 4-го товара
МаксОбъемМеста = 25; // Ограничение объема коробки
мМеста = Новый Массив; // Массив, где каждый элемент — текущий объем коробки
ЛучшееРешение = Неопределено;
// Запускаем рекурсивный перебор с первого товара (индекс 0)
ПоискРешения(0);
// Выводим результат
Если ЛучшееРешение <> Неопределено Тогда
ВывестиРезультатУпаковки(ЛучшееРешение);
Иначе
Сообщить("Не удалось распределить товары по местам!");
EndIf;
КонецПроцедуры
Теперь опишем основное тело рекурсивного перебора. На каждом шаге мы пытаемся положить текущий товар в одно из уже созданных грузовых мест либо открыть новое грузовое место:
Процедура ПоискРешения(ИндексТовара)
// Если распределили все товары
Если ИндексТовара = мТовары.Количество() Тогда
СохранитьЛучшийВариант();
Возврат;
КонецЕсли;
ТекущийТовар = мТовары[ИндексТовара];
// Вариант А: Пробуем положить товар в уже существующие коробки
Для НомерМеста = 0 По мМеста.Количество() - 1 Цикл
Если мМеста[НомерМеста] + ТекущийТовар <= МаксОбъемМеста Тогда
// Товар помещается в коробку, "кладем" его туда
мМеста[НомерМеста] = мМеста[НомерМеста] + ТекущийТовар;
// Рекурсивный переход к следующему товару
ПоискРешения(ИндексТовара + 1);
// Откат назад (бэктрекинг) для перебора других вариантов
мМеста[НомерМеста] = мМеста[НомерМеста] - ТекущийТовар;
КонецЕсли;
КонецЦикла;
// Вариант Б: Пробуем открыть новую коробку под этот товар
// Ограничим общее количество открываемых коробок общим числом товаров
Если мМеста.Количество() < мТовары.Количество() Тогда
мМеста.Добавить(ТекущийТовар);
ПоискРешения(ИндексТовара + 1);
// Откат назад
мМеста.Удалить(мМеста.Количество() - 1);
КонецЕсли;
КонецПроцедуры
Для завершения алгоритма нам понадобится вспомогательная функция, которая анализирует полученное решение и сохраняет его, если оно требует меньше грузовых мест, чем найденные ранее варианты:
Процедура СохранитьЛучшийВариант()
КоличествоМест = мМеста.Количество();
Если ЛучшееРешение = Неопределено Или КоличествоМест < ЛучшееРешение.Количество() Тогда
// Копируем структуру текущего распределения в ЛучшееРешение
ЛучшееРешение = Новый Массив;
Для Каждого ОбъемМеста Из мМеста Цикл
ЛучшееРешение.Добавить(ОбъемМеста);
КонецЦикла;
КонецЕсли;
КонецПроцедуры
Процедура ВывестиРезультатУпаковки(Результат)
Сообщить("Минимально необходимое количество грузовых мест: " + Результат.Количество());
Для Номер = 0 По Результат.Количество() - 1 Цикл
Сообщить("Грузовое место №" + (Номер + 1) + ", объем заполнения: " + Результат[Номер]);
КонецЦикла;
КонецПроцедуры
---
Поскольку полный перебор пасует перед заказами с большим количеством товаров, в реальных складских системах (WMS) на базе 1С применяют быстрые приближенные алгоритмы. Они работают за сотые доли секунды и дают результат, который в 95% случаев совпадает с идеальным математическим решением.
Наиболее популярный и эффективный среди них — метод First-Fit Decreasing (FFD) или «Первый подходящий по убыванию».
Разберем по шагам логику работы алгоритма FFD:
Напишем этот лаконичный и быстрый алгоритм на встроенном языке 1С 8.3:
Функция РаспределитьПоАлгоритму_FFD(ТаблицаТоваров, МаксОбъемМеста) Экспорт
// Шаг 1. Сортируем таблицу товаров по убыванию объема
ТаблицаТоваров.Сортировать("Объем Убыв");
// Структура для хранения результатов упаковки:
// Массив коробок, где каждая коробка — это структура со списком товаров и текущим суммарным объемом
мГрузовыеМеста = Новый Массив;
// Шаг 2. Распределяем каждый товар
Для Каждого СтрокаТовара Из ТаблицаТоваров Цикл
ТоварУпакован = Ложь;
// Шаг 3. Ищем место в уже открытых коробках
Для Каждого Коробка Из мГрузовыеМеста Цикл
Если (Коробка.ТекущийОбъем + СтрокаТовара.Объем) <= МаксОбъемМеста Тогда
// Добавляем товар в существующую коробку
Коробка.Содержимое.Добавить(СтрокаТовара.ТоварСсылка);
Коробка.ТекущийОбъем = Коробка.ТекущийОбъем + СтрокаТовара.Объем;
ТоварУпакован = Истина;
Прервать; // Товар упакован, переходим к следующему
КонецЕсли;
КонецЦикла;
// Шаг 4. Если в существующие коробки товар не влез — открываем новую
Если Не ТоварУпакован Тогда
НоваяКоробка = Новый Структура;
НоваяКоробка.Вставить("Содержимое", Новый Массив);
НоваяКоробка.Содержимое.Добавить(СтрокаТовара.ТоварСсылка);
НоваяКоробка.Вставить("ТекущийОбъем", СтрокаТовара.Объем);
мГрузовыеМеста.Добавить(НоваяКоробка);
КонецЕсли;
КонецЦикла;
Возврат мГрузовыеМеста;
КонецФункции
Этот алгоритм работает чрезвычайно быстро даже на списках из сотен тысяч номенклатурных позиций. Математически доказано, что количество коробок, полученное методом FFD, превышает теоретический абсолютный минимум не более чем на 22% в самом худшем случае, а на практике этот показатель редко превышает 2–3%.
---
В реальной жизни объем — далеко не единственный критерий упаковки. Если мы хотим создать полноценное решение для склада, нам нужно учесть ряд важных физических ограничений:
Применяя алгоритм FFD с добавлением двумерного контроля ограничений (Объем + Вес), вы получите стабильное, надежное и быстрое решение для распределения заказов по грузовым местам, которое без проблем справится с любым потоком документов в вашей базе 1С.