Стохастический дискретный спуск

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

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

Абстрактная аллегория задачи стохастической оптимизации

Обзор технологий

С 2016 года компания Lokad преимущественно оптимизирует цепочки поставок с помощью вероятностных прогнозов. Без вероятностных прогнозов оптимизированные решения неизбежно становятся хрупкими, подверженными даже небольшим колебаниям спроса или сроков поставки. Напротив, решения, оптимизированные с использованием вероятностных прогнозов, являются надежными. Хотя надежные решения можно вычислить с помощью относительно простых «жадных» эвристик, эти эвристики часто не справляются с более сложными ограничениями.

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

Подготовить исторические данные.
Сгенерировать вероятностные прогнозы.
Получить надежные решения.

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

В конечном счете, этапы (1), (2) и (3) выполняются в рамках Envision.

Традиционные решатели и их ограничения

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

Очень немногие решатели обрабатывают стохастический случай. Почти все существующие решения сосредоточены на детерминированном сценарии, где отсутствует неопределенность. К сожалению, нельзя просто «перенастроить» детерминированный решатель для стохастических случаев без введения недопустимого уровня аппроксимации.
Большинство решателей не обладают достаточной масштабируемостью. Задачи цепочек поставок могут достигать крайне больших размеров: один миллион SKU может обернуться десятками миллионов переменных после моделирования для оптимизации. Разделение цепочки поставок лишь для того, чтобы соответствовать возможностям решателя, неприемлемо. Решатель должен изначально обрабатывать десятки миллионов переменных.
Многие решатели не обладают достаточной выразительностью. Целевая функция часто не может считаться линейной, квадратичной или даже выпуклой. Недопустимо искажать задачу под упрощенные математические предположения лишь для того, чтобы удовлетворить ограничениям решателя. Следовательно, решатели должны предлагать высоко выразительные парадигмы программирования.

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

Изнутри

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

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

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

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

Примеры

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

Пополнение запасов в магазинах модной одежды

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

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

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

Ремонт авиационных двигателей

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

Стохастическая оптимизация — в частности, стохастический дискретный спуск — позволяет надежно приоритизировать инвестиции в запчасти, помогая поставщику услуг MRO (технического обслуживания, ремонта и капитального ремонта) минимизировать время ремонта авиационных двигателей. Для каждого приобретаемого элемента ключевым вопросом становится: «С учетом данного бюджета, на сколько дней задержки ремонта я могу избежать?» Таким образом, закупки запчастей стратегически приоритизируются для сокращения времени простоя — что имеет решающее значение, поскольку MRO получают оплату за поставку исправных двигателей, и любая задержка является прямой потерей как для MRO, так и для авиакомпании. Простой жадный подход здесь не работает, так как зависимости между деталями могут вызвать каскадные задержки. Напротив, если MRO решит не хранить определенные запчасти на складе, это может не повлиять на общий график, если эти детали можно будет закупать параллельно, ожидая компонентов с большим сроком поставки. Стохастический дискретный спуск учитывает эти взаимозависимости и возможности параллельных закупок.

Ограниченное многопоставочное снабжение

Рассмотрим пополнение запасов с множественными ограничениями и несколькими вариантами поставок. Поставщики устанавливают MOQ (минимальные объемы заказа), которые могут быть указаны как в единицах (для всего заказа), так и в денежном выражении (для общего заказа). Кроме того, следует стремиться к полным контейнерам для снижения транспортных расходов. Продукты могут поставляться локально — что приводит к более коротким срокам поставки и более низким MOQ, но высоким издержкам за единицу — или от отдаленных поставщиков, которые предлагают более низкие цены за единицу, но связаны с более длительными сроками поставки и более высокими MOQ. Хотя компания может заказывать несколько контейнеров еженедельно, любой конкретный продукт обычно появляется не более чем в одном контейнере в месяц.

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