料理来るの遅いなぁ――数理最適化で飲食店のビジネス課題「調理遅れ」を解決できるのか：リクルート事例で分かる数理最適化入門（2）

リクルートにおける数理最適化の応用事例を通じて、数理最適化とは何か、どのようにビジネスに応用できるのかを紹介する連載。今回は、飲食店の最重要課題の一つ、「調理遅れ」を数理最適化で解決する際の考え方やポイントなどについて解説する。

[須藤遼介，リクルート]

　本連載「リクルート事例で分かる数理最適化入門」ではリクルートでの数理最適化の応用事例の紹介を通して、数理最適化がどのようにビジネスに応用できるのかを紹介します。連載初回の前回は、数理最適化の概要、リクルートにおける4つの応用事例、実問題適用への手順、機械学習との違い、使い分け方などを解説しました。

　連載第2回の本稿では、数理「最適化のビジネス応用事例の一つとして、リクルートの製品「Airレジオーダー」の「キッチンモニター」で利用されている調理順並べ替えによる提供遅れ防止機能を紹介します。

　なお記載している内容は公開可能な範囲で簡略化しており、一部ロジックは現実のAirレジオーダーと異なる点があることをご了承ください。

Airレジオーダーのキッチンモニターとは

　Airレジオーダーは弊社リクルートで提供している、飲食店の煩雑になりがちな注文を一元管理し、最適なタイミングでの調理、提供をサポートするオーダーシステムです。中でもキッチンモニターは、料理の注文をキッチンのiPadで表示、管理する機能で、セルフオーダー、ハンディー、「Airレジ」など複数の経路での注文に対応しています。

• セルフオーダー：お客さま自身がスマホのWebブラウザから入力する注文
• ハンディー：ホールスタッフなどが、お客さまの注文を受けて、iOS端末で使えるハンディーで入力する注文
• Airレジ：レジで先に注文と会計をする場合に、Airレジで行われる注文

キッチンモニター公式サイトから引用

　キッチンモニターを利用するメリットは、「注文の管理が容易になる」点だけでなく、「過去の注文／調理状況をデータとして保存、管理できる」点もあります。これらの保存されたデータを分析することで、紙での注文管理ではできなかった業務支援の可能性が広がります。

　ここからは、具体的な案件内容を紹介します。

ビジネス課題の理解

調理遅れとは

　皆さんも、飲食店で料理を注文した際に「来るの遅いなぁ」みたいに思った瞬間が一度はあるのではないでしょうか。

　調理業務が遅れてしまい、お客さまが期待した時間より、提供が遅れてしまっている状態を料理の「調理遅れ」とわれわれは呼んでいます。調理遅れは飲食店の顧客の満足度を大きく下げる要因です。飲食店のクレーム分析でも、調理遅れはクレーム要因のトップとしてたびたび挙げられており、飲食店の最重要課題の一つです。そこで、われわれはキッチンモニターを利用して調理遅れを削減する機能の実装を検討しました。

頼んだはずのだし巻きたまごが届かない人の図（吹き出しは筆者の想像）（「https://unsplash.com/photos/Jn1csk3lWDA」から画像を引用）

調理所要時間は簡単には変えられない

　調理遅れを削減する方法として、最も直接的なのは「調理単体にかかる時間（＝調理所要時間）」を短くすることが考えられます。

　大手チェーン店などでは、調理工程、仕込み、キッチンのレイアウト、機材の改善や、そもそものメニューの変更などによって調理所要時間を改善しています。しかし、一般の店舗でここまでの効率化は難しく、現在のキッチンモニター単体でもここまでのサポートは困難です。そのため、調理所要時間を変えずに調理遅れを削減することを検討する必要があります。

調理にかかる合計時間はそう簡単に短くできない

調理順の最適化による調理遅れの削減

　調理所要時間は変えずに、調理遅れを削減することは可能でしょうか？

　われわれが注目をしたのは「料理ごとにお客さまに調理が遅れていると見なされる期限（＝調理期限）が異なっている」点でした。例えば、おつまみや前菜といった料理は注文後すぐに届いてほしい半面、鍋やデザートなどは注文後すぐに届かなくてよいケースがほとんどです。

　そこで調理遅れの削減を「調理にかかる時間の総和を短くする」問題ではなく、「調理遅れ時間の総和が最小化されるような調理順を求める」問題とし、これを最適化問題として解くことにしました。

※なお現実には調理遅れを単純に削減すること以外にも調理順には考慮ポイントがありますが、ここでは言及しません。

調理所要時間を短くするのではなく、調理の順列を求める問題として解くことにした

問題定義

問題の性質の把握と類似問題の検討

　今回解く問題は「調理遅れ時間の総和が最小化されるような調理順を求める」ことです。これは、どのような調理順なのでしょうか？

　遅れ時間を減らす方法として単純に考えられるのは、「期限が近い順に調理をする方法」です。一見、これは調理遅れを減らせそうですが、「調理遅れの総和を最小化」という観点では最適な方策ではありません。下図は調理期限が近い順に調理を行った場合と、最適化問題を解いた場合の調理順を比較したものです。

　2つの調理順を見比べると、一部調理順を入れ替えることで、調理遅れを縮小／回避できており、その結果遅れ時間の総和が減らせていることが分かります。

　このような調理順は、人間がぱっと計算するのが困難です。しかし数理最適化を用いれば、注文状況を入力として最適化問題を解くことで機械的に最適な調理順を計算できます。

　ただ、数理モデルの構築に慣れておらず、現実の問題をどのように数式に表現したらいいか分からない場合もあるのではないでしょうか。そういう場合は類似の問題を探すことが数理モデルの構築を手助けします。

　例えば今回の問題は実は「スケジューリング問題」という問題の一種であり、特に同時調理可能な注文数が1つの場合は「1機械スケジューリング問題」という数理最適化の教科書に載っている問題の一種と考えられます。これは古くから工場の工程の最適化などをお題に研究されていた分野です。よくよく考えてみると、「注文」→「生産計画された部品」、「機械」→「調理師」、「部品の納期」→「調理期限」と考えると、分野は違えど、解いている問題は同じように考えられ、同じロジックで調理順の問題についても解くことが可能です。

工場の生産計画とレストランの調理順決めは問題の性質が似ている

　このように、最適化問題を現実の問題に適用する場合、既に数理最適化が活躍している分野の典型的な問題を参考にすることが有効です。そのため、「どのような問題があって、どのように解かれているのか」という典型例を多く把握することは数理最適化のビジネス応用に大いに役立ちます。久保幹雄先生の「Python言語による実務で使える100+の最適化問題」のように最適化問題の典型例を紹介しているサイトも存在します。

アルゴリズムによる求解

　数理モデルを構築できた後はアルゴリズムによって求解します。ここでは、数理最適化ソルバーを用いる方法を紹介します。

数理最適化ソルバー

　数理最適化ソルバーは、最適化問題を解いてくれるソフトウェアです。今回も定式化した式とデータを数理最適化ソルバーに入力することで、最適解を得ることができます。数理最適化ソルバーの多くは幅広い問題を解けますが、各問題に特化したアルゴリズムよりは求解性能は劣ります。しかし、最適化アルゴリズムを構築せずに解を得られるので、数理最適化ソルバーをうまく利用することでシステム全体の開発効率を向上できます。ソルバーには有料のものから無料のものまで存在します（一般に有料のものの方が高速）。

インタフェース

　ソルバーはそれ単体でも利用できますが、Pythonなどからソルバーを利用できるインタフェースがサードパーティーから提供されていることがあります。

　数理最適化をシステムに組み込む場合は、次のような最適化問題を解く以外の処理が必要となります。

• ソルバーに与えるデータの取得
• 得られた解によってアプリケーションの挙動を変更する

　そのようなケースではPythonなどから使えるインタフェースを介したソルバーによって、他のプログラムとシームレスにソルバーの機能を利用できるので、実装の面で非常に便利です。

　インタフェースは多くの場合、複数のソルバーに対応しているので、ソルバーの切り替えなども容易に可能となるメリットもあります。

　下図はPythonインタフェースとして最も有名なツールの一つ「PuLP」を利用したモデリングのコード例です。PuLPはデフォルトでは「Cbc（COIN-OR branch-and-cut）」というソルバーを利用します。Pythonに慣れている方ならコードを見るだけでなんとなくどのような問題を解いているのか想像がつくのではないでしょうか？

　PuLPの利用法については『Pythonではじめる数理最適化』（オーム社）という本がケーススタディーも交えて解説してくれているので非常にお薦めです。筆者はGoogleが提供しているインタフェース「OR-Tools」を利用することも多いです。

PuLP（左）とOR-Tools（右）で同じ問題を解いた例

1機械スケジューリング問題を解くプログラムの例

　スケジューリング問題を解いた例を紹介します。今回はダミーデータとして、以下のような注文データを用意しました。最適化に使ったプログラムはこちらのリンクに掲載してあります。

　このデータを基に、注文を「調理期限が近い順に調理した場合」と「最適化によって得られた調理順で調理した場合」を比較すると、約27％も調理遅れ時間を削減できています。

最適化によって期限の近い順に調理を行うより遅れ時間の総和を減らせる調理順が見つかる

　一度数理最適化ソルバーを用いたプログラムを得られれば、新しいデータが来ても毎回最適化された並び順を計算できます。そのため、この調理順にのっとった表示順でiPadに注文を表示することで、調理の支援を期待できます。

キッチンモニター公式サイトから引用

　なお、リンク先にはソルバーとしてCbcを利用したもの以外のコードも用意しています。特にCbcだと注文数が10個程度になると計算に数十秒かかります。より短い時間で解を得る必要があれば、改めて専用の最適化アルゴリズムを開発するか、商用のソルバーを検討することになります。

最適化問題の入力データの推定

　ここまで最適化について説明してきましたが、実は重要な項目の説明が1つ抜けています。そもそも最適化の入力データ「調理所要時間」「調理期限」はデータとして取得可能なのでしょうか？

　結論からいうと、調理所要時間や調理期限は直接、計測できません。そこで、われわれは過去に取得したデータと機械学習や統計モデルを利用した手法を用いて、これらの値を推定しています。

　一見、入力値を取得できないために、最適化が困難に見えるケースでも、その他の手法を併用することで最適化問題を構築できるようになるケースがあります。特に機械学習はその予測の精度や手軽さから、リクルートの数理最適化案件でも非常に強力なツールの一種として利用されています。

数理最適化に用いる入力データの一部は統計モデル、機械学習などで予測する

分析、検証

　ここまでの過程で、いろいろと仮定した中での最適解は得られているはずです。しかし今回組んだ最適化問題上では最適値を算出できていたとしても、その算出結果を用いてビジネス目標を達成できるかどうかは全くの別問題なのです。考慮していなかった制約条件の欠落や、目的関数の設計のミスといった要因で本来得たかったビジネス成果を得られないケースがあります。

　例えば「遅れ時間の総和を最小化」した結果、「最大の遅れ時間」が増えてしまうようなケースが発生し、その結果としてひどい顧客体験を提供してしまうかもしれません。また今回の調理順アルゴリズムでは並行調理が考慮されていないので、遅れが減ったのはいいが、一緒に届いてほしい注文がバラバラに届いて顧客体験を損ねてしまう可能性もあります。

　最初からクライアントへのヒアリングなどを重ねて、より詳細にモデルを設計すればこのような問題は回避できるのでしょうか？　ビジネス目標を達成できるような問題を一度で定義することは困難なのが現実です。そこで、一度モデルを作って終わりではなく、検証、課題分析、改善の繰り返しが、クライアントに喜んでもらえるシステムの開発に必要になります。

　この案件では、協力していただける店舗でのテストやヒアリングなどを繰り返すことで役に立つといえるレベルのロジックを開発できました。この改善、検証のイテレーションをいかにうまく回すかが、数理最適化のビジネス応用では最も大事なポイントです。

求解して終わりではなく分析、検証、改善の繰り返しが必要

終わりに

　以上、リクルートでの数理最適化案件の実例として、Airレジオーダーのキッチンモニターにおける調理順最適化案件を紹介しました。本稿を読むことで、「数理最適化案件ってこういう感じなのか」といったイメージを持っていただけるとうれしいです。

　次回以降はまた別のメンバーが、違うドメインでの数理最適化の面白い実例を紹介するので引き続き連載の購読をよろしくお願いします。数理最適化にかかわらずリクルートのデータを用いた事例に興味を持った方は、データ組織のテックブログもご覧ください。

筆者紹介

須藤遼介

株式会社リクルート データエンジニアリングユニット データエンジニアリング部 旅行・飲食・ビューティー・ＳａａＳデータエンジニアリンググループ所属

自動車メーカーで自動運転のソフトウェア開発に携わった後、2019年にリクルートに中途入社。以後、機械学習エンジニアとして、販促やSaaS領域のデータ活用全般を担当。