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

❖ автор Рёсуке Судо

Долгое время ожидания заказа — может ли математическая оптимизация решить бизнес-проблему задержки приготовления блюд в ресторанах?

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

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

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

Что такое кухонный монитор AirREGI?

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

• Самостоятельный заказ: заказы вводятся клиентами самостоятельно через веб-браузер смартфона.
• Ручной: заказы вводятся персоналом зала или другими сотрудниками с помощью ручного устройства, которое можно использовать с устройствами iOS, после получения заказа клиента.
• AirREGI: заказы, оформленные в AirREGI (клиент выбирает блюда и оплачивает всё на кассе).

Адаптировано с официального сайта кухонного монитора

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

Вот некоторые конкретные детали проекта.

Понимание проблем бизнеса

▍ Что такое задержка приготовления?

Наверняка у вас бывали моменты, когда вы заказывали еду в ресторане и думали: «заказ готовится слишком долго».

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

Схема человека, не получившего свой заказ вовремя (изображение взято отсюда)

▍ Необходимое время приготовления нелегко изменить

Самый прямой способ сократить задержки в приготовлении — это сократить время, необходимое для самого процесса приготовления (т. е. время приготовления).

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

Общее время, затрачиваемое на приготовление пищи, не может быть сокращено так просто

▍ Сокращение задержек за счёт оптимизации порядка приготовления

Можно ли сократить время задержки без изменения времени приготовления?

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

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

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

Проблема была решена как вопрос поиска вариантов приготовления, а не сокращения необходимого времени приготовления

Определение проблемы

▍ Понимание природы проблемы и изучение аналогичных проблем

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

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

Проблема была решена как вопрос поиска вариантов приготовления, а не сокращения необходимого времени приготовления

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

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


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

Например, эта проблема фактически является «проблемой планирования», особенно когда количество заказов, которые могут быть приготовлены одновременно, равно единице, что можно считать типом проблемы, которая в учебниках по математической оптимизации называется «проблемой планирования на одной машине». В этой области уже давно изучаются такие темы, как оптимизация производственных процессов. Если вы хорошо подумаете об этом, то вы можете рассмотреть это как 'заказ' → 'запланированные производственные детали', 'оборудование' → 'готовка' и 'дата поставки деталей' → 'срок приготовления', то решаемую вами проблему можно считать одной и той же, несмотря на то, что разные направления, и для решения проблемы заказа в ресторане можно использовать ту же логику.

Характер проблемы схож с планированием производства на заводе и определением заказа блюд в ресторане

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

Алгоритмическое решение

После построения математической модели её можно решить алгоритмически. В этом разделе представлено использование решателя математической оптимизации.

▍ Решатель математической оптимизации

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

▍ Интерфейсы

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

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

• получение данных для передачи решателю,
• изменение поведения приложения в соответствии с полученным решением.

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

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

На следующей схеме показан пример моделирования кода с помощью одного из самых известных интерфейсов Python, PuLP, который по умолчанию использует решатель под названием Cbc (COIN-OR branch-and-cut). Если вы знакомы с Python, вы, вероятно, можете догадаться, какую проблему вы решаете, просто взглянув на код.

Книга на японском языке «Математическая оптимизация на Python» (オーム社) объясняет, как использовать PuLP, на примерах из практики, и очень рекомендуется к ознакомлению. Автор также часто использует OR-Tools — интерфейс, предоставленный компанией Google.

Пример решения одной и той же задачи с помощью PuLP (слева) и OR-Tools (справа)

▍ Пример программы для решения задачи планирования работы машины

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


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


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

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

Адаптировано с официального сайта кухонного монитора

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

▍ Оценка исходных данных для решения оптимизационной задачи

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

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

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

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

Анализ и проверка

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

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

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

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

Поиск решений не является завершением процесса, скорее необходимо повторение анализа, проверки и совершенствования

Заключение

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