車がないときに Yandex.Taxi が車を検索する方法

優れたタクシー サービスは、安全で信頼性が高く、迅速である必要があります。 ユーザーは詳細には立ち入りません。ユーザーにとって重要なのは、「注文」ボタンをクリックして、地点 A から地点 B まで連れて行ってくれる車をできるだけ早く受け取ることです。近くに車がない場合、サービスは次のようにする必要があります。クライアントが誤った期待を持たないように、このことをすぐに知らせてください。 しかし、「車禁止」の標識が頻繁に表示される場合、ユーザーがこのサービスの利用をやめて競合他社に行くのは当然です。

この記事では、機械学習を使用して、低密度エリア (つまり、一見すると車が存在しないように見える場所) での車の検索の問題をどのように解決したかについて話したいと思います。 そして、それから何が起こったのか。

背景

タクシーを呼ぶには、ユーザーはいくつかの簡単な手順を実行しますが、サービス内では何が起こっているのでしょうか?

ユーザー	ステージ	バックエンド Yandex.Taxi
開始点を選択します	ピン	候補者の簡易検索であるピン検索を開始します。 見つかったドライバーに基づいて、到着時刻が予測されます (ETA がピンに表示されます)。 指定された点での増加係数が計算されます。
目的地、運賃、要件を選択します	提供	ルートを構築し、増加係数を考慮してすべての料金の価格を計算します。
「タクシーを呼ぶ」ボタンを押す	ご注文	車の徹底的な検索を開始します。 最適なドライバーを選定し、オーダーを提案します。

オン ピンのETA, 価格計算 и 最適なドライバーの選択 私たちはすでに書きました。 そして、これはドライバーを見つける物語です。 オーダーが作成されると、検索はピンとオーダーの XNUMX 回行われます。 オーダーの検索は、候補者の募集とランキングの XNUMX 段階で行われます。 まず、道路グラフに沿って最も近いドライバー候補が見つかります。 その後、ボーナスとフィルタリングが適用されます。 残りの候補者がランク付けされ、勝者が注文のオファーを受け取ります。 彼が同意した場合、彼は注文に割り当てられ、配達場所に行きます。 彼が拒否した場合は、次のオファーが来ます。 候補がなくなった場合は、再度検索が始まります。 これは XNUMX 分以内に完了し、その後注文はキャンセルされて消去されます。

ピンの検索は注文の検索と似ていますが、注文が作成されず、検索自体が XNUMX 回だけ実行される点が異なります。 候補数や検索範囲の設定も簡素化されています。 このような単純化が必要なのは、ピンの数が桁よりも多く、検索がかなり難しい操作であるためです。 この話の重要な点は、予備検索中にピンに適切な候補が見つからなかった場合、注文を許可しないことです。 少なくとも以前はそうでした。

ユーザーがアプリケーションで見たものは次のとおりです。

車のない車を検索する

ある日、私たちはある仮説を思いつきました。ピンに車がなかったとしても、場合によっては注文を完了できるのではないかということです。 結局のところ、ピンと注文の間にはある程度の時間が経過し、注文の検索がより完全になり、場合によっては数回繰り返されます。この間に、利用可能なドライバーが表示される場合があります。 また、その逆もわかっていました。ピン上でドライバーが見つかったとしても、注文時にドライバーが見つかるとは限らないということです。 時には彼らが消えたり、誰もが注文を拒否したりすることもあります。

この仮説を検証するために、私たちは実験を開始しました。テスト グループのユーザーに対して、ピンの検索中に車の存在を確認するのをやめました。つまり、ユーザーには「車なしで注文」する機会がありました。 結果は全く予想外でした: 車がピンに載っていない場合、29% の場合、後で注文時に検索したときに見つかりました。 さらに、車のない注文は、キャンセル率、評価、その他の品質指標の点で、通常の注文と大きな違いはありませんでした。 車を使わない予約は全予約の 5% を占めましたが、成功した旅行全体では 1% 強にすぎません。

これらの注文の執行者がどこから来たのかを理解するために、ピンの検索中のステータスを見てみましょう。

• 利用可能： 可能でしたが、遠すぎるなどの何らかの理由で候補に含まれませんでした。
• 注文時: 忙しかったですが、なんとか自分自身を解放したり、仕事に参加できるようになったりしました チェーンオーダー;
• 忙しい： 注文を受け付ける機能は無効になったが、運転手は列に戻った。
• 利用不可： ドライバーはオンラインではありませんでしたが、現れました。

信頼性を高めてみましょう

追加注文は素晴らしいことですが、検索が成功した割合が 29% であるということは、ユーザーが長時間待った結果、結局どこにも行かなかった時間の 71% を意味します。 これはシステム効率の観点からは悪いことではありませんが、実際にはユーザーに誤った期待を与えて時間を無駄にし、その後ユーザーは動揺してサービスの使用を中止してしまう可能性があります。 この問題を解決するために、私たちは注文中の車が見つかる可能性を予測する方法を学びました。

スキームは次のとおりです。

• ユーザーはピンを置きます。
• 検索はピンに対して実行されます。
• 車がいない場合は、おそらく車が現れるだろうと予測します。
• 確率に応じて注文を許可するか許可しませんが、現時点ではこのエリアの車の密度が低いことを警告します。

アプリケーションでは次のようになります。

このモデルを使用すると、新しい注文をより正確に作成でき、人々を無駄に安心させることがなくなります。 つまり、適合率-再現率モデルを使用して、機械を使用せずに信頼性と注文数の比率を調整することです。 サービスの信頼性は、製品を使い続けたいかどうかに影響します。つまり、最終的には旅行の回数にすべてが帰着します。

適合率と再現率について少し機械学習の基本タスクの 1 つは、オブジェクトを 1 つのクラスのいずれかに割り当てる分類タスクです。 この場合、機械学習アルゴリズムの結果は、多くの場合、いずれかのクラスのメンバーシップの数値評価 (確率評価など) になります。 ただし、実行されるアクションは通常、二項対立です。車が利用可能な場合は注文させますが、そうでない場合は注文しません。 具体的には、数値推定を生成するアルゴリズムをモデルと呼び、分類器を XNUMX つのクラス (XNUMX または –XNUMX) のいずれかに割り当てるルールと呼びます。 モデル評価に基づいて分類器を作成するには、評価しきい値を選択する必要があります。 どの程度正確に行うかはタスクに大きく依存します。

いくつかの稀で危険な病気の検査 (分類器) を行っていると仮定してください。 検査結果に基づいて、私たちは患者をより詳細な検査に送るか、「よし、家に帰ってください」と言うかのどちらかです。 私たちにとって、病気の人を家に送ることは、健康な人を不必要に検査することよりもはるかに悪いです。 つまり、私たちはこの検査ができるだけ多くの本当に病気の人に効果があることを望んでいます。 この値はリコールと呼ばれます =。 理想的な分類器の再現率は 100% です。 最悪の状況は、全員を検査に送ることです。そうすれば、リコールも 100% になります。

その逆も起こります。 たとえば、私たちは学生向けのテスト システムを作成していますが、それには不正行為検出機能が備わっています。 不正行為の一部のケースで突然チェックが機能しなくなった場合、これは不快ではありますが、重大ではありません。 一方で、やってもいないことを理由に学生を不当に責めるのは非常に悪い行為です。 つまり、分類器の肯定的な答えの中に、おそらくその数が犠牲になるかもしれないが、できるだけ多くの正しい答えが存在することが私たちにとって重要です。 これは、精度を最大化する必要があることを意味します = 。 すべてのオブジェクトでトリガーが発生した場合、精度はサンプル内の定義されたクラスの頻度と等しくなります。

アルゴリズムが数値的な確率値を生成する場合、異なるしきい値を選択することで、異なる適合率と再現率の値を実現できます。

私たちの問題では、状況は次のとおりです。 再現率は提供できる注文の数、精度は注文の信頼性です。 モデルの適合率と再現率の曲線は次のようになります。

極端なケースとしては、誰にも注文を許可しない場合と、全員に注文を許可する場合の 0 つがあります。 誰も許可しない場合、リコールは 100 になります。注文は作成されませんが、失敗する注文はありません。 全員を許可すると、再現率は 29% (可能なすべての注文を受け取ります)、精度は 71%、つまり注文の XNUMX% が不良になります。

開始点のさまざまなパラメーターを記号として使用しました。

• 時間/場所。
• システム状態 (近隣のすべてのタリフおよびピンの占有マシンの数)。
• 検索パラメータ (半径、候補数、制限)。

標識について詳しくは

概念的には、次の XNUMX つの状況を区別したいと考えています。

• 「深い森」 - 現時点ではここには車がありません。
• 「アンラッキー」 - 車はありますが、検索しても適切な車がありませんでした。

「不運」の一例としては、金曜日の夕方にセンターに多くの需要がある場合が挙げられます。 注文はたくさんあり、喜んでくれる人もたくさんいますが、全員に対応できるドライバーが足りません。 このような結果になる可能性があります。ピンに適切なドライバーがありません。 しかし、現時点ではこの場所には多くのドライバーがおり、彼らのステータスは常に変化しているため、文字通り数秒以内にそれらは表示されます。

したがって、ポイント A 付近のさまざまなシステム インジケーターは優れた特徴であることが判明しました。

• 車両の総数。
• 注文した車両の数。
• 「Busy」ステータスで注文できない車両の数。
• ユーザー数。

結局のところ、周囲に車が多ければ多いほど、そのうちの XNUMX 台が利用可能になる可能性が高くなります。
実際、私たちにとっては、車の位置を特定するだけでなく、旅行を成功させることが重要です。 したがって、旅行が成功する確率を予測することができました。 しかし、この値はユーザーとドライバーに大きく依存するため、これを行わないことにしました。

モデルトレーニングアルゴリズムは次のとおりです。 キャットブースト。 実験から得られたデータはトレーニングに使用されました。 実装後はトレーニング データを収集する必要があり、場合によっては少数のユーザーがモデルの決定に反して注文する可能性がありました。

結果

実験の結果は予想どおりでした。モデルを使用すると、信頼性を損なうことなく、車なしの注文による成功した旅行の数を大幅に増やすことができます。

現時点では、このメカニズムはすべての都市と国で導入されており、その助けにより旅行の成功率は約 1% です。 さらに、自動車の密度が低い一部の都市では、そのような旅行の割合が 15% に達します。

タクシー技術に関するその他の投稿

• Yandex.Taxi でドライバー間で注文を分配する方法
• 動的な価格設定、または Yandex.Taxi が高い需要を予測する方法
• コンピュータービジョンを使用して車の状態を評価する方法。 Yandex.Taxi の経験
• Yandex.Taxi が機械学習を使用して車のピックアップ時間を予測する方法

出所： habr.com