NearMe Tech Blog

NearMeの技術ブログです

相乗り配車の注文処理について

はじめに

配車サービスの注文処理はECサイトのそれと似ています。 ECサイトでは商品を検索し、カートに入れて、注文します。 このとき、在庫が確保できていれば注文できます。 もしくは、後から在庫確保または在庫切れの通知が届く場合もあります。 その後、配送手配が行われ、お届け日などが通知されます。

配車サービスでは、商品に対応するのが、出発地と目的地を結ぶ移動手段になります。 在庫確保の流れはドライバーの予定を押さえる形になります。 このとき配車確定まで時間がかかる場合もあります。 その後、配車手配が行われ、ピックアップ時刻などが通知されます。

今回は、NearMeの相乗りサービスにおける注文処理について説明します。 当サービスでは事前予約で注文を貯めつつ、注文が入る度に最適な相乗りの組み合わせを計算して配車確定を逐次的に行えるようにしています。 このような相乗りにおいてどのようなパタンが発生するか見ていきます。

基本的な注文処理

配車における主要な注文処理は、注文申込(Apply) → 配車可否確認(Accept/Reject) → 配車完了(Complete) という流れです。 ただし、配車に至るまでに注文がキャンセル(Cancel)される可能性もあります。 図で示すと以下のようになります。

f:id:nearme-jp:20220322232136p:plain

ここで配車可否確認においては、いくつかの方法があります。 一つは、運行管理者が全体の運行スケジュールを見てドライバーの予定を押さえる方法です。 この場合、注文申込から配車可否確認まで時間がかかります。例えば、24時間以内に回答します、といった形になります。 もう一つは、ドライバーが直接配車可否を決める方法です。 特にリアルタイムの場合は、注文が入ると近くの車両のドライバーアプリに通知し、そこで配車可否が決定されます。 その他、様々な情報を駆使して自動的に配車可否を決めたり、配車率が高ければ投機的に配車可能を伝えることも考えられます。

ここまではフローとしてはシンプルかと思います。

相乗りを考慮した状態遷移

上記の基本的な注文処理において、複数の注文が入ってきたときに、各注文と複数の注文を束ねる運行(Trip)の状態遷移について説明します。

まずは複数の注文が相乗りしながら配車確定していく流れを次図に示します。

f:id:nearme-jp:20220323104236p:plain:h460

注文処理のステップは以下のようになります。

  1. 何もない状態からスタートします
  2. 注文Aが入ると(Apply A)、仮の運行1(Trip1)が生成されます。
  3. 注文Bが入ると(Apply B)、仮の運行1の下で注文Aと相乗りになります。
  4. 注文Aを配車確定します(Accept A)。運行1は注文Bがまだ配車確定されていないのでまだ仮の状態です。
  5. 注文Bを配車確定します(Accept B)。運行1の配下の注文は全て配車確定されたので、運行1はある種"確定"の状態になります。
  6. 一方、3の状態から運行単位で配車確定して(Accept Trip1)、注文Aと注文Bを同時に配車確定することも可能です。
  7. 注文Cが入り(Apply C)、3つの注文がまとまった相乗りが成立します。注文Cはまだ配車確定していないので、運行1はまた仮の状態になります。

配車確定前に注文が貯まりながら、相乗り処理が逐次的に行われていることが分かります。

今度は、注文にアサインされた運行が切り替わるパタンについて見てみます。

f:id:nearme-jp:20220322234138p:plain:h260

  1. 注文Aと注文Bが、それぞれ配車確定前に相乗りになった状態です。
  2. 注文Dが入ると運行が2つになり、注文Bは注文Dとくっつきます。このとき、注文Aと注文Bの対よりも、注文Bと注文Dの対の方が効率の良い運行で、かつ、注文Aと注文Bと注文Dの3つでは相乗りが成立しない状況になっています。
  3. 注文Dを配車不可(Reject)すると、再び注文Bは注文Aとくっついて、運行2は消滅します。

配車確定前に貯まった注文同士で、ダイナミックに相互作用しているのが見てとれます。

一方、素朴に運行管理者が予定を押さえる場合は、運用の煩雑さから"配車確定後の注文は別の運行に切り替わらない"という縛りを加えることが可能です。この場合は次のようになります。

f:id:nearme-jp:20220322234402p:plain:h220

  1. 注文Aが単独、注文B、Dが相乗りで配車確定になった状態です。
  2. "配車確定後に別の運行に切り替わらない"場合、注文Dがキャンセルされると、注文Aと注文Bが別々の運行のままになります。

先ほどは注文が却下/キャンセルされると運行が1つになったところが、今回は運行が2つのままになっているのが分かります。なお、この縛りは設定によって変えることができ、ここは運用の煩雑さと配車効率のトレードオフになります。

時間確定処理

事前予約型の相乗り配車では、先の注文申込(Apply) → 配車可否確認(Accept/Reject) → 配車完了(Complete) の処理フローにおいて、配車確定後にさらに時間確定(Finalized)が追加されています。ピックアップ時刻はある程度時間幅を持たせることで相乗りが成立しやすくなりますが(参考)、逆に、ユーザーにとっては予定が立てづらくなって不便です。そこで、あるタイミング、例えば、乗車の1日前のところで、ピックアップ時刻を確定、もしくはその時間幅を短縮するという時間確定処理を行います。

f:id:nearme-jp:20220323000345p:plain

時間確定処理が入った処理フローも相乗りを考慮して見てみます。

f:id:nearme-jp:20220323001126p:plain:h400

  1. 注文Aと注文Bが、それぞれ配車確定前に相乗りになった状態です。
  2. 運行1を時間確定します(Finalize Trip1)。時間確定処理は注文単位ではなく運行単位で行います。このとき、各注文のピックアップ時刻の時間幅が短縮されます。完全に時刻を確定させると追加の相乗りがほとんど発生しなくなるので(前後にくっつくか、全く同じルートの注文にくっつくかのみになります)、実用的には少し時間幅を残します。そして、ユーザーには確定したピックアップ時刻を通知します。なおここで、追加の相乗りがあってもピックアップ時刻が早まることはないようにしています。
  3. 注文Cが入り、注文Aと注文Bと相乗りします。
  4. 再度、運行1を時間確定します(Finalize Trip1)。このとき、注文Cにピックアップ時刻を通知するとともに、注文Aと注文Bにおいてピックアップ時刻が変更した場合は、それぞれそのユーザーにその時刻を通知します。
  5. 注文Bがキャンセルされると、少し非効率になりますがピックアップ時刻は変わらずに注文Aと注文Cが運行1に残ります。

時間確定処理後も、よりきつい時間制約の下で追加の相乗りが発生しているのが分かります。

別の運行に渡す処理

最後に、ある注文を今の運行から剥がして別の運行に渡す処理(Skip)についても見てみます。 この処理は、ある注文に対して特定の運行にアサインさせないという制約を加えることで実現します(参考)。 追加の相乗りがあったけど、諸々のスケジュールの関係でこの運行では行けないので、別の運行に注文を渡してとってもらうことを想定しています。

f:id:nearme-jp:20220323001444p:plain:h300

  1. 注文Aと注文Bが異なる運行でそれぞれ配車確定していて、追加の注文Dが入って注文Bと相乗りになった状況です。
  2. 注文Dを今アサインされている運行2から剥がすことにより(Skip D)、注文Aと相乗りになります。
  3. さらに注文Dを今アサインされている運行1から剥がすと(Skip D)、既に剥がした運行2とはくっつけないため、今度は独立した運行になります。

より複雑な制約条件の下、逐次的に相乗り処理が行われているのが分かります。

おわりに

事前予約型の相乗り配車サービスの注文処理における様々な状態遷移を見てきました。 注文申込、 配車可否確認、キャンセル、時間確定、別の運行に渡す処理などの操作によって、 単体の注文の状態だけでなく、別の注文と相互作用して様々なパタンが発生することを示しました。 また、処理過程において、ピックアップの時間幅を短縮したり、特定の運行にアサインさせないなど、制約条件が細かく変わっていくことも示しました。 このようなパタンを緻密に管理することでサービスが実現されていることが伝わればと思います。

最後になりますが、NearMeではエンジニアを募集しています!まだまだ多くの可能性が潜んでいる領域です。興味を持った方はぜひ以下から応募いただければと思います。

Author: Kenji Hosoda

このエントリーをはてなブックマークに追加