市場における需要と供給のバランスを取るためのモンテカルロシミュレーションの使用。

 Instacartでは、私たちの目標は食料品の配送に誰もがアクセスできるようにすることです。 過去9ヶ月間、私たちはいくつかの確立された市場から、100以上の市場にまで劇的に成長しました。 このような急速な拡大は、多くの成長の可能性をもたらしますが、私たちの需要に予測不能性が起こる要因となります。 ショッパーにまんべんなく仕事を提供し、すべての顧客に同じ日の配送を提供することは非常に難しい問題となります。

この記事は、急速に成長している分散性の高い市場で需要と供給のバランスを取るためにモンテカルロシミュレーションをどのように活用するかについての記事です。

    2017年1月から2017年9月までのInstacartのサービスロケーションの進展

需要と供給のバランス

需要と供給のバランスをとることは、注文を受けてそれを実行するビジネスに携わるすべての企業にとって非常に重要です。 需要が供給を上回る場合、注文の取消しを決定するシステムがあり、それが、当社が同日の供給を上回る配達を妨げます。 私たちは、ある日に対応できない需要のパーセンテージをロストデリバリーとして定義します。
需要より多くの供給がある場合、ショッパーは空き状態になり、1時間当たりの注文数が少なくなるため収益が低下します。 私たちのショッパーは、プラットフォームで時間を有効に使うことを好みます（待機時間を無くす）。

              Supply < Demand: Lost Deliveries, Supply > Demand: Idleness

                   供給<需要：配達、ロストデリバリー>需要：安らぎ

私たちが毎日同じ需要があれば、私たちは毎日正確に同数のショッパーを雇うことでしょう。 しかし、特に新マーケットでは需要と供給の予測不可能性な要因があり、それがスタッフィングを非常に困難な問題にしています。
あまりにも多くの配送を失うことなく、ショッパーをアイドル（待機）状態にしないために、各時間帯の毎日の各マーケットの適切な数のショッパーに、どのように調整していますか？ 　この問題は何がそんなに難しいのですか？　差異はどこから来ていますか？ 　私たちはこれらの質問にすべて答えますが、まず正式に解決しようとしている問題を定義しましょう。

問題ステートメント

特定のマーケットと特定の日に、どのようにスタッフを雇用しますか：

•各時間のショッパーの数

次のようにします：

•ショッパーのアイドル状態を最小限に抑える
•ロストデリバリーの最小化

この問題の最終的なアウトプットは次のようになります：

これらの数字はStaffing Levelsと呼ばれます。

この問題で難しい点は何ですか？

分散

ラッシュアワー、台風、吹雪、Game of Thronesシーズンファイナル、そして連休にのみ激しい標準的な需要と供給の変化（急変）に対応しなければなりません。 ショッパーの生産性も一致しません。 経験者もすぐにタスクをコンプリートできます。一方、いくつかのアイテム、特に新しいショッパーは、プラットフォームに慣れて立ち上がるときに時間がかかるものもあります。 ショッパーは必要に応じてシフトを取り消す柔軟性も持っているので、私たちの供給に予測不能性が増します。
以下の各コンポーネントには差異があり、スタッフィングの決定に影響します。

制約

問題をさらに複雑にするいくつかの制約があります。 私たちの供給は、各都市の異なる店舗の場所から達成することができます。 店舗は異なる営業時間で営業しています。 私たちのピッキングと配達時間は、店舗や道がどれだけ忙しいかによって異なる場合があります。 パートタイマーのショッパーであれば、どのくらいの期間、私たちと一緒に仕事をすることができるかという制約があります。

私たちは160以上の小売業者とやりとりをしており、小売業者固有のルールに従わなければならないことがよくあります。

目的の統一

また、アイドル状態やロストデリバリーに関連するコストを定量化し、より良い人事決定を行うためにそれらを単一の機能に統一する必要があります。

アイドル状態は人件費の増加につながり、ロストデリバリーは収益の損失につながります。 潜在的なリピート顧客が失われた場合でも、ロストデリバリーは長期間の費用がかかる可能性があります。

ヒューリスティックに基づくスタッフィングの方法

最初は、予測とヒューリスティックベースの方法を組み合わせてこの問題を解決しました。 これらのアプローチの背後にある基本的なアイデアは、適応コース修正に基づいていました。

•前週の人員数を使って、予測をします
•前週のアイドル状態と納品の遅れに基づいて次の週に修正します
•来週の需要予測の変更を調整する

しかし、これらのアプローチでは、しばしば配送が多すぎるか、ショッパーがあまりにも多くアイドル状態になってしまいます。 先週の成果への依存は、局所的な最適値で解決することによって潜在的に誤りのあるフィードバックループを招く可能性があります。 たとえば、より多くのショッパーを集中的に配置されていない店舗よりも多くのショッパーをその店舗の周りにより多くの注文密度で置くことが最適かもしれない。 そのようなニュアンスは、これらのアプローチでは捕らえにくいです。

この複雑さと不確実性をすべて処理するために、我々はモンテカルロシミュレーションを試みることにしました。

シミュレーションベースの最適化

モンテカルロシミュレーション法は、このような問題に対していくつかの利点を提供します。

•先週の結果に依存しない
•複雑なシステムをランダム変数間の相互作用としてモデル化する
•分散をより適切に処理する確率的最適化を実行する

アイデアは、さまざまな需要と供給のさまざまなバリエーションをシミュレートし、すべてのシミュレーション実行でアイドル状態とロストデリバリーコストを最小限に抑える一連のスタッフレベルを解決することです。

各シミュレーションは、私たちがスタッフを募集したいマーケットの将来の日付を表す必要があります。 これは、注文、店舗、ショッパーの場所、注文を実行するのにかかる時間を把握するための予測モデル、および取り消す可能性が高いショッパー数の推定が必要であることです。

注文のシミュレーション

私たちは、まず、将来どのくらい多くの注文が期待されるのかを考えなければなりません。 我々は、毎日の各マーケットに対する需要のためのポイント推定値を生成する需要予測アルゴリズムを有します。 しかし、実際の需要は必ずしも予測と一致するとは限らず、分散する傾向があります。 変動性を考慮に入れて、各シミュレーションで達成する必要のある注文数を決定するために、エラー分布に基づいて需要予測の分布を作成します。

Example of a demand forecast distribution. Mean = Demand Forecast.

需要予測分布の例 平均=需要予測。

この分布から数値をサンプリングしたところ、3100の配達があったとしましょう。 その後、そのマーケットに歴史的に置かれたすべての注文から多数の注文をサンプリングします。

サンフランシスコの一部におけるデマンドの空間的ディストリビューション（実際のデータの上に加えられたノイズ）

何度も何度もやり直していくと、注文数の変動と、スペースと時間のばらつきの両方に対処します。

ショッパーのシミュレーション

すべてのショッパーが同じ働き方をするわけではありません。 遅い人もいれば、早い人もいます。 ガンマ分布とそのサンプルからスピードをモデル化します。 彼らはまた、いつも同じ場所にいるわけではありません。 彼らは自宅の場所と店舗の場所間のどこかでシフトを開始し、シフトの最中に最後の配送場所と最寄りの店舗の場所間のどこにでも置くことができます。 マルコフモデルを用いて、それらの位置の分布をモデル化します。

各シミュレーションの人員配置

注文、ショッパー、および店舗のシミュレーションを開始したら、そのシミュレーションに必要な理想的なスタッフィングを把握できます。

注文、ショッパー、および店舗でブートストラップされたシミュレーションの例。

基本的にはタイムウィンドウ付きのVRP（Vehicle Routing Problem）であるフルフィルメント問題を解決することでこれを行います。 我々は、一貫性を保ちながら計画を現実のものにできるだけ近いものにするために、実際に注文を実行するために実際に使用する同じアルゴリズムをリアルタイムで使用します。

シミュレーションごとにVRPを解く

上記の問題を解決することで、ルートの最適なセットが得られます。ルートのそれぞれには、期限とそれを実行することでかかる時間に基づく開始時刻と終了時刻があります。 これらの最適なルートから、私たちは逆向き解決法で必要なショッパーの数を把握できます。 このアプローチによって、より最適なルートの一部である店舗内のより多くのショッパーに自動的にスタッフを派遣することもできます。

人員配置レベルを生成するために逆向き解決法を使っての例

時間帯別に必要なショッパーの数の例

複数のシミュレーション

すべての変動性を考慮に入れて、各シミュレーションでスタッフィングを繰り返しサンプリングして解決することにより、上記のプロセスを何百回も繰り返します。

すべてのシミュレーションの結果を集計

最終的な人員配置レベルを解決する

最終的には、すべてのコストを最小限に抑えるスタッフングレベルの最終セットを解決する必要があります。 x_h（h：午前8時から午後10時まで、x_hは[0、∞]からの範囲の整数変数です）は時間hに必要なショッパーの数を表しています。 目的はすべてのx_hを解決することです。

x_h（h：8AM〜10PM）は、必要なショッパーの数を決定する整数変数です

この特定のシミュレーションでは、x_hが赤線で表される値を取る場合、1 でマークされた領域では、過剰なコスト（オーバースタッフ）がかかり、したがってアイドル状態のコスト（アンダースタッフ）が発生します。 2でマークされた領域では、私たちは控えめであり、したがってロストデリバリーコストの損失を招きます。すべてのシミュレーション実行でこれらのコストを最小限に抑えることによって、すべてのx_hを解決します。

N：シミュレーション実行数

•h：時間帯

ld_cost：ロストデリバリーコスト

•x_h：非負整数変数
•l_h、i：シミュレーションiで時間hに必要なショッパー人員レベルの最終セット

赤い線は、上記の最適化問題を解いた後のx_hの値を表します。

アーキテクチャ

私たちがこれまでに検討したすべてをまとめると、スタッフ用エンジンのアーキテクチャは次のようになります：

いくつかのシナリオを実行するコアシミュレーションエンジンがあります。 次に、これらのシミュレーションを実行し、最終的な人員レベルのセットを構築するオプティマイザを用意します。

結果

このアプローチのパフォーマンスをテストするために、このアプローチで生成された人員レベルを、プロダクションとトラッキングメトリックの2つの主な目的で使用しました：ロストデリバリーとアイドル状態を、以前のアプローチと比較しました。

ロストデリバリーとアイドル状態の密度プロットの比較

成長を促進するために昔は高いショッパー数を誇ってたマーケットでは、ほぼ同じ量のロストデリバリー率を維持しながら、アイドル状態を大幅に削減することができました。 これは、ショッパーを稼働させ、収入を上げる可能性を高めながら、成長を続けることができることを意味します。

ロストデリバリーは安定していましたが、新しいマーケットのアイドル状態を大幅に低下させました。

低レベルのアイドル状態を維持するために昔は人員を確保してきたマーケットでは、アイドル状態を同じに保ちながら、ロストデリバリーを減らすことができました。 これにより、当社の顧客にとってより一層利用できるようになり、より迅速に成長することができます。

アイドル状態を同じに保ちながら、より成熟したマーケットでロストデリバリーを減らすことができました

これからが本番

フォローアップの記事では、私たちが過成長のためのスタッフへのこのアプローチをどのように拡張（活用）したか、そしてこのプロジェクトで学んだ教訓のいくつかについて話し合います。

________________________________________
Instacartで抱える多くの困難な問題の1つに取り組むことに興味がある場合は、キャリアページをご覧ください。

タイトル：No order left behind; no shopper left idle.

作者：Jagannath Putrevu

原文URL:https://tech.instacart.com/no-order-left-behind-no-shopper-left-idle-24ba0600f04f