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

Afresh создает современные технологии цепочки поставок для решения проблем, связанных со свежими продуктами питания. Ежегодно треть продуктов питания в мире выбрасывается в отходы. В Соединенных Штатах 40 процентов пищевых отходов происходит на уровне розничной торговли и потребления. Большая часть этих отходов происходит в отделах свежих продуктов в продуктовых магазинах. Afresh работает над устранением этих потерь.

Проблема

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

Почему хороших прогнозов недостаточно

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

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

Итак, вы создаете прогнозиста, который предсказывает спрос на каждый элемент, учитывая:

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

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

Удобно владея волшебством машинного обучения, вы развертываете модель и заказываете именно ее рекомендации.

Ой! Через день у вас заканчивается товар и вы теряете ценные продажи. Если вы всегда заказываете оценку средних продаж, которая сводится к минимуму убытков L1, это означает, что вы испытываете нехватку запасов почти в 50% случаев.

Что еще хуже, вы не представляете, как справиться со случаями, когда вы продаете меньше, чем заказываете. Коробка хлопьев семидневной давности такая же, как сегодня? Может быть. А как насчет 7-дневной упаковки черники? Предупреждение о спойлере: это не так.

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

Оптимальное решение для заказа круп

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

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

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

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

Как это работает на практике? Мы найдем оптимальный порядок и стоимость состояния в момент времени t = N-1, а затем найдем оптимальный порядок в момент времени t = N-2, учитывая уже полученные затраты в N-1. Мы рекурсивно вычислим все эти значения и в конечном итоге получим оптимальную политику управления на горизонте.

Давайте определим все это на Python.

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

Затем мы запишем функцию стоимости заказа некоторой суммы order и завершения в состоянии inventory.

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

def get_cost(inventory, order, order_cost,
             over_order_cost, under_order_cost):
    over_order_cost = max(inventory, 0) * over_order_cost
    under_order_cost = -min(inventory, 0) * under_order_cost
    return over_order_cost + under_order_cost + order * order_cost
def act_and_get_cost(inventory, order, demand):
    # possibly negative  
    resulting_inventory = inventory + order - demand
    cost = get_cost(inventory, order)
    next_inventory = max(resulting_inventory, 0)
    return next_inventory, cost

Теперь мы определим наш решатель. Мы переберем возможные заказы в каждом состоянии и найдем тот с наименьшими ожидаемыми затратами, интегрировав вероятностный спрос. Самая низкая стоимость назначается как значение состояния, а лучший порядок сохраняется в качестве нашей политики для этого состояния. Мы будем рекурсивно определять эти состояния, пока не достигнем t = 0. Результат нашего решателя будет:

path_array: [time, inventory_count] → оптимальный порядок, если вы находитесь в этом состоянии

cost_array: [время, inventory_count] → стоимость пребывания в этом состоянии

Давайте запустим наш решатель для случайного распределения спроса.

# 10 days of forecasts, 15 possible values
forecasts = np.random.random((10, 15))
# Normalize to make probabilities:
forecasts = forecasts / np.expand_dims(forecasts.sum(axis=1), 1)
# Solve
solver = NonPerishableDPSolver(2, 6, 0)
explain_array, path_array, cost_array = solver.dp_solve(forecasts)

Мы можем проанализировать решения нашей политики в момент времени T = 0:

О чем говорят нам эти сюжеты? Для созданного нами набора вероятностей спроса существует оптимальное количество запасов - пять единиц, - которые мы должны иметь под рукой в ​​момент времени T = 0 после прибытия утреннего груза. Если наш утренний инвентарь превышает пять единиц, мы не должны ничего заказывать. Если у нас меньше пяти единиц, мы должны заказывать до пяти единиц и не более того. Поскольку заказ крупы стоит денег, ожидаемая стоимость штата с уже имеющимися запасами ниже.

Мы экспериментально заново открыли классический результат. Оптимальный объем заказа в момент времени k для нашей задачи принимает следующий вид при разумном выборе функции затрат:

Как насчет вычислительной сложности?

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

Мы могли бы узнать намного больше об оптимальном заказе хлопьев, но давайте на этом остановимся. У нас есть еще один товар на заказ.

Оптимальное решение для черники

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

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

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

Если мы предположим продажи в порядке очереди (FIFO) (самые старые черники продаются первыми), наш переход между действием / состоянием можно описать следующими тремя функциями:

def get_sales(state: np.array, total_sales: int):
    """Given total_sales, allocate them in a FIFO manner"""
    for i in range(max_age, 0):
        sale = min(state[i], total_sales)
        total_sales -= sale
        state[i] = state[i] - sale
    return total_sales # lost sales
def transition(state):
    """Every item of age k ages into k+1, oldest items go to
     waste"""
    last = 0
    tmp = 0
    for i in range(max_age):
        tmp = state[i]
        state[i] = last
        last = tmp
    return last # waste
def act(state, shipment, sales):
    "Given a shipment and sales, transform the state"""
    state[0] = shipment
    lost_sales = get_sales(state)
    waste = transition(state)

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

Анализируем черничную политику

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

Ниже мы отображаем государственную стоимость перевозки двух единиц черники разного возраста. Мы видим, что более старые акции имеют гораздо более высокую ожидаемую государственную стоимость, чем более молодые. Две двухдневные черники в этом сценарии в 2,5 раза менее ценны, чем две свежие черники, при T = 0 и сформированном распределении спроса.

Здесь мы строим график зависимости количества запасов на складе от процента «старых предметов» (старше трех дней) от ожидаемой стоимости состояния. Функция ценности далеко не так чиста, как одномерная задача с зерном. На это очень явно влияет относительный возраст нашего инвентаря.

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

Что, если бы мы заказали чернику, как хлопья?

Теперь, когда у нас есть две политики - одна не учитывает срок годности, а другая учитывает - мы можем сравнить их эффективность в симуляторе.

  • Мы установили срок годности черники 3, стоимость единицы 1,75 и цену 2.
  • Политика в отношении зерновых планирует все свои действия, как и раньше, без учета срока хранения.
  • Политика Blueberry планирует свои заказы с известным сроком годности. Он имеет те же order_cost и under_order_cost, что и политика в отношении зерновых.

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

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

  • В соответствии с нашей политикой в ​​отношении черники теряется на 30% меньше черники, чем в отношении зерновых.
  • Учитывая цену и удельную стоимость черники, политика учета срока годности имеет стоимость почти на 8% ниже, а средняя стоимость по сравнению с симуляциями составляет 45,591 против 49,246.

Совершенно очевидно, что при заказе черники необходимо учитывать скоропортность.

Контроль складских запасов скоропортящихся продуктов в Afresh

Хотя эти оптимальные политики полезны для понимания формы нашей проблемы, они не совсем подходят для производства.

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

В то время как для зерновых требуется динамическая программа с 150 состояниями, чтобы найти оптимальную политику с T = 10 и U = 15, нам нужно решить динамическую программу 1,7 миллиарда состояний, чтобы найти политику для черники. со сроком хранения шесть дней. Мы также проигнорировали множество факторов (обсуждаемых ниже), которые затрудняют решение этой проблемы с помощью точного динамического программирования.

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

Afresh объединяет идеи из всех этих областей для решения этой сложной проблемы. Мы разработали способы оценки сложных моделей скоропортящейся продукции на основе данных, разработали современные методы вероятностного прогнозирования для оценки спроса на продукцию и создали новые инструменты оптимизации, чтобы собрать все это воедино. Мы проверяем эти модели на крупномасштабном моделировании на протяжении миллионов магазинов-дней. Мы разместили их в сотнях продуктовых магазинов США, где они обеспечивают ежедневное пополнение запасов свежих продуктов.

Реальный мир

Сегодняшние цепочки поставок - это цепочки поставок зерновых. Они не созданы для сложных черник. Это имеет драматические последствия для окружающей среды. В Соединенных Штатах от 30 до 50% всех свежих продуктов выбрасывается в отходы. Сокращение количества этих отходов на 25% позволит сэкономить 83 миллиарда галлонов воды и устранить 10 миллионов тонн выбросов парниковых газов в год.

Afresh был основан для решения этой проблемы. Наша технология работает. Мы уже сократили количество пищевых отходов в основных продуктовых сетях на 25%, и каждое улучшение наших моделей приближает этот показатель к 100%. Это непростая задача - реальный мир намного сложнее, чем магазин черничных хлопьев.

Вот еще несколько проблем, о которых стоит подумать:

  • Мы можем разработать более сложные правила, регулирующие цены в зависимости от возраста товара, который мы продаем, или еженедельно корректировать размер полки в зависимости от того, насколько хорошо товары продаются. Эти политики имеют чрезвычайно сложные стохастические структуры принятия решений.
  • Продуктовые сети разрезают арбузы в чаши для фруктов и кладут манго в коктейли. Эти производные продукты имеют разную маржу и характеристики скоропортящейся продукции - сколько из них мы производим и когда?
  • Мы заботимся о различных показателях в реальном мире и должны решать проблемы оптимизации с более жесткими ограничениями: например, в продуктовых магазинах может потребоваться, чтобы риск того, что бананы закончились, составляет менее одного процента.
  • Прогнозирование спроса - это сложная и требовательная система. Спрос на многие скоропортящиеся товары очень сезонный, очень эластичный и взаимозаменяемый. На спрос может повлиять возраст продуктов на полке (как это повлияет на нашу DP?)
  • Мы не знаем срок хранения всех свежих продуктов. Кроме того, срок хранения не соответствует чистоте - некоторые предметы могут распадаться экспоненциально, некоторые могут погибнуть через определенное количество дней. Многие товары не соответствуют модели продаж FIFO. Нам нужно изучить это поведение на основе данных.
  • Магазины работают с ограничениями по размерам подсобных помещений и грузовиков, которые могут ограничивать наши заказы. Более крупные заказы могут привести к получению скидки от поставщика.

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