Fulfillment Time Estimation: How to Make Food Delivery Faster?

はじめに

最近、Alibaba のローカルライフ・スマート物流チームによる論文「Order Fulfillment Cycle Time Estimation for On-Demand Food Delivery」が、KDD'2020 Applied Data Science Track の Oral 発表として採択されました (ACM Knowledge Discovery and Data Mining (SIGKDD)、CCF A ランク学会、データマイニング分野の最高峰カンファレンスであり、2020 年の Oral 発表採択率は 5.8%)。

注文履行サイクルタイム (OFCT：Order Fulfillment Cycle Time) の問題は、一般的な時間推定問題よりも複雑です。レストランとユーザー間には需要と供給の関係があり、レストランの出餐時間は不明であり、ライダーの行動には不確実性があります。本論文では、配達時間の予測問題を初めて学術コミュニティに詳細に紹介し、効果的な解決策を提示しました。このアプローチはレビューアーから全会一致で承認されました。

Ele.me プラットフォームがユーザーに時間通りに食事を配達することを保証する注文履行の全プロセスを段階的に分解することで、配達履行時間の推定が他の一般的な配達時間問題 (配車サービスなど) とどのように異なるかを分析し、履行時間の長さに影響する特性について説明しました。ユーザーにとっては、食事が届くまでの時間がわかるだけかもしれませんが、その背後では履行時間推定の精度を確保するために多数の要因を抽出する必要があります。これらの要因を深層ニューラルネットワークに入力して要因と履行時間の関係を推論し、さらにレストラン、ユーザー住所、ライダーの隠れベクトルを導入してモデルの予測性能を向上させます。最後に、新しい後処理ニューラルネットワーク演算子を提案し、モデルの収束速度と精度を向上させます。本論文で紹介するモデルは実際に Ele.me にデプロイされ、毎日数千万人のユーザーにサービスを提供しています。

背景

履行時間推定モデルは、ユーザーが注文を確定してからライダーがユーザーに注文を配達するまでの時間を推定します (推定配達時間)。Ele.me プラットフォームでは毎日数千万件の注文が発生します。リアルタイム配達の一部として、時間推定はユーザー体験に影響するだけでなく、ライダーの履行にも関わるため、プラットフォームにとってその精度は非常に重要です。見積もりが長すぎても (ユーザー体験の低下)、短すぎても (ライダーが時間通りに配達できない) いけません。以下の図は、時間推定に関連するさまざまな環節を示しています。

主な環節は以下のとおりです。

・ユーザー：注文確定から注文がユーザーに配達されるまで。すべてのユーザーは、注文した食事を時間通りに受け取りたいと考えています。

・レストラン：注文の受付からレストランでの食事準備。レストランはできるだけ早く食事準備を完了し、ライダーのピックアップと配達に影響を与えないようにする必要があります。レストランに到着したライダーが長時間待たされると、ライダーが焦りを感じやすくなり、一部のユーザーはアプリ上でライダーに催促します。

・ライダー：ライダーが注文を受注して配達を完了します。これには、レストランへの到着とレストランからの注文ピックアップが含まれます。同時に、ライダーは複数の注文をピックアップする可能性があるため、出発前にすべての注文が揃うまで待つ必要があります。

・プラットフォーム：Ele.me プラットフォームはユーザー、レストラン、ライダー間を協調し、配達効率を考慮する必要があります。これには注文割り当てとルートプランニングが含まれます。注文割り当てとは、近くの適切なライダーに注文を割り当てることであり、ルートプランニングとは、ライダーに合理的なピックアップと配達のルートを推奨することです。このルートはライダーの配達距離と注文の遅延リスクの両方を考慮する必要があります。

以下の図は、Ele.me でフードデリバリーを注文した際に表示される情報であり、配達時間は当社の履行時間推定モデルによって算出されています。

配達履行時間と ETA の違い

推定到着時間 (ETA) は「Estimated Time of Arrival」の略で、一般的に出発地点から目的地までの到着時間を推定します。配車サービスにおける推定到着時間は典型的な ETA 問題です。

本論文で提案するフードデリバリー履行時間推定モデルは、ユーザーが注文を確定してからライダーが食事を配達するまでの時間を推定します。ユーザーが Ele.me でフードデリバリーを注文した後、注文はプラットフォーム上で流通を開始します。

一般的な配達時間推定と比較して、配達履行時間の推定はより特殊であり、主に以下の 2 つの点に反映されています。

1 考慮すべき要因が多い

一般的な配達時間推定問題は、天気、交通状況、時空間情報、ルート情報のみを考慮すればよいのに対し、フードデリバリー履行時間推定では、これらの情報に加えてレストランの地理位置、レストランの注文準備時間、およびディスパッチシステムの注文情報なども考慮する必要があります。

2 重要な情報を事前に取得できない

Ele.me はユーザーが注文を確定した時点で既に推定配達時間を提示していますが、この時点では注文はまだライダーに受け取られておらず、システムによってライダーが割り当てられてからピックアップと配達が開始されるため、ライダーの情報と実際の配達ルートを事前に取得することはできません。

上記 2 つの違いは、配達履行時間予測の精度に大きな課題をもたらします。

配達時間予測に必要な特徴量

配達履行時間をモデル化するには、一般に注文情報に関連するデータを十分に活用する必要があります。

・空間特徴：ユーザーのエリア ID、レストラン ID、都市 ID、グリッド ID などの多数の ID 特徴を含みます。
・時間特徴：時間と分、その日が平日かどうかを含みます。
・注文規模を記述する特徴：注文に対応する料理の数と注文価格などを含みます。
注文価格がどのように配達時間に影響するのか不思議に思うかもしれません。ユーザーの注文金額が高い場合、食事の重量や体積が通常比較的大きくなります。たとえば、ユーザーがケーキを注文したり、複数杯のミルクティーをまとめて注文した場合です。このような合計金額が高い注文はライダーにとって配達しにくいため、履行に時間がかかります。この相関関係を示しており、注文価格がある程度、注文の配達難易度に関する暗黙の情報を記述できることがわかります。

需要と供給が履行時間に与える影響

プラットフォームの観点から、ユーザーの注文量とレストランの受注量は時間帯によって激しく変動します。この需要と供給の次元での変動は、実際の配達時間に大きな影響を与えます。

需要と供給の特徴量構築の作業を紹介する前に、フードデリバリーにおける「ウェーブ」の概念を説明します。ライダーの一連の注文に対して、指定された注文セットのピックアップと配達の行動がすべてそのグループ内で完結するように注文をグループ化し、このグループがライダーの現在の配達ウェーブとなります。需要と供給の変動に対して、時間帯別の需要供給比や完了率などの特徴量を構築しました。需要供給比が高いほど、ウェーブの平均所要時間が長くなり、履行時間も長くなります。

一方、完了率が高い場合、ライダーがより多くの注文の配達を完了し、システムから割り当てられる次の注文を引き受けられる状態にあると推測できます。

さらに、レストランの現在ピックアップ待ちの注文数 (レストランが注文を受信した後、ライダーのピックアップを待っている注文数) によってレストランの繁忙度を記述します。レストランの受注数が増加し処理能力が限られている場合、注文の滞留が発生します。ライダーが既にレストランに到着している場合、食事を受け取るまでに時間がかかります。これに対応して、レストランが繁忙になると、モデルが推定する履行時間は長くなります。

レストランの出餐時間

注文の配達時間は配達履行時間予測モデルの重要な要因です。この特徴量はレストランの過去の配達時間を集約して得られます。しかし、既存の課題が出餐時間の計算精度に大きな課題をもたらしています。主な課題は以下のとおりです。

・レストランには調理完了後に一つずつ配達ボタンをクリックする人的余裕がなく、プラットフォーム側がレストランの実際の出餐時刻を完全に取得できません。そのため、現在は主にシステムが収集するライダーのピックアップクリックデータに依存してレストランの実際の出餐時間をマークしています。

・Ele.me プラットフォームは現在、主に Ele.me アプリ経由でレストランが発生させた注文を計算しており、他のチャネルや店内食事のデータが不足しているため、レストランの実際の負荷を把握することが困難です。

・レストランの実際の出餐時間は比較的ランダムです。たとえば、レストランは特定の食事について事前準備を行う場合があり、これらの事前準備された食事はすぐに提供できます。ユーザーが注文した時点で調理を始める必要がある食事については、ライダーがレストランに到着してからしばらく待つ必要があります。この部分の作りたて注文の実際の履行時間は長くなります。

・注文の順番は必ずしもレストランの調理順序を示しません。レストランのコンロ数は限られており、対応するコンロは特定の料理のみを処理します。そのため、同じ料理が一連の注文に含まれている場合、厨房はまとめて調理することを選択します。この場合、一部の注文の出餐時間は明らかに短くなります。

実際の使用では、レストランが注文を受信した時刻からライダーが実際にピックアップをクリックした時刻までの時間でレストランの実際の出餐時間を計算しています。以下のノイズデータが存在します。

・ライダーが注文を受信した直後に出発してレストランに到着をクリックする
・ライダーが注文を受信した直後にピックアップボタンをクリックする

さらに、一部のトレーニングサンプルでは、ライダーが食事を受け取る時点でレストランは既に食事準備を完了していると判断できます。たとえば、ライダーが遅れてピックアップする場合や、ライダーが同時に複数の食事をピックアップする場合です。これらのデータについて、レストランの出餐時間の特徴量を計算する際に一定割合を除外しています。

ライダー情報の合理的な活用方法

プラットフォームの観点から、Ele.me は各都市を「グリッド」を最小単位とした異なるエリアに分割しています。各ハミングバード配達拠点のライダーは拠点周辺の複数の固定グリッドを担当します。拠点がカバーするグリッド内の商業地区や住宅地に対するライダーの熟知度が配達効率を決定します。ライダーはレストランの位置とユーザーの所在地に精通しているため、ピックアップや配達の過程で迂回がありません。

ユーザーが注文を確定すると、Ele.me アプリはすぐにユーザーに推定配達時間を表示します。この時点では、注文がどのライダーに割り当てられるかは不明です。ライダーに関連する要因を十分に活用するため、注文を受け取る可能性のある各ライダーを、ライダーとの距離や現在の受注数に基づいて特徴化し、注文を受け取る可能性のあるライダーのシーケンスを配達時間予測モデルにエンコードします。そして、アテンションメカニズムを使用してライダーのシーケンス情報を抽出し、モデルの予測能力を向上させます。

多次元類似注文の配達区間 ETA

配達区間の ETA とは、ライダーが配達先 (ユーザーの所在地) 付近で降車してから食事をユーザーに届けるまでの推定時間を指し、ライダーの配達プロセスの最後の環節です。

配達区間の ETA を推定するために、理論的には回帰モデルを直接使用して学習できますが、一般的に回帰モデルは入力を一連の特徴量に変換し、教師あり学習を通じてこれらの要因と出力目標の関係を見つけ、モデルの汎化性能を向上させます。これらの関係は通常、ニューラルネットワークとアンサンブル木モデルに基づく滑らかな関数としてパラメータ化されます。しかし、この滑らかさの仮定の欠点は、ロングテールのイレギュラーなケースをうまく処理できないことであり、ユーザー体験に影響を与える可能性があります。たとえば、ライダーが高層ビルのエレベーターを利用して配達する場合、ピーク時には長時間待たされる可能性があり、システムがこのようなリアルタイム予測を行うことは困難です。ライダーが配達時にビル内で 7.6 分を費やした例を示しています。

この問題を部分的に緩和するために、最近のメモリベース言語モデル [1] のアイデアを借用し、過去の注文を配達時間予測のコーパスとして使用し、多次元特徴量を構築することで各履歴注文を表現します。新しい注文が発生した際に、K 近傍法に基づいて新しい注文に類似した複数の履歴注文を検索し、これらの類似注文の実際の配達時間を加重平均して新しい注文の推定配達時間とします。最後に、K 近傍探索に基づく推定配達時間を配達履行時間推定モデルの特徴量として入力します。

ロングテールデータの処理方法

時間推定は本質的に回帰問題です。モデルのトレーニング中に、モデルの収束が遅く、交差検証の性能が期待から外れていることを発見しました。原因を分析した結果、モデルがフィッティングしたデータ分布と実際の履行時間の分布に乖離があることが判明しました。実際の履行時間は右側に長いテールを持つ分布であり、少数の注文で配達時間が長く、モデルが十分に学習できていませんでした。この問題を解決するために、本論文では新しい後処理ニューラルネットワーク演算子を提案し、配達履行時間予測モデルのフィッティング結果をスケーリング・変換して、モデルの収束速度と精度を向上させます。後処理演算子は以下のように記述できます。

オフラインでのトレーニングと検証を経て、後処理演算子は配達履行時間予測モデルの収束速度と精度を効果的に向上させることができます。

最近、新しい後処理演算子である適応 Box-Cox 逆変換を検討しました。本論文で提案する後処理演算子と比較して、適応 Box-Cox 逆変換演算子はロングテールデータの分布によりよく適合し、モデルの効果をさらに向上させます。現在、この演算子はオンライン推論に適用されています。

実験結果

本論文で提案したフードデリバリー履行時間予測モデルは「エンコーディングと予測」をモデルの主な構造として採用しており、具体的な構造を以下の図に示します。

その中で、Nearest Courier Index モジュールは前述のライダー情報のエンコーディングを実装しています。このモジュールにより、モデルは注文を受け取る可能性のあるライダーの情報を十分に活用できます。Postprocessing は後処理演算子です。この演算子により、モデルはより速く収束し、精度も向上します。

配達時間予測モデルを提案する以前から、既存のオンライン時間予測モデルが安定的に運用されていたため、既存のオンラインモデルをベースラインとして AB 実験を実施しました。実験データによると、従来モデルと比較して、フードデリバリー履行時間予測モデルの MAE は相対的に 9.8% 改善し、ユーザークレーム率は相対的に 19.3% 改善しました。予測誤差とユーザークレーム率が顕著に改善され、ユーザー体験に大きな好影響を与えています。

まとめと今後の展望

本記事では、Ele.me で実際にオンライン運用されユーザーにサービスを提供しているフードデリバリー履行時間予測モデルを紹介しました。その有効性はオフライン評価とオンラインテストを通じて実証されています。

今後、主に以下の 2 つの方向性に注力して研究を継続します。

・出餐時間はフードデリバリー履行時間予測モデルの重要な要因の一つですが、現在の出餐時間の処理は比較的単純であり、大幅な改善の余地があります。

・さらに、出餐時間と履行時間のマルチタスク学習に対応する汎用モデルフレームワークを開発する予定です。