Целое программирование для управления запасами и эффективности выполнения заказов

Менеджеры по производству, логистике и розничной торговле сталкиваются с ежедневными решениями, которые непосредственно влияют как на рентабельность, так и на уровень обслуживания. Сколько единиц каждого продукта следует заказывать? Какие заказы клиентов должны быть упакованы первыми? Какой маршрут доставки дает самую низкую стоимость без нарушения часов работы водителя? Эти вопросы имеют общую математическую структуру: они включают дискретный выбор, который не может быть представлен фракциями. Флот грузовиков не может быть 3,7 транспортных средств; сборочная линия не может работать 2,4 партии. Именно здесь становится необходимым целое программирование.

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

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

От линейного программирования к целочисленному программированию

Линейное программирование решает задачи, где все переменные могут принимать любое реальное значение. Например, смешивание бензина может предложить использование 1,5 баррелей сырой А и 2,3 баррелей сырой В - осуществимое и оптимальное решение. Многие логистические решения, однако, не допускают таких дробных результатов. Склад не может заказать 0,6 контейнера, а производственная ячейка не может обрабатывать 2,7 рабочих мест одновременно. Целое программирование исправляет это, требуя, чтобы определенные переменные были целыми. Когда только некоторые переменные являются целыми, модель представляет собой смешанную целочисленную линейную программу (MILP). Когда все переменные являются целыми, это чистая целочисленная линейная программа (ILP).

Математическая формула

Целая программа выражается как:

Минимизируйте c^Tx
, подлежащее Ax ≤ b
x ≥ 0
x ∈ Zⁿ_i ∈ Z для подмножества

Здесь c — вектор затрат, A — матрица ограничений, b — вектор ресурсов, а x — переменные целочисленного решения. Для двоичных задач (0—1) переменные дополнительно ограничены {0,1}. Эта простая структура скрывает огромную сложность: целочисленные программы в целом NP-тверды, что означает, что для больших экземпляров могут потребоваться сложные алгоритмы и коммерческие решатели.

Почему целочисленные переменные имеют значение в операциях

В инвентаризации и исполнении целочисленные переменные, естественно, представляют собой дискретные предметы, заказы, транспортные средства, работников и объекты. Без целочисленных ограничений линейное программирование может заказать 23,4 единицы медленно движущегося SKU, что приводит к дробному запасу безопасности - неосуществимый результат на практике.

Интегрированное программирование в управлении запасами

Управление запасами уравновешивает затраты на хранение запасов с рисками запаса. Традиционные модели, такие как количество экономического порядка (EOQ), предполагают постоянное пополнение и детерминированный спрос. Реальные системы запасов сталкиваются с дискретными заказами, возможностью совместного использования нескольких продуктов, минимальными количествами поставщиков и ограничениями серийного производства. Целое программирование позволяет точно моделировать эти сложности.

Классический размер лота с целочисленными переменными

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

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

Эти модели теперь являются стандартными в современных системах планирования (APS) от таких поставщиков, как SAP, Oracle и Blue Yonder.

Многоуровневая оптимизация инвентаря

Цепочки поставок часто охватывают несколько уровней - поставщиков, центральные склады, распределительные центры и розничные магазины. Целое программирование координирует решения о пополнении по эшелонам. Например, ритейлер может консолидировать заказы из сотен магазинов в количествах грузовых автомобилей. Целые переменные захватывают количество грузовиков, выбор точек консолидации и назначение магазинов для поставок. Исследование Центра транспорта и логистических исследований MIT; Логистика обнаружила, что многоэшелон MILP снизил общие затраты на инвентаризацию на 12-18% в сетях потребительских товаров.

Ограничения на запас и уровень обслуживания

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

Целое программирование для эффективности выполнения заказа

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

Складской заказ Batching and Picking

В типичном распределительном центре сборщики путешествуют через проходы, собирая предметы для нескольких заказов. Заказы групп задач по пакетам так, что один сборщик может получить все предметы в одной поездке. Цели заключаются в том, чтобы минимизировать общее расстояние поездки и сбалансировать рабочую нагрузку между сборщиками. Это вариант проблемы маршрутизации транспортного средства (VRP) с дополнительными ограничениями: пропускная способность выборщика (например, максимальное количество заказов на партию) и временные окна для завершения. В формулах программирования целых чисел используются бинарные переменные для назначения заказов партиям и для секвенирования в каждой партии. Решения, такие как IBM ILOG CPLEX и Gurobi, могут обрабатывать экземпляры с сотнями заказов, и многие склады сообщают о сокращении времени в пути на 20-40% после реализации оптимизированной партии.

Расписание маршрутизации и доставки транспортных средств

Проблема маршрутизации транспортных средств (VRP) является классическим приложением для целочисленного программирования. Парк транспортных средств должен обслуживать набор клиентов из депо, сводя к минимуму общее расстояние или стоимость поездки при соблюдении пропускной способности транспортного средства, временных окон и часов водителя. Целые переменные представляют последовательность остановок, назначение маршрутов для транспортных средств и количество используемых транспортных средств. Расширения реального мира - такие как разнородные парки, перерывы для водителей и динамические поступления заказов - естественно выражаются как MILP. Такие компании, как UPS и Domino's Pizza используют целочисленное программирование для планирования десятков тысяч маршрутов ежедневно. Согласно опросу 2023 года, принятие оптимизации маршрута увеличило чистую прибыль на 5-10% в операциях доставки последней мили.

Распределение заказов через центры исполнения

Розничные торговцы электронной коммерции с несколькими складами должны решить, какой центр исполнения (FC) будет отправлять каждый пункт линии, чтобы минимизировать общую стоимость (отгрузка плюс обработка). Проблема распределения - это проблема транспортировки с целыми потоками. Когда товары уже упакованы в случаях, количество отгруженных случаев должно быть целым числом. Добавление ограничений доступности запасов и сроков доставки превращает распределение в MILP. Система управления заказами Amazon использует целое программирование для назначения заказов на ФК в миллисекундах, позволяя ей выполнять свои обязательства по доставке в течение двух дней и в тот же день, сохраняя при этом низкие затраты на доставку.

Алгоритмы и программное обеспечение для решения целочисленных программ

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

Ветвь-и-связь

Стандартный алгоритм MILP является разветвленным. Он начинается с расслабления целочисленных ограничений и решения релаксации LP. Если решение содержит дробные переменные, алгоритм создает дочерние узлы путем разветвления на одну дробную переменную (например, x ≤ 5 или x ≥ 6). Каждый узел представляет собой новую проблему LP. Алгоритм обрезает узлы, которые не могут дать лучшего решения, чем текущее лучшее целочисленное решение. Для больших проблем ветвление само по себе слишком медленное, поэтому современные решатели добавляют плоскости разреза - ограничения, которые отсекают дробные решения без удаления целых возможных точек. Эта комбинация называется разветвлением и разрезом.

Коммерческие и открытые источники

Программное обеспечение для целочисленного программирования производственного класса включает в себя:

IBM ILOG CPLEX — один из самых быстрых и надежных решателей, широко используемый в цепочке поставок, финансах и производстве. IBM CPLEX Optimizer
Gurobi Optimizer — известен своим высокопроизводительным MILP-решателем и отличной поддержкой приложений инвентаризации и маршрутизации. Gurobi Inventory Management Resources
Google OR-Tools — бесплатная библиотека с открытым исходным кодом, которая включает в себя целые программные решатели (через Coin-OR или CPLEX) и специализированные алгоритмы маршрутизации и планирования. (см. OR-Tools Documentation)
SCIP (Solving Constraint Integer Programs) — фреймворк с открытым исходным кодом, разработанный в Институте Цузе в Берлине. Он предлагает множество плоскостей резки и первичную эвристику.

Выбор правильного решателя зависит от размера проблемы, требований к скорости и бюджета. Для большинства корпоративных проблем с запасами и выполнением CPLEX или Gurobi являются отраслевыми стандартами.

Реальные мировые тематические исследования

Распределение автомобильных запчастей

Крупный дистрибьютор автомобильных запчастей пополнил 20 000 SKU на пяти складах. Он использовал многоэтажки MILP для определения количества заказов и уровней запасов безопасности, учитывая целые размеры лотов (паллеты и чехлы). Модель включала ограничения складской мощности, сроки поставки и сезонность спроса. После внедрения общий объем запасов сократился на 15%, а уровень обслуживания вырос с 92% до 97%. Ежегодная экономия средств превысила 2 миллиона долларов.

Модный ритейлер Заказ выполнен

Европейский модный ритейлер столкнулся с высокими расходами на доставку и поздними поставками в пиковый сезон. Он развернул целочисленное программирование для распределения онлайн-заказов в четыре центра исполнения на основе наличия запасов, зон доставки и емкости. Модель работала каждый час, назначая заказы на самый дешевый FC, который все еще может соответствовать дате обещания. В течение трех месяцев средняя стоимость доставки на заказ упала на 22%, а скорость доставки вовремя выросла с 86% до 95%.

Доставка продуктов питания Home Delivery Routing

Большая продуктовая сеть, работающая в плотных городских районах, использовала MILP для планирования ежедневных маршрутов доставки для 200 фургонов. Модель учитывала временные окна (двухчасовые слоты), пропускную способность транспортного средства (количество тотов), ограничения сдвига водителя и модели пробок. Эффективно распределяя заказы и разумно останавливая последовательность, компания сократила количество маршрутов на 8% и общие километры на 12%, сохраняя при этом производительность доставки в режиме времени на 98%.

Проблемы и будущие направления

Масштабируемость и вычислительное время

Целые задачи программирования растут комбинаторно. Модель инвентаризации с 500 SKU, 52 неделями и многоуровневой структурой может превышать 100 000 бинарных переменных. Даже лучшим решателям могут потребоваться минуты или часы, чтобы доказать оптимальность. Практикующие часто полагаются на ограниченные по времени эвристические решения: принимают лучшее целое решение, найденное в рамках бюджета времени (например, 300 секунд). Достижения в параллельных вычислениях и облачных решателях раздвигают границы: Инструменты Google OR теперь могут решать проблемы маршрутизации с тысячами клиентов за секунды.

Качество данных и интеграция

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

Оптимизация в реальном времени

Классическое целочисленное программирование предполагает статические, известные входы. Электронная коммерция и доставка в тот же день требуют быстрой переоптимизации по мере поступления заказов. Это привело к разработке MILP с катящимся горизонтом, переоптимизированной каждые несколько минут, а также гибридных моделей, которые сочетают целочисленное программирование с обучением подкреплению. Например, модель динамического выбора может пересдавать заказы каждые 30 минут на основе последних 200 заказов. Исследователи из Стэнфордского университета недавно продемонстрировали структуру, которая решает VRP с 500 динамическими заказами менее чем за две секунды с использованием изученных теплых стартов и небольшого решателя MILP.

Интеграция с искусственным интеллектом

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

Заключение

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

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