Delivery Scope: A New Way of Restaurant Retrieval For On-demand Food Delivery Service

Delivery Scope: A New Way of Restaurant Retrieval For On-demand Food Delivery Service(KDD2020 Accepted Papers)を読んでまとめました。
解釈間違い等ある時がありますので、その場合指摘いただけると助かります。

目次

背景と概要

背景

• 中国では、オンデマンドのフードデリバリーサービスが人気となっており、毎日3,000万件以上の注文がMeituan-Dianping(美団点評)の利用者により行われ、平均30分以内に配達されている
  • Eater(食べる人、消費者)の急増と宅配業者の数が限られている事より、配送能力をどれだけフルに活用できるかがオンデマンドのフードデリバリーサービスのカギとなる。

概要

• 本フレームワークでは、delivery scope generation algorithmを提案している。
  • delivery scope:レストラン検索の新しい仕組みで配送範囲を定義
    • 本アルゴリズムが出来る前は各都市のオペレーションスタッフが全配送範囲を手書きで書いており、Eaterの需要と飲食店・宅配業者といった共有のバランスを考え書くのは大変な作業だった。
  • 空間データマイニング技術、機械学習、組み合わせ最適化を活用
• delivery scope generation algorithmの流れ

  • 1.ターゲットとなる飲食店のdelivery scope候補を作成。

    • delivery scope候補作成の流れ
      • 1.Initialization
      • 2.Scope Shape Optimization for Experience
      • 3.Scope Compression
      • 4.Covering High-Demand Areas

  • 2.回帰モデルにより飲食店がscopeを採用した場合の注文数・平均の注文から配達までの時間を推定しスコアリング。

  • 3.2値整数計画問題(binary integer programming problem)としてdelivery scopeの割り当てプロセスを定式化。
    • 特定エリア内の各飲食店のdelivery scopeの最適化を行う。
    • 近似解を高速に解くアルゴリズムとして、BIP Heuristic Algorithmを提案。

以下詳細(今回は長いです)

以下、フードデリバリーサービスの大きな流れ

delivery scope

• 制約:平均30分以内にEaterに注文を届けなければならないが、宅配の供給量に限りがあるので、Eaterが自分たちの町の全レストランに注文できるという状態は現実的ではない。
• サービスプラットフォームでは全レストランにサービスエリアとしてspatial polygon(直訳すると空間的な多角形)を提供している
  • そのエリア内の飲食店にだけ、Eaterは注文が可能
• 本論文ではspatial polygon : delivery scopeと定義している。

delivery scopeのイメージ

delivery scopeの従うべき原則

delivery scopeは以下の内容に従うべきである。
1.レストランの配達範囲は、需要の高いエリアをカバーしなければならない。
2.配達範囲は、その供給能力が相対的に低い場合、他のレストランより小さくなければならない。
3.配達範囲は、遠く離れた場所をカバーしてはならない。

RESTAURANT RETRIEVAL SYSTEM ARCHITECTURE

• レストラン検索システムについて:2つのpartで構成
  • Delivery Scope Indexer
    • delivery scopeの追加・削除などを実施
  • Delivery Scope Generation System
    • 後述

Delivery scope system architecture

DELIVERY SCOPE GENERATION ALGORITHM

• 目的:宅配業者による配達ブロックであるtarget station内の全飲食店に対して、リーズナブルなdelivery scopeを提供すること。
  • 一つの駅にあるレストランの数:200~1000程

How to Draw Single Scope : delivery scope候補の生成プロセス

• delivery scopeは複数の頂点を持つ多角形で表現される。
• single scope generation algorithmは以下の4モジュールにより構成される。
  • 1.Initialization
  • 2.Scope Shape Optimization for Experience
  • 3.Scope Compression
  • 4.Covering High-Demand Areas
• 各モジュールはそれ以前の暫定delivery scopeを入力とする。

  1.Initialization

• まずレストランの位置を中心として、入力半径(目標)の円を描く。
  • 円:境界線上で等間隔の一定数の点で表現される。
• これらの点から中心までのnavigation distance(実際に到達するために移動する距離)が直線距離よりもはるかに大きい場合が考えられる。
  • 本アルゴリズムでは、元の点と中心との間で中心までのnavigation distanceが目標半径にほぼ等しい点を探索(二値探索)。
  • 各ステップにおいて、以下の長さで中心に向かい移動する。
    • (小さい距離でも境界点を更新する毎に、navigation distanceが変化する事を想定していると思われる)

naviDist:境界点~中心のnavigation distance,
straightLineDist:境界点~中心の直線距離,
targetRadius:入力目標半径,
minStep:探索過程で最小移動長を制限するハイパーパラメータ

モジュール1:Initializationのイラスト

2.Scope Shape Optimization for Experience

• ユーザー、飲食店、配送業者のより良い体験を保証するためにdelivery scopeの境界線は道路に沿う必要がある。
  • delivery scopeの境界線が建物やブロックに跨っている場合、同じ建物の中で異なるユーザー体験になる場合がある。
    • e.g.同じ建物のEaterである飲食店に注文できる人・できない人が混在する場合があるかもしれない。
• 道路に従った境界線取得のため、navigation routesを使用する。
  • navigation routesを使用した際のstubを除去する処理も行われる。

3.Scope Compression

• 効率的なデータ計算のため冗長な点を除去する。
  • 各点の隣接する点との角度を計算し十分180°に近い場合、その点は削除される。
  • また隣接する点との角度および距離に基づいて各点を評価し、より高スコアな方を残す。
• 本モジュールには、Douglas-Peucker algorithmも用いられている。

モジュール2:Scope Shape Optimization for Experience、3: Scope Compressionのイラスト

4.Covering High-Demand Areas

• 需要の高いエリアをカバーするようにdelivery scopeを変更する。
  • 中心を注文分布に応じてシフトさせる
  • 需要の高い領域がdelivery scopeに直接マージされる。
    • 上記領域はGeoHashクラスタリング(K-meansとDBSCANの組み合わせ)で決定される。

モジュール4:Covering High-Demand Areasのイラスト

• 以下が実験で示されている実際のdelivery scopeの生成過程

Delivery Scope Drawing Algorithmの結果

Single Scope Scoring : delivery scope候補生成後のスコアリングプロセス

• 1つの飲食店に対し異なる半径のdelivery scope候補を生成した後、スコアリングを行う。
• 受注数の推定
  • スコアリング対象のdelivery scopeの範囲が現状より小さい場合、過去の注文数を 用いる
  • スコアリング対象が大きい場合、以下の2段階となる。
    • 現状のdelivery scopeの範囲内(以下図の黄色い領域):過去データからスコアを計算
    • 現状のdelivery scopeの範囲外かつスコアリング対象のscopeの範囲内(以下図のピンク色の領域):回帰モデルにて予測。
      • リッジ回帰、ランダムフォレスト、XGBoost等を使用し比較している。
• 平均配送時間の推定:上記受注数と同様に計算される。

Single Scope Scoringのイラスト

Delivery Scope Optimization

• ここまで得られた情報を使って、各飲食店に合理的なdelivery scopeを割り当てて駅におけるglobalな最適化(GMV (Global Merchandise Volume))や注文数を達成すると同時にEaterの体験を保証する事を考える。

問題設定

ターゲットとなる駅に対して以下を考える

今回の問題は以下のBIP(二値整数計画)問題として扱う。

上記問題の近似解を高速に解くアルゴリズムとして、以下のBIP Heuristic Algorithmが提案されている。

BIP Heuristic Algorithm

検証

A/Bテスト

• 1448駅、160,000の飲食店でランダムに選択しA/Bテストを実施
• 評価では以下の指標を使用している
  • t:平均納品時間
  • d:平均配送距離
  • OR:オンタイム率
  • CR:完了率
  • CE:クーリエ効率、1人のクーリエ(配達員と同じ？)が1日に完了した注文数の平均
• 結果として以下を述べている(下の表)
  • 注文数が約1.68pp改善
  • クーリエ効率が約1.94pp改善
• また、下の図ではほとんどの実験都市では本論文で提案したアルゴリズムで生成したscopeの方が配送効率を悪化させずにより多くの注文をもたらしているとしている。

実験結果

A/Bテスト結果

人が作った結果よりもアルゴリズムの結果が良い事に関する考察

• 以下の2点があげられている。

  • アルゴリズムで生成されたdelivery scopeは手動のものより優れている

    • 人手で作った場合、境界点と飲食店の距離が同じになるような飲食店中心の多角形を描く傾向がある。
    • そのためnavigation distanceと直線距離に大きな違いがあった場合、実質的にdelivery scopeが遠い位置をカバーする事となる。

  • BIPモデルがレストランの特性に応じて異なるscopeをカスタマイズしている。

    • 一般的にconversion rateが高く、交通の便が良い程scopeを大きく設定できる。
    • 以下の図は同じ駅の飲食店でも生成されるscopeに大きな違いがある事を示している。