滴滴出行のタクシー、ライドシェアの特徴は、呼ぶとすぐにやってくることだ。滴滴出行では、車が必要な人の近くにあらかじめ配車をしておくシステムを構築している。その初歩的な仕組みを、滴滴の首席アルゴリズムエンジニアの王犇氏が滴滴技術で解説をした。
90％以上の乗車で、車が2km以内にいる滴滴出行
滴滴の「快車」と呼ばれるサービスは、基本的にタクシーと同じだ。大きな違いは、流しているタクシーを路上で拾うのではなく、スマホから呼ぶこと。自動的に現在地が取得され、最も近くにいるドライバーとマッチングされる。現在、90％以上の乗車が、ドライバーが2km以内にいるという状況が実現できている。
この、乗客とドライバーのマッチングをいかに効率的に行うかが、滴滴のサービス品質向上の鍵になっている。
近い方、評価が高い方をマッチングさせる
乗客とドライバーが1：1であれば話は簡単だ。マッチングさせるしかなく、乗客に待ち時間を伝え、ドライバーは乗客を迎えにいく。
乗客とドライバーが1：2の場合も、事情はさほど複雑ではない。近い方のドライバーをマッチングさせる。
では、２人のドライバーがまったく同じ時間かかる場合はどちらにマッチングさせるべきだろうか。この場合は、ドライバーの評価が高い方を優先してマッチングさせる。
滴滴などのライドシェアでは、乗客は利用した時に、運転手の評価ができるようになっている。主に接客品質などの評価で、これが低いドライバーは、マッチングされる確率が下がり、一定以下になると、まったくマッチングされなくなることもある。これにより、接客品質を維持している。
▲1人の乗客に１台の車。マッチングは自動的に決まってしまう。
▲1人の乗客に２台の車。早くつく方の車がマッチングされる。
▲1人の乗客に２台の車。どちらも同じ距離にいる場合は、評価の高いドライバーがマッチングされる。これで接客品質を保っている。
平均待ち時間を最小化させる最適解を計算する
乗客とドライバーの数が少ない時は、アルゴリズムと呼ぶほどの複雑さはないが、実際の都市では、問題は一気に複雑になる。
仮に20人の乗客と20人のドライバーをマッチングさせるとなると、その組み合わせは20！（20の階乗）という19桁もの数になる。
その前に2：2のケースを考えてみよう。乗客１に対しては３分で配車され、乗客２には12分で配車される。一見、これでいいように見えるが、実はこの配車には問題がある。なぜなら、乗客は待ち時間が長くなれば長くなるほど、キャンセルをする確率が上がっていくからだ。しかも、キャンセル確率は、時間が長くなるほど尻上がりに上がっていく。待ち時間12分の乗客は途中でキャンセルをしてしまうかもしれない。それは避けなければならない。
そのため、乗客の平均待ち時間と累積待ち時間の両方を最小化することが重要なのだ。３分と12分の場合では、平均待ち時間は7.5分、累積待ち時間は15分ということになる。
一方で、同じケースで、マッチングの組み合わせを変えてみると、乗客1の待ち時間は５分になり、乗客２の待ち時間も５分になる。平均待ち時間は５分、累積待ち時間は10分となり、大幅に短縮される。このマッチングが正解となる。
滴滴では、毎日3000万件のマッチングを行い、ピーク時には1分間で６万件以上のマッチングを行なっている。
基本的には、すべての乗客とドライバーの予想待ち時間マトリクスを計算し、その中から適切な組み合わせを探し出している。
▲2人の乗客に２台の車。一見、これで最適解のように見えるが、平均待ち時間は7.5分、累積待ち時間は15分となり、最適解にはなっていない。
▲マッチングを変えることで、平均待ち時間は5分、累積待ち時間は10分となり、最適解が得られた。待ち時間が長くなればなるほど、キャンセルされる確率が高くなるので、平均待ち時間を最小化することが重要になる。
未来の状況も加味して、さらに待ち時間を短縮する
滴滴は、これに未来予測を加えている。数分後の状況を予測して、より平均待ち時間が短くなるようにする。
例えば、ある乗客に対して、最も近い空車が12分の距離にいるとする。他のドライバーはすべて乗客を乗せているのでマッチングの対象にはならない。しかし、ここで目的地近くになっているドライバーの未来予測を行う。ある乗客を乗せているドライバーは、２分で目的地に到着をし、そこから２分で乗客を迎えに行ける。合計４分で乗客を乗せることができる。
この場合は、乗客を乗せている方のドライバーがマッチングされる。乗客から見ると、12分の待ち時間だったものが、４分間に短縮された。
▲マッチングには未来予測も考慮される。単純マッチングでは、12分の距離にいる空車がマッチングされるが、もう一台、2分後に乗客を降ろし、2分で迎車できる車がある。この場合は、乗客を乗せていても、次のマッチングがされることがある。
需要と供給のヒートマップを計算し、車を必要な場所へ移動させる
これは未来予測というほどまでのことはない。ほぼ確定している予測情報を利用しているだけだ。滴滴ではさらに大局的な未来予測を行っている。
人間のドライバーは、乗客を乗せていない空車の時、乗客が多そうな場所に向かい、客を捕まえる確率を高めようとする。しかし、この行動が、配車の効率を悪くしている。10人の客が予想される場所に、20台のタクシーが集まってしまようなことが起きるからだ。理想的には10人の客が予想される場所に10台のタクシーが集まり、残りの10台は別の客が予想できる場所に向かってほしい。
適切な配置は、需要と供給の比があらゆる場所で1：1になることだが、人間のドライバーは需要の絶対量が大きな場所に向かってしまいがちなので、需要の大きな場所では余剰のドライバーが生まれてしまう。
ドライバーの多くが、局所最適解に殺到するために、全体の最適化が阻まれている。しかし、人間一人の判断では、局所的な最適解しか知ることができない。この課題を解決するために、滴滴プラットフォームが存在している。
▲滴滴出行プラットフォームでは、1.5秒から2秒ごとに、各セルでの需要と供給のヒートマップを計算している。ドライバーは隣のセルの方が需要が強ければそちらに移動するということを繰り返していく。これで最適な配車が可能になる。
ドライバーは隣のセルへ移動するだけでいい
滴滴では、時間、曜日、天候などを機械学習し、各地域での需要予測を計算し、それを実際の配車数と比較して、需要と供給の過不足を計算する。過剰な地域にいるドライバーを、近隣の不足地域に誘導することで、全体の最適化を計っている。
このような計算を1.5秒から2秒ごとに行うことで、配車を最適化することで、滴滴の乗車の90%以上で、ドライバーが2km以内にいるという状況を実現できている。
滴滴出行の実車率（全走行距離に対する収入の対象となる走行距離の割合）は公開されていないが、「TAXI TODAY in Japan 2019」（全国ハイヤー・タクシー連合会、http://www.taxi-japan.or.jp/pdf/Taxi_Today_2019.pdf）によると、日本の都市部では40％台になっている。つまり、走っている間の半分以上は、お客を乗せていないことになる。
滴滴出行は、アルゴリズムや機械学習を使って、この実車率を高めることに挑戦している。乗客から見ると、「すぐにやってくる」「タクシーを探さなくてもいい」などの利点が生まれることになる。
