中国ライドシェア最大手DiDiが採用するマッチングアルゴリズム。利用者全員の平均待ち時間最小化を考える「ダイナミックVRP」とは？

複数の車両がスタート地点から需要のある地点を回り、ゴールに到達するまでの最短経路を考える「VRP（Vehicle Routing Problem、配送計画問題）」。この問題に時間経過とともに起きうる乗客の増減、車両の移動といった動的変量を加えたのが、ライドシェア業界で言われている「ダイナミックVRP（Dynamic Vehicle Routing Problem、動的配送計画問題）」。アプリ配車が主流の中国でトップの市場シェアを誇る滴滴出行（ディディチューシン、以下DiDi）は、この「ダイナミックVRP」に挑み、配車注文の応答率を90％以上に引き上げることに成功している。本記事はDiDiのチーフアルゴリズムエンジニア・Wang Ben氏の技術ブログ記事をもとに、利用者全員の平均待ち時間の最小化を目指す同社の試みを解説する。

• keyboard_arrow_down 「最短法」の配車アルゴリズムは最適なのか？
• keyboard_arrow_down 時間軸をも考慮する「ダイナミックVRP」。DiDの取り組みとは
• keyboard_arrow_down 機械学習で需要の高い場所にタクシーを事前に誘導する
• keyboard_arrow_down O2O領域で重要になる機械学習とダイナミックVRP

タクシー配車アプリは日本でも広く使われている。スマートフォンでタクシーを呼ぶと、近くにいるタクシーが迎えにきてくれ、確実に乗車できるというものだ。日本交通系の「JapanTaxi」とDeNA系の「MOV」が統合された「GO」、中国から上陸した「DiDi」、米国から上陸した「Uber Taxi」などが競い合っている。

このような配車サービスには、スマホ登場以前からも無線タクシーというものがあった。電話で乗車地点を伝えると、センターのスタッフが最も近くにいるタクシーを配車してくれるというものだ。無線タクシーの場合、配車のアルゴリズムは「最短法」。利用者から最も近い位置（厳密には到着時間）にいるタクシーとマッチングをする。利用者の視点からは、最も早くタクシーが到着することになり、ユーザー体験を最大化できるため、このシンプルなアルゴリズムで何も問題はない。

しかし、その単純なアルゴリズムが成立したのは、無線タクシーの利用者が全体の数パーセントにすぎなかったからである。中国の場合、配車アプリが広がるにつれ、ほぼ100％の利用者がアプリから配車注文している。このレベルになると、最短法では問題が生じてしまう。

極端な例として、新幹線のターミナル駅や空港を想定しよう。乗客が次々と現れ、近い場所にいるタクシーからマッチングしていく。しかし、朝晩など他所でタクシーの需要が高まる時間帯だと、近くにいるタクシーは枯渇してしまう。すると、後のほうの利用者はタクシーが到着するまで長い時間待たされることになる。最短法は、このような突発的な需要発生に弱いのだ。

配車アルゴリズムが目指すのは、1人の利用者に最短時間でタクシーを提供することではなく、利用者全員の平均待ち時間を最小化することだ。そこで登場するのが、「ダイナミックVRP」という考え方である。あるエリアに複数人の利用者と複数台の車両がいて、その数とステータスは時間経過とともに変動することを想定し、いかにして利用者全員の待ち時間を最短化できるかを考える問題だ。

中国のライドシェア企業DiDiは自社の技術ブログで、ダイナミックVRPを実践上で解決する「全体最適化」と「連続配車」という2つの考え方について紹介している。これらを組み込んだ配車アルゴリズムを活用し、DiDiは配車注文の応答率を90％以上に引き上げることに成功した。

・全体最適化

「全体最適化」とは、その名のとおり、利用者全員の平均待ち時間を最小化する考え方である。ブログでは利用者2人とタクシー2台がいるシチュエーションを想定している。

最短法を適用すると、利用者1から3分離れているタクシー1を配車することになる。ただその場合、利用者2の待ち時間は12分になり、利用者の平均待ち時間は7.5分（画像A）。一方、利用者1から離れているように見えるタクシー2を配車した場合、利用者の平均待ち時間は5分と短くなる（画像B）。利用者1人にとっての「最短」を求めるのではなく、利用者全体にとっての「最適」を追求するという考え方だ。

・連続配車

実際の配車現場ではよく以下のような場面に遭遇するという。

配車注文を出している利用者1人から5分離れた距離のところに空車ステータスのタクシーが1台走っている。従来のアルゴリズムだと、このタクシーをすぐに利用者に配車するだろう。ところが、3分離れた距離にも乗客を乗せているタクシーが1台走っていて、今まさに目的地に着き乗客を降ろしている最中だ。つまり、数秒後には、こちらのタクシーも空車ステータスに変わり、利用者にとっては最も早く到着するタクシーになる。

配車注文があった瞬間の状況だけでマッチングすると、利用者の待ち時間は5分になる。しかし、数分後の状況まで想定して判断すると、利用者の待ち時間は3分+αに短縮される。

下図のような場合、利用者にとっての配車候補は2台ある。1台は12分の距離にいる空車。もう1台は4分の距離にいる賃走状態のタクシーで、2分後に乗客を降ろし、空車ステータスに戻る。乗降客の時間を加味しても4分+αで利用者のところに到着できるため、DiDiの配車システムでは後者のほうを利用者に配車する。このように、配車注文があった瞬間の状況ではなく、時間による状況変化も計算に入れることで、全体的な最適マッチングをつくっているのだ。

DiDiのチーフアルゴリズムエンジニアのWang Ben氏によると、DiDiではこのような「ダイナミックVRP」の考え方に基づいたアルゴリズムを採用しているものの、実際の70%から80％の配車は、最短法と同じマッチングが行われているという。それでも、最短法のみの場合と比べて、1.2倍から1.5倍の実車率を実現できているそうだ。

実車率を上げる工夫は、このマッチングアルゴリズムだけではない。DiDiでは、機械学習を使った需要予測も行っている。

サービス提供エリアを六角形のセル（サイズは都市によって異なるが、1辺数百m程度）に分割し、1.5秒から2秒に1回、各セルの需要予測を行なっている。そして、実際にそのセル内にいるタクシー、そして将来空車ステータスになるタクシー台数をカウントし、需要と供給のギャップのヒートマップをつくっている。

供給が過剰になっているセルにいる運転手には、隣の供給が不足しているセルに移動すると、乗客を乗せた場合の報奨金が上乗せされるというインセンティブ情報が送られる。自然と供給過剰のセルから供給不足のセルへタクシーを移動させられるので、需要に対するタクシーの最適配置が実現できている。

日本でもタクシー配車や宅配便の配送ルート決定に、VRPの考え方に基づくアルゴリズムが採用されている。しかし、時間軸までを考慮したダイナミックVRPではなく、スタティックな考え方に基づくものが多いようだ。

中国では以前から都市人口に対してタクシーの台数が少なく、特に夕食後の時間はタクシーがつかまならないという課題が存在している。DiDiはこの課題に着目してタクシー配車サービス企業として創業し、ライドシェア、シェアリング自転車、ロボタクシー（自動運転タクシー）と、都市交通の課題を解決する幅広い事業を展開している。現在の中国では、「タクシーはアプリで呼ぶもの」が常識になっており、利用密度がきわめて高い状態になっている。その需要に押され、ダイナミックVRPの考え方を取り入れ、アルゴリズムを洗練させていく必要があったのだ。一方、日本ではアプリ配車の利用者はまだ少数派で、中国ほど高度なアルゴリズムは必要とされていない。

しかし、状況は変わりつつある。コンビニ大手の「セブン-イレブン」は、一部の店舗で提供していた半径500m以内に最短30分で商品を届けるデリバリーサービスを、2025年度までに全国規模に拡大すると発表している。報道記事によると、デリバリーは店舗スタッフではなく、専門チームが行い、その運用システムにはAIが活用されるようだ。おそらく、デリバリーチームは複数店舗を受け持ち、機械学習による需要予測に基づき、ダイナミックVRPに近い考え方で、最適配送ルートが計算されるシステムになるのではないかと推測する。

このように、ダイナミックVRPの実践はタクシー配車だけでなく、フードデリバリー、生鮮食料品のデリバリーなどO2O（Online to Offline）ビジネスと呼ばれる領域でも広く需要があるだろう。今後、時間指定や即時配送などのサービスが多様化していくにつれ、スタティックなルート計算では間に合わなくなり、機械学習予測とダイナミックVRPを取り入れたシステム構築が必要となるはずだ。

参考資料
滴滴（DiDi、ディディ）技術ブログ「滴滴技术」（2021年10月5日アクセス）