Table of Contents

Перебои в цепочке поставок и необходимость устойчивости

Глобальные цепочки поставок становятся все более сложными и взаимосвязанными, но они также более уязвимы для сбоев, чем когда-либо прежде. От пандемии COVID-19 и экстремальных погодных явлений до геополитической нестабильности и кибератак компании сталкиваются с растущим спектром рисков, которые могут остановить производство, отложить поставки и подорвать доверие клиентов. Традиционные детерминированные модели планирования, которые предполагают идеальное знание спроса, времени выполнения заказа и затрат, часто терпят неудачу в условиях такой неопределенности. Чтобы справиться с этим, предприятия обращаются к надежным целочисленным моделям программирования, которые явно объясняют изменчивость и наихудшие сценарии, позволяя лицам, принимающим решения, проектировать сети поставок, которые остаются жизнеспособными даже тогда, когда условия резко меняются.

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

Понимание целочисленного программирования в цепочках поставок

Целое программирование — это раздел математической оптимизации, где некоторые или все переменные решения ограничены целыми значениями. В контексте цепочки поставок модели IP захватывают такие решения, как:

  • Количество объектов, которые можно открыть или закрыть
  • количество инвентаря, которое должно храниться в каждом месте (часто целые числа из-за упаковки)
  • Присвоение клиентов распределительным центрам
  • Маршрутизация транспортных средств с фиксированной пропускной способностью

Стандартная формула целочисленного программирования состоит из объективной функции (например, минимизации общей стоимости) и набора ограничений (например, пределов мощности, требований к уровню обслуживания).

Минимизируйте cTx при условии Ax ≤ b, x ∈ Zn (или смешанного целого с реальными переменными).

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

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

Ключевые характеристики моделей программирования с высоким целым числом

Для построения надежной модели IP для устойчивости цепочки поставок необходимы следующие характеристики:

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

Ключевые элементы надежных моделей в деталях

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

Неопределенное моделирование

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

Пример: В многоэталонной модели инвентаризации неопределенный спрос d i на продукт i моделируется как d i ∈ [μ i — σ i, μ i + σ i], где μ i — прогноз, а σ i — максимальное отклонение. Чтобы избежать чрезмерной защиты, надежная модель может ввести бюджет неопределенности Γ, который ограничивает общее отклонение по всем продуктам, представляя идею о том, что не все требования будут в своих крайностях одновременно.

Сценарный анализ

Когда распределения вероятностей доступны, методы генерации сценариев (например, моделирование Монте-Карло, сопоставление моментов или историческая кластеризация) создают конечный набор сценариев, которые приближаются к базовой случайности. Каждый сценарий имеет связанную вероятность. Затем надежная IP-модель оптимизирует этот дискретный набор, гарантируя, что ограничения для каждого сценария (или с вероятностными гарантиями). Для большого количества сценариев используются методы разложения, такие как разложение Бендеров или прогрессивное хеджирование, чтобы сохранить проблему разрешимой.

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

Объективные функции: балансирование затрат и устойчивости

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

  • Минимизируйте наихудшие затраты: Защищает от самого неблагоприятного сценария. Это может быть чрезмерно консервативным, но уместным, когда сбои могут быть катастрофическими.
  • Минимизация ожидаемых затрат при условии ограничения на наихудший случай: Предлагает компромисс между эффективностью и устойчивостью.
  • Минимизируйте стоимость наихудших сценариев (1-α)% (Условная стоимость в риске, CVaR): Сосредоточьтесь на хвосте распределения затрат, популярном выборе в области управления рисками в финансах и цепочках поставок.
  • Максимизация уровня обслуживания при условии бюджетных ограничений: В гуманитарной логистике или высокотехнологичном производстве надежное удовлетворение спроса может быть важнее, чем стоимость.

Ограничения: обеспечение осуществимости в сценариях

Надежные ограничения требуют, чтобы для каждой реализации в наборе неопределенности решение должно удовлетворять требованиям к емкости, сохранению потока и уровню обслуживания. Это моделируется с использованием надежных аналогов - реформаций, которые превращают бесконечное количество ограничений в конечное множество (обычно через дуальность). Например, ограничение емкости объекта, такое как Σ j flow ij ≤ C i, может потребоваться для всех реализаций спроса. Используя надежные методы оптимизации, это становится линейным ограничением с дополнительными переменными, представляющими отклонение в худшем случае. К компромиссу добавляется размер проблемы, но современные решатели (например, Gurobi, CPLEX) эффективно обрабатывают эти структуры.

Методы повышения надежности: передовые методы

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

Стохастическое программирование с помощью регресса

Двухступенчатое стохастическое целочисленное программирование является одной из наиболее широко изученных структур. На первом этапе принимаются такие решения, как открытие объекта, выбор поставщика и инвестиции в технологии. На втором этапе после реализации требований оптимизируются оперативные решения (количество продукции, распределение запасов, маршрутизация). Цель состоит в минимизации затрат первой стадии плюс ожидаемое значение затрат второй стадии. Эта модель обычно решается с помощью разложения Бендеров, где основная задача обрабатывает решения первой стадии, а подзадачи оценивают затраты второй стадии для каждого сценария. Подзадачи часто сами являются целочисленными задачами программирования, требующими расширенного разложения, как целые L-образные сокращения.

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

Оптимизация с использованием бюджетной неопределенности

Этот метод, популяризированный Берцимасом и Симом, определяет набор неопределенности, где каждый неопределенный параметр может отклоняться от своей номинальной стоимости не более чем на заданную сумму, но общее нормализованное отклонение по всем параметрам ограничено бюджетом Γ. Надежный аналог линейного ограничения включает добавление термина, который масштабируется с Γ, давая трактуируемую линейную проблему. Поскольку набор неопределенности является многогранным, модель сохраняет свою структуру и может быть решена со стандартными решателями IP. Параметр Γ управляет консерватизмом: Γ = 0 дает детерминированный случай, а Γ = количество неопределенных параметров дает наихудший случай (полная защита). Этот подход был применен к проектированию сети цепочки поставок, контролю запасов и местоположению объекта.

Бендеры разложение и вырезание методов самолета

Масштабные надежные модели IP часто превышают память и временные рамки при решении в виде монолитных моделей. Разложение Бендеров разделяет проблему на главную задачу (содержащую целочисленные переменные) и набор подзадач (линейных или целых), которые представляют операционные решения при каждом сценарии или реализации неопределенности. Основная проблема решается итеративно, и вырезы из подзадач добавляются для уточнения решения. Этот метод может обрабатывать проблемы с тысячами сценариев. Методы резки плоскостей, такие как вырезы Гомори или вырезы лифта и проекта, также используются в рамках разветвления и выреза, чтобы затянуть релаксацию линейного программирования, ускоряя конвергенцию.

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

Случайные ограничения и их сильные контрагенты

Иногда достаточно удовлетворить ограничения с высокой вероятностью (например, 95%), а не для всех сценариев. Сдержанное на случай программирование использует вероятностные ограничения. При нормальных предположениях распределения они могут быть переформулированы как детерминированные выпуклые ограничения с использованием обратных кумулятивных функций распределения. Для моделей IP это приводит к коническим или конусным ограничениям второго порядка, которые могут быть решены с помощью современных решателей. Альтернативно, основанные на сценарии приближения (средняя аппроксимация выборки) преобразуют случайные ограничения в большое количество детерминированных ограничений, которые могут быть решены с использованием методов снижения сценария.

Приложения и тематические исследования: влияние на реальный мир

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

Проектирование устойчивых распределительных сетей

Многонациональный ритейлер с операциями в более чем 50 странах сталкивался с частыми перебоями в поставках из-за закрытия границ и задержек в портах. Используя двухступенчатую стохастическую модель IP, компания перепроектировала свою складскую сеть, чтобы включить гибкость: некоторые распределительные центры были спроектированы с дополнительной мощностью для обслуживания нескольких регионов, а запасы были предварительно размещены в стратегических местах. Модель рассмотрела 1000 сценариев спроса, полученных из исторических продаж и макроэкономических показателей. Результатом стала сеть, которая сократила средние задержки поставок на 30% во время кризисов, одновременно увеличив общие затраты всего на 6% по сравнению с бережливым базовым уровнем.

Внешняя ссылка: Пример применения стохастического программирования к местоположению объекта в условиях неопределенности см. в статье в Operations Research.

Оптимизация инвентаря с надежностью

Поставщик автомобильных запчастей нуждался в управлении запасами для тысяч SKU с очень изменчивым спросом, особенно для новых моделей транспортных средств. Была разработана надежная модель линейного программирования с смешанным целым числом, которая рассматривала уровни запасов безопасности как целочисленные переменные (поскольку детали поступают в упаковках). Используя набор бюджетной неопределенности, модель установила целевые показатели запасов, которые защищали от 80% колебаний спроса, не требуя экспоненциального запаса безопасности. Реализация привела к сокращению запасов на 20% при сохранении тех же общих инвестиций в запасы.

Планирование местоположения объекта с учетом сбоев

Во время пандемии COVID-19 фармацевтическая компания осознала, что ее предложение из одного источника для ключевых активных ингредиентов является уязвимостью. Была построена надежная модель IP для выбора набора резервных поставщиков и уровней запасов безопасности, учитывая сценарии, в которых каждый поставщик может быть недоступен в течение нескольких месяцев. Модель включала бинарные решения для контрактов поставщиков и целые решения для количества заказов. Оптимальное решение рекомендовало двух резервных поставщиков, каждый из которых расположен на другом континенте, и увеличение уровня запасов на 35% для критических лекарств. Увеличение стоимости было оправдано стоимостью предотвращения полной остановки производства.

Маршрутизация транспорта с переменным временем в пути

Компания по распределению продуктов питания столкнулась с непредсказуемым движением и задержками погоды. Надежная модель целочисленного программирования для маршрутизации транспортных средств, назначенных грузовиков и секвенированных поставок, обеспечивая при этом, что окна времени доставки были выполнены, даже если время в пути увеличилось до 20% на определенных дугах. Модель использовала надежный аналог ограничений временных окон, в результате чего маршруты были длиннее в среднем, но имели гораздо более высокие показатели своевременной доставки. Компания сообщила о 15% улучшении показателей удовлетворенности клиентов и 10% сокращении аварийных поставок.

Вычислительные задачи и практическая реализация

В то время как надежное целое число программирования предлагает значительные преимущества, оно также представляет вычислительные препятствия. Добавление сценариев или надежных ограничений может значительно увеличить размер проблемы. Например, сеть со 100 возможными местоположениями объекта, 1000 клиентов и 500 сценариев может генерировать модель с миллионами ограничений и переменных. Для того, чтобы сделать такие модели разрешимыми, практикующие используют комбинацию методов:

  • Снижение сценариев: Использование кластеризации (например, k-средств) или оптимальных алгоритмов сокращения для сохранения только репрезентативного подмножества сценариев.
  • Разложение: Как обсуждалось, разложение Бендеров или Данцига-Вольфа разбивает проблему на управляемые части.
  • Эвристика: Для очень больших проблем матеуристические подходы (например, поиск большого района в сочетании с подзадачами IP) обеспечивают почти оптимальные решения быстро.
  • Параллельные вычисления: Многие решатели теперь используют несколько ядер и распределенные вычисления для решения нескольких подзадач параллельно.

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

Внешняя ссылка: Обзор вычислительных инструментов для надежной оптимизации см. документацию Gurobi по надежной оптимизации .

Будущие направления: интеграция машинного обучения и расширенной аналитики

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

Машинное обучение для прогнозирования неопределенности

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

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

Оптимизация в реальном времени и цифровые двойники

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

Внешняя ссылка: Обсуждение цифровых двойников в управлении цепочками поставок см. в статье McKinsey.

Вывод: создание устойчивых цепочек поставок с надежным IP

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

Ключевыми шагами к принятию являются: (1) выявление дискретных решений, которые наиболее уязвимы для неопределенности; (2) характеристика неопределенности с использованием исторических данных и экспертного суждения; (3) выбор соответствующего подхода к надежности (наихудший случай, бюджетный, стохастический), который согласуется с толерантностью к риску организации; (4) реализация модели с использованием разложения, если это необходимо; и (5) проверка с историческими или смоделированными сбоями. По мере того, как машинное обучение и данные в реальном времени становятся более интегрированными, надежное целое программирование станет еще более мощным, позволяя цепочкам поставок, которые не только устойчивы, но и действительно адаптивны.

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