以前は、タクシーを呼び出すには、異なる数のディスパッチサービスを呼び出して、車が30分以上配達されるのを待つ必要がありました。 現在、タクシーサービスは十分に自動化されており、モスクワでのYandex.Taxi車の配達の平均時間は約3〜4分です。 しかし、雨を降らせるか、大量のイベントを終了することは価値があり、再び無料の車が不足する可能性があります。
私はAnton Skogorevです。Yandex.Taxiのプラットフォーム効率の開発チームを率いています。 本日、Habrの読者に、ユーザーがいつでも無料の車を見つけることができるように、高い需要を予測し、さらにドライバーを引き付ける方法を学びました。 次数の値に影響する係数がどのように形成されるかを学習します。 そこにあるものはすべて、一見思えるほど単純ではありません。
動的な価格設定の課題
動的価格設定の最も重要なタスクは、常にタクシーを注文する機会を提供することです。 これは、サージ価格係数を使用して達成され、これに計算された価格が乗算されます。 単にサージと呼びます。 急増はタクシーの需要を規制するだけでなく、新しいドライバーを引きつけて供給を増やすのにも役立つと言うことが重要です。
サージが大きすぎると、需要が減りすぎ、無料の車が過剰になります。 設定が低すぎると、ユーザーには「無料の車はありません」と表示されます。 無料の車の不足と需要の低さの間の薄い氷の上を歩く係数を選択できる必要があります。
この係数は何に依存すべきですか？ ユーザーの周りの車と注文の数への依存をすぐに思い浮かびます。 これで、次数をドライバーの数で単純に除算し、係数を取得して、それを何らかの式（場合によっては線形）で急上昇させることができます。
しかし、このタスクには小さな問題があります-ユーザーの周りの注文を数えるには遅すぎるかもしれません。 結局、注文はほとんどの場合、すでに占有されているマシンです。つまり、係数の増加は常に遅れます。 したがって、私たちは作成された注文ではなく、車を注文する意図を考慮します-ピン。 ピンは、アプリケーションの起動時にユーザーが付けるカード上のラベル「A」です。
問題を定式化しましょう：ユーザーのある時点でマシンとピンの瞬時値を読み取る必要があります。
ピンと車の数を数えます
ピンの位置が変更されると（ユーザーがポイント「A」を選択）、ユーザーアプリケーションは新しい座標と追加情報の小さなシートをバックエンドに送信し、ピンをより正確に評価するのに役立ちます（選択した関税など）。
私たちは、各マイクロサービスが個別のタスクに従事するマイクロサービスアーキテクチャに準拠しようとします。 Surgerマイクロサービスは、サージの計算に従事しています。 ピンを登録し、データベースに保存し、RAM内のピンのナゲットも更新します。 このような作業中のキャッシュラグはわずか数秒であり、この場合は許容範囲です。
データベースについて一言
登録時に、各ピンはTTL Indexを使用してMongoDbに非同期的に追加されます。TTLはピンの「寿命」であり、上昇係数を計算するためにアクティブと見なされます。 これらのアクションを実行する間、ユーザーは待機しません。 たとえ何かがうまくいかなくても、ピンを失うことはそれほど大きな悲劇ではありません。
ホットキャッシュは、 ジオハッシュインデックスを使用して構築されます。 すべてのピンをジオハッシュでグループ化してから、注文点の周りの目的の半径のピンを収集します。
車でも同じことを行いますが、トラッカーと呼ばれる別のサービスでは、サーガーは単に「この半径内に何人のドライバーがいるのか」という質問に答えます。
したがって、係数の瞬時値を考慮します。
キャッシング
ケース ：モスクワのガーデンリングに立って、車を予約したい。 同時に、価格は非常に頻繁にジャンプし、これは迷惑です。
すでにメカニズムを知っているので、これはドライバーがサージのリクエスト時に条件付きの信号機で蓄積し、すぐに出発するという事実によるものであることが理解できます。 このため、サージと価格は著しく「ジャンプ」する可能性があります。
これを回避するために、ユーザーによるサージの価値をキャッシュします。 ユーザーがサージに来たときに、そのユーザーの許容半径内に保存されたサージ値があるかどうかを確認します（ユーザーのすべての保存されたサージの線形ツアー）。 存在する場合、それを返します。そうでない場合、新しいものを期待して保存します。
これはうまくいきましたが、他の状況もあります。
ケース ：2人のユーザーがサージを要求します。 前のケースからの信号機の車がすでに去っているとき、一方は他方より30秒遅れて注文します。 2人のユーザーがほぼ同時に注文すると、大幅に異なるサージが発生する可能性があります。
そして、ここではユーザーごとのキャッシュから位置ごとのキャッシュに進みます。 これで、サージ値をユーザーのみにキャッシュする代わりに、すでに慣れ親しんでいるジオハッシュのキャッシュを開始します。 だから私たちはほとんど問題を修正しています。 なぜほとんど？ なぜなら、ジオヘッシュの境界に違いがあるかもしれないからです。 ただし、平滑化機能があるため、問題はそれほど重大ではありません。
スムージング
おそらく、信号機に関するケースを読んで、信号機に応じて、瞬間的な急増を考慮することは何らかの形で不誠実であることがわかりました。 私たちもそう思うので、状況を修正する方法を見つけました。
瞬間的なサージの値が私たちの周りで起こっていることとどれだけ異なるかを決定するために、回帰問題の機械学習から最近傍法を借用することにしました。
メソッドの正式な説明のように、トレーニング段階では、すべてのオブジェクトを保存します。この場合、ピンのサージの計算値は、すべてのピンをキャッシュにロードするときにすべてこれを行います。 小さなことは、瞬時値を計算し、それをゾーン内の値と比較し、ゾーン内の値から大きく逸脱できないことに同意することです。
そのため、イベントに迅速に対応し、増加する係数の値をすばやく読み取ることができるシステムを取得します。
サージ運転カード
ドライバーと通信するには、ドライバーのアプリケーションにサージマップを表示できる必要があります-タクシーメーター。 これにより、ドライバーは、現在いる場所と、最も高価な注文を受け取るために移動すべき場所に需要があるかどうかについてフィードバックを提供します。 私たちにとって、これはより多くのドライバーが高い需要でゾーンに来てそれを解決することを意味します。
私たちは、ドライバーのデバイスはかなり弱いデバイスであるというパラダイムで生きています。 したがって、サージの六角形グリッドのレンダリングはバックエンド側にあります。 クライアントはタイルのバックエンドに来ます。 これらは、マップ上に直接表示するためのカットラスターイメージです。
Surgerマイクロサービスから定期的にピンのキャストをピックアップし、六角形グリッドのレンダリングに必要なすべてのメタ情報を計算する個別のサービスがあります。どのヘックスとサージはそれぞれにあります。
おわりに
動的価格設定は需要と供給のバランスを常に検索するため、需要の高いエリアに追加のドライバーを引き付けるなど、ユーザーは常に無料の車を利用できます。 たとえば、現在、サージを計算するための機械学習のより深い使用に取り組んでいます。 この分野のタスクの1つとして、ピンが注文に変換される確率を決定し、この情報を考慮する方法を学習しています。 ここには十分な仕事があるので、私たちはチームの新しい専門家に常に喜んでいます。
この大きなトピックの一部についてさらに詳しく知りたい場合は、コメントに書いてください。 フィードバックやアイデアも歓迎します！
PS次の出版物で、私の同僚は、機械学習を使用してタクシーの到着予定時刻を予測することについて話します。