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

Middle Mile соединяет склады, сортировочные центры и транспортные хабы. Здесь концентрируются пиковые нагрузки наиболее сложных операционных задач всей цепочки поставок. Но если раньше это была задача для диспетчеров с телефонами и таблицами Excel, то сегодня эту битву ведут алгоритмы и высоконагруженные системы. В этой статье мы углубимся во внутренние механизмы Middle Mile и посмотрим на них как на математические задачи и как на вызов для IT-архитектуры: системам нужно в режиме near real-time собирать потоки событий из десятков источников, поддерживать консистентный «цифровой двойник» сети и пересчитывать планы с жёсткими SLA по задержке и доступности.

Почему «идеального расписания» не существует

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

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

Если представить упрощённо, что для каждого из 50 маршрутов мы выбираем один из 10 вариантов доставки груза, то уже получаем 10⁵⁰ комбинаций, это число с пятьюдесятью нулями. В реальности вариантов на много порядков больше, потому что добавляются менеджмент водителей, временны́е окна, требования к отдыху, взаимная зависимость маршрутов и множество других параметров.

Допустим, вы сможете проверять по 1 миллиарду решений в секунду. Возможно, вы никогда не слышали слово «дециллион» (это число с 33 нулями), но именно три дециллиона лет вам понадобится, чтобы перебрать все варианты для нашего примитивного примера из 50 маршрутов.

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

Поэтому в реальной логистике не ищут идеальное решение. Ищут достаточно хорошее, устойчивое к неопределённости и экономически выгодное.

Суть задачи: что именно нужно оптимизировать

Представьте сеть из десятков узлов (склады, хабы) и сотен возможных маршрутов между ними. Планировщик должен решить, какие машины и водители куда поедут, сколько груза возьмут и сколько часов отработают. При этом на каждую машину и водителя накладываются сотни ограничений: время работы водителей, допустимая грузоподъёмность и объём кузова, доступность техники, требования разных клиентов и сервисных соглашений. По сути, это обобщённая задача Vehicle Routing Problem (VRP) – задача маршрутизации автопарка.

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

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

При этом накладываются жёсткие правила: система должна учесть все ограничения — вместимость машины, часы работы водителя, условия договора и т.д.

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

Как математика справляется с хаосом

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

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

Далее наступает этап проверки устойчивости через симуляции. Система задаёт вопросы: что если спрос вырастет на 10%? Что если 15% водителей будут недоступны? Что если мы закупим собственный флот из 100 грузовиков или подпишем контракты с десятью новыми перевозчиками? Эти симуляции проводятся на разных горизонтах:

• Долгосрочные — для понимания требуемой мощности
• Среднесрочные — для формирования предварительных рабочих рейсов для водителей
• Краткосрочные — для заполнения этих рейсов реальными грузами

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

IT-фундамент

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

Архитектурно процесс устроен следующим образом:

Поток данных. Информация поступает не статичными таблицами, а потоком событий: GPS, телематика, сканы, погодные условия. Для этого нужны надежные ETL-пайплайны с поддержкой эволюции схем, дедупликации и контроля качества данных. Они формируют единый источник истины (Feature Store).

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

Надежность и SLA. Система должна соблюдать жесткие временные рамки. Реализован механизм Graceful Degradation: если точный алгоритм (например, MILP) не успевает, система автоматически переключается на эвристики или упрощенные модели. Инженерная задача здесь — это управление конкурентностью, кэширование и поиск баланса между скоростью ответа и качеством оптимизации.

Перейдем от теории к практике.

Математические примеры

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

Допустим, у нас есть 2 транспортных хаба: N (North) и C (Central).

Между ними существует логистическая линия NC, по которой курсирует наш транспорт.

Груз и блоки

Введем понятия:

load — это единица груза (например, трейлер).

block — одна смена/рейс (перевозка некоторого числа load).

Блок имеет следующие параметры:

• длительность смены: 8 часов
• вместимость q = 1 load (за смену)

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

1P означает (First-Party / Первая сторона). Это ваши собственные мощности. Вы напрямую владеете активом или заключаете долгосрочный контракт с фиксированными обязательствами.

Если купили 20 блоков — платим за 20, даже если использовали 15.

Это дополнительная, гибкая мощность от внешнего партнера. Здесь мы платим только за фактически активированные смены, но не можем взять больше 40 в неделю.

Это мощность, доступная на открытом рынке. Ее можно покупать оперативно и по мере необходимости, но она дороже. Именно этот вариант может выручить в различных непредвиденных ситуациях.

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

Планирование

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

Напомню основные типы планирования:

Long-term — долгосрочное планирование на 1-6 месяцев

Mid-term — среднесрочное недельное расписание

Short-term — краткосрочное за 1-2 дня до выезда

Вот тут и начинается работа.

Long-term — планирование на 1-6 месяцев

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

Суть задачи

Long-term — это задача решения в условиях неопределённости: заранее требуется выбрать решение S (портфель контрактов), которое минимизирует ожидаемую суммарную стоимость по распределению возможных спросов.

У нас есть разные сценарии k, которые влекут за собой различный спрос Dᵏ. Это количество loads, требуемое для того, чтобы его удовлетворить. Каждый сценарий k может быть реализован с вероятностью, которую обозначим как pₖ.

Математически: если C(S,Dᵏ) — стоимость портфеля S при реализации спроса D по сценарию k, то там нужно минимизировать эту стоимость:

Мы хотим выяснить, во сколько нам обойдется выбранная стратегия S . Для этого работает простое математическое ожидание: рассчитываем стоимость для каждого возможного сценария k. Умножаем каждую такую стоимость на вероятность pₖ наступления этого сценария. Суммируем все полученные взвешенные стоимости. Итоговая величина и есть ожидаемая (средняя прогнозируемая) стоимость нашего портфеля S.

Два простых портфеля. Когда скупой платит дважды

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

Портфель A: приобрести 30 committed-блоков заранее. Эта стратегия делает ставку на максимальное использование собственных фиксированных мощностей, а для покрытия возможного дефицита используется спотовый рынок.

Стоимость при реализованном спросе D:

Пояснение: первые 30 loads это наш committed флот. Мы за них уже заплатили. Если спрос D>30, экстренно докупаем (D — 30) spot-блоков.

Портфель B: построен на иной логике. Приобретаем только 20 committed-блоков, но дополнительно имеем возможность использовать до 10 flexible-блоков, оплачивая только фактически использованные. Мы стремимся снизить фиксированные расходы, заместив часть дорогих обязательств более гибким, но более дорогим в использовании ресурсом.

Формула для расчёта стоимости усложняется, так как теперь нужно учитывать три источника:

Фактическая стоимость зависит от D

Пояснение: первые 20 loads покрываются committed; следующие до 10 — flexible (если спрос превышает 20, но не более 30 в сумме); всё сверх 30 — spot.

Базовая фиксированная стоимость здесь ниже — 8,000 у.е. При спросе в 20 блоков гибкие и спотовые мощности не задействуются, и стоимость остаётся на этом уровне.

При спросе в 25 блоков требуется 5 гибких блоков, что добавляет 2,500 у.е., доводя общую сумму до 10,500 у.е.

В пиковом сценарии используются все 10 доступных гибких блоков (ещё 5,000 у.е.) и дополнительно 5 спотовых блоков (3,500 у.е.), что в сумме даёт 16,500 у.е.

Ожидаемая стоимость:

Интерпретация результатов:

Портфель B даёт меньшую ожидаемую стоимость: 10,950 vs 12,700. Экономия в ожидании: 12,700-10,950 = 1,750 у.е. Эта экономия достигается за счёт сокращения фиксированных обязательств и оплаты гибких ресурсов только по факту их использования.

Однако в худшем сценарии (с 20% вероятностью)

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

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

И в результате мы формируем рекомендацию для long-term блока:

«Для линии NC стоит иметь примерно X committed-блоков и Y гибких блоков такого-то типа».

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

Mid-term — недельное расписание

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

Для решения проблемы используется Mixed-Integer Linear Programming (MILP) — смешанно-целочисленное линейное программирование.

Итак, нам нужно выбрать, какие блоки будут перевезены и каких водителей на них назначить.

Пусть B — множество кандидатов блоков, D — множество водителей, T — дни недели.

В модели используются двоичные переменные двух типов: переменные x_b, определяющие, будет ли выполнен блок b, и переменные y_(d,b), указывающие, назначен ли водитель d на блок b.

Переменные:

Каждый блок характеризуется своей вместимостью q_b (объём груза), продолжительностью h_b в часах и привязкой к определённому дню недели. Водители имеют индивидуальные недельные лимиты рабочих часов H_d и набор допусков к различным типам работ.

Каждый block b характеризуется:

Система ограничений моделирует реальные операционные условия. Первое и основное ограничение — покрытие спроса: суммарная вместимость всех активированных блоков в каждый день t должна быть не меньше прогнозируемого спроса D_t на этот день. Это гарантирует, что весь планируемый объём перевозок будет выполнен.

Второе ограничение связано с контрактными обязательствами: необходимо активировать как минимум comm_min commited-блоков и не более flex_max flexible-блоков, что обеспечивает выполнение условий долгосрочных соглашений.

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

Четвёртое важное ограничение — требования к отдыху между сменами. Если интервал между окончанием одного блока и началом другого составляет менее 11 часов, один и тот же водитель не может быть назначен на оба блока. Это условие моделируется неравенством для каждой такой пары блоков:

Пятое ограничение учитывает квалификацию и допуски водителей. Для каждого сочетания водителя и блока задаётся параметр eligible_(d,b), равный единице, если водитель имеет право выполнять данный блок. Назначение возможно только при наличии соответствующего допуска.

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

Целевая функция (пример):

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

Short-term(1-2 дня):

Наступает «день X». Прогноз рассчитал 25 машин, а фактически приехало 24. Один водитель заболел, на трассе перекрыли мост. Красивое Mid-term планирование больше не актуально. Времени на долгие вычисления MILP уже нет. Включается режим оперативного реагирования.

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

Формально это выражается как минимизация суммы затрат на спотовом рынке и всех штрафов за срывы сроков:

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

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

Алгоритм сортирует нераспределенные грузы по срочности или стоимости штрафа и пытается «впихнуть» самый важный груз в ближайшую доступную машину. Это похоже на сборы чемодана за 5 минут до такси — вещи будут упакованы, и вы уедете, но чемодан, скорее всего, не застегнется, а рубашки помнутся. «Жадный» алгоритм дает допустимое решение мгновенно. Оно почти всегда получается дорогим и не оптимальным, но на расчет более хорошего решения времени нет.

Будущее Middle Mile: динамические расписания

Будущее логистики — за динамическими, адаптивными системами. Комбинация машинного обучения для точного прогнозирования и продвинутых алгоритмов оптимизации позволит генерировать не один жёсткий план, а множество сценариев. Прогнозирование станет точнее благодаря ML, а планирование – быстрее благодаря ИИ.

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

Заключение: математика, которая держит мир в движении

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

Закладка

-

0

+

518

Twitter

VK

Telegram