Всем привет. Меня зовут Василий Гуров, я занимаюсь задачами оптимизации в ML Research Lab MAGNIT TECH. В этом материале разберу два промышленных кейса из крупного ретейла – планирование смен сотрудников магазинов и сглаживание нагрузки на распределительные центры.

На поверхности это разные задачи. В первой нужно построить график работы сотрудников по ролям и временным интервалам. Во втором кейсе стоит задача перераспределения логистических потоков так, чтобы снизить пики нагрузки на распределительные центры (РЦ). Но инженерная проблема у них оказалась общей. Прямая time-indexed постановка быстро раздувала модель до сотен тысяч и миллионов бинарных переменных, давала нестабильные рекомендации и плохо укладывалась в SLA.

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

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

Почему модели ломаются на масштабе

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

Вторая проблема – время расчёта. Часто внимание сосредоточено на алгоритмах, но в реальном процессе значительная часть времени уходит на подготовку данных, вызовы ML-моделей, проверку ограничений и запись результата. Иногда оптимизационное ядро занимает меньшую часть общего времени, а узким местом становится прогнозный слой или слой обработки данных. Но в нашем случае именно ускорение решения оптимизационной модели имеет решающее влияние на соблюдение SLA.

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

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

На практике эти ограничения редко решаются выбором более сильного солвера. Чаще приходится менять постановку – укрупнять единицу решения, заранее отсекать заведомо невозможные варианты, разделять ограничения на жёсткие и мягкие, а часть логики переносить в генерацию кандидатов и постобработку.

Меняем единицу решения: от слотов к кандидатам

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

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

Дальше задача сводится к выбору совместимого подмножества кандидатов с учётом спроса, ограничений, штрафов и SLA. В планировании смен таким кандидатом становится допустимая смена. В сглаживании нагрузки на РЦ – допустимый перенос потока.

Кейс 1. Планирование смен сотрудников магазинов

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

Исходная постановка

В терминах исследования операций это вариант employee rostering или workforce scheduling – задачи построения графика сотрудников с ограничениями покрытия спроса, доступности, навыков, трудовых правил и фонда часов. Прямая постановка обычно превращается в time-indexed MILP или CP-SAT модель. В них переменные показывают, работает ли сотрудник в конкретном временном слоте, роли и дне.

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

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

Какой вид могут принять переменные в такой задаче

Переменные могут принять такой вид:

Такая переменная в решении равна единице, если сотрудник e работает в день d в слот t в роли r.

Даже для одного магазина такая модель быстро становится тяжёлой. При 15-минутном шаге и 14 часах работы получаем 56 слотов. Если модель сама выбирает начало и конец смены, то для одного сотрудника и одной роли есть 1596 возможных интервалов. Для 30 сотрудников и 3 ролей это уже около 144 тысяч потенциальных форм смены на день – ещё до учёта перерывов, доступности, заморозок и мягких ограничений. На недельном горизонте такая постановка легко уходит в сотни тысяч или миллионы переменных на магазин.

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

Кандидатные смены. От слотов к готовым вариантам

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

После этого модель решает не «работает ли сотрудник в каждом 15-минутном слоте», а «какую из допустимых смен выбрать». В терминах исследования операций это set covering с ограничениями совместимости. Кандидатная смена покрывает спрос по ролям и слотам, а для сотрудника в день можно выбрать не более одной смены.

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

У такого подхода есть обратная сторона. Если генератор кандидатов слишком узкий или «жёсткий», модель найдёт оптимум только внутри искусственно обеднённого пространства. Поэтому для генератора нужны метрики полноты – сколько кандидатов создано по сотруднику и дню, какие причины отбраковки сработали чаще всего, есть ли хотя бы один допустимый кандидат для критичных ролей и слотов. Иначе можно получить не «оптимальный график», а оптимальный график среди случайно оставшихся вариантов.

Как изменяется ограничения покрытия

После применения такого подхода ограничение покрытия становится значительно проще:

Здесь u – переменная дефицита по недопокрытию. Мы штрафуем её в целевой функции, поэтому модель не падает при отсутствии допустимого решения, а показывает, где и какой ресурс не сходится. После такой трансформации локальная задача обычно имеет до 50 тысяч переменных и решается за 10-30 секунд на магазин или группу похожих магазинов.

Как работает декомпозиция

Практически задача решалась как набор локальных задач по магазинам или группам похожих магазинов. Контур здесь простой. Прогноз нагрузки → перевод в потребность по ролям → генерация кандидатных смен → локальная MILP/CP-SAT модель → постобработка → метрики качества.

Магазин остаётся естественной единицей планирования, но не полностью изолированной. Сверху нужен контроль общих правил, бюджета часов, качества и SLA.

Кейс 2. Сглаживание нагрузки на РЦ

Второй пример – сглаживание нагрузки на распределительный центр. Если в планировании смен мы в основном распределяем людей по времени и ролям, то в РЦ мы управляем потоками - поставки, отгрузки, окна прибытия и отправки, операции приёмки, комплектации, перемещения и обработки.

Исходная постановка

В терминах исследования операций это ближе к задачам Capacity Smoothing – сглаживанию нагрузки относительно ограниченной мощности ресурсов. Если опуститься ниже, к назначению конкретной машины на конкретные ворота и последовательность операций, задача превращается уже в Dock Scheduling. Важно не смешивать эти два уровня в одной монолитной модели. Первый отвечает на вопрос «Куда сдвинуть нагрузку?», а второй – «Как именно исполнить расписание на площадке».

На входе есть план входящих и исходящих потоков, прогноз объёмов, доступность ворот, зоны обработки, мощности, временные окна, персонал, техника, буферы и связи между операциями. Решение должно не «уменьшить работу», а перераспределить потоки таким образом, чтобы снизить пики и не создать проблему дальше по цепочке. Упрощённо можно представить нагрузку РЦ как профиль по времени - сколько условных единиц работы приходится на каждый интервал. Эти единицы могут описывать разные операции – приёмка, размещение, отбор, сборка, отгрузка, обработка возвратов. У каждой операции есть своя пропускная способность и свои ограничения. Один и тот же объём в разных зонах может иметь разную стоимость для системы.

Как выглядит переменая потока для базовой постановки

При реализации монолитной модели с индексацией по времени мы бы назначали каждый поток на слот, ворота, зону и операцию:

Данная переменная равна единице, если поток f обрабатывается в слот t через ворота g, в зоне z на операции o.

При тысячах потоков (а в масштабах Магнита их может быть значительно больше), 24-48 слотах (при почасовой разбивке), нескольких зонах, десятках ворот и разных операциях мы получаем порядка 3 миллионов бинарных переменных на один РЦ и горизонт 1-2 дня. Расчёт длился часами, и был чувствителен к шуму во входных данных.  И главная проблема была в том, что монолитная модель одновременно пыталась решать задачи разного уровня: сглаживать профиль нагрузки, выбирать ворота, учитывать персонал, проверять буферы и не нарушать последовательность операций. При этом часть потоков вообще нельзя двигать из-за сроков годности, жёсткого окна поставщика, связанной отгрузки, критичного товара или транспортных ограничений. Поэтому следующий шаг был таким же, как в планировании смен: перейти от детальной постановки к более крупной единице решения.

Кандидатные переносы. От детального расписания к допустимым move-кандидатам.

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

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

Описание кандидатного переноса

Практически кандидатный перенос описывается как объект

где f - поток, t_{from} и t_{to} - исходный и целевой слоты, z - зона, q - объём или трудоёмкость, p - приоритет, а последний элемент - стоимость отклонения от исходного плана.

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

которое вводится для того, чтобы обеспечить выбор только одного сценария переноса.

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

Как работает декомпозиция

На первом уровне строится агрегированный профиль нагрузки по РЦ, зонам, типам потоков и временным слотам. На втором уровне выделяются интервалы риска – слоты, в которых нагрузка превышает 85% мощности или зоны с конфликтами по воротам, персоналу и буферам. На третьем уровне агрегированная ведущая задача переносит только потоки в допустимых временных окнах. Целевая функция штрафует перегрузку, высокий пик, отклонение от плана, нарушение приоритета и новые пики рядом. Именно этот уровень и отвечает за выбор оптимального подмножества из всех созданных кандидатов.

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

На пятом уровне постобработка проверяет, не ухудшили ли мы соседнюю зону или следующий процесс.

После декомпозиции агрегированная модель имеет до 120 тысяч переменных, а детальные подзадачи проверки допустимости – до 20 тысяч переменных. Первый расчёт рекомендации занимает 1-3 минуты, скользящий пересчёт при изменении входных данных – это 30-90 секунд.

Эвристики. Что спасало модель от красивого, но нерабочего решения

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

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

Пример 1. Смены. Жёсткие правила выносились в генератор кандидатов

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

Пример 2. Смены. Стабильность графика была частью постановки

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

Пример 3. РЦ. Переносы генерировались только в безопасные окна.

В РЦ непереносимые потоки – например критичный товар, жёсткое окно поставщика, связанные входящие и исходящие операции фиксировались заранее. Для переносимых потоков кандидат создавался только если целевой слот не возвращал зону в интервал риска, не ломал буфер перед критичной операцией и не создавал новый пик рядом. Для борьбы с «зубчатым» профилем мы штрафовали не только максимум нагрузки, но и резкие перепады между соседними слотами.

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

Заключение

Главный вывод этих кейсов не в том, что одну задачу удалось решить за 10-30 секунд, а другую – за 1–3 минуты. На масштабе решающим оказался не выбор более мощного солвера, а изменение постановки задачи и выбор альтернативной единицы решения.

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

Именно этот переход к правильной единице решения позволил значительно уменьшить размерность задачи, встроить бизнес-правила до вызова солвера, стабилизировать результат и уложиться в SLA. Солвер остаётся важным инструментом, но промышленная оптимизация выигрывает не за счёт самого продвинутого инструмента решения задач оптимизации, а за счёт архитектуры – генерации валидных кандидатов, разделения жёстких и мягких ограничений, декомпозиции, проверки допустимости и контроля качества результата.

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