配車のルーティングにおいて、最適化のアルゴリズムはコアとなる機能ですが、 これに相対して開発する必要があるのが、データベースを絡めた永続的な状態管理です。 事前予約型の空港送迎の相乗りサービスでは、注文が入る度に逐次的にルーティングを行なっていて、注文全体で時系列に変化する"ルーティングの状態"があります。 ここではその状態管理についてアーキテクチャを交えて解説します。
サービス構成
NearMeで構築している配車ルーティングは次の二つのサービスに分かれて処理されています。
一つは、ルーティングサービスで、最適化のアルゴリズムを提供します。データベースとは直接はやり取りせず、永続的な状態を持たずに、入力を受け取って出力を返します。ただし、地点間の最短経路の移動時間を取得するために地図サービスとは連携しています。
もう一つは乗車サービスです。これはデータベースとやり取りして、乗車の諸々の状態を管理します。ユーザー、ドライバー、オペレータからの様々な操作を受けます。そして、ルーティングサービスを介して、現在の"ルーティングの状態"から次の"ルーティングの状態"を算出し、データベースを更新します。
サービスを分けた理由として、まず、それぞれで得意な言語を利用したかったからというのがあります。NearMeでは基本的にTypeScriptで書いていますが、ルーティングサービスは数理最適化のライブラリのためPythonを利用しています。次に、ルーティングサービス単体でCPUに最適化されたマシンでスケールさせたかったというのもあります。乗車サービスではボトルネックはデータベースになる一方、ルーティングサービスではボトルネックはCPUになるからです。また、ステートレス、ステートフルで境界を分けた方が整理しやすいというのもあります。結果的に、コードベースはそれぞれ大きくなり、この分割によって見通しはよくなっています。
状態遷移
配車のルーティングでは、どの注文とどの注文をマッチングさせるかを決めます。各運行において、どの順番で乗車させて、どの順番で降車させるかも決め、複数の経由地からなるルートも算出します。あまりにルートが長すぎるとマッチングは非成立となります。また、車両に乗れる人数以上を乗せることになったり、あらかじめユーザーが決めた希望出発/到着時間から離れてもマッチングは非成立となります。
一般にこれは組合せ最適化問題を解くことになり、扱う要素数が増えると爆発的に計算量が増えます。そのため、組合せ最適化問題に帰着する前に、まず、適切な数の注文数に絞ります。ただし、絞り込んだ注文とそれ以外の注文はなるべく互いマッチしないようにします。例えば、空港送迎の相乗りサービスでは、初めに大きく時間と空間で絞り、時間として日付を、空間として配車サービスのマルチテナント化についてで説明した「羽田空港送迎」のようなサービスのエリアを用いています。この絞り込みはデータベースのインデックスにより高速に行われます。
絞り込みの後は、注文が入る度に、また注文がキャンセルされる度に、配車のルーティングを行います。このとき、前回のルーティング結果を保存しておいて、それを基に最適化アルゴリズムを用いて次のルーティングを算出します。なお、アルゴリズムの中では、出入りする注文に対してさらに"近い"注文に絞って、山登り法的に組合せ最適化問題を解いています。
ここで各注文の配車可否という状態が加わると、また性質の異なる状態を考慮する必要があります。注文が入ると、運行管理者またはドライバーに通知され、そこでルートや在庫状況などを考慮して配車可否を判断します。特に事前予約の場合、配車可否までに多少時間がかかることもあります。したがって、その間に注文が入ったり、キャンセルされたりする可能性があります。このとき、配車可能な注文だけからなる"ルーティングの状態"と、配車可能な注文と配車未決定の注文からなる"ルーティングの状態"に枝分かれします。前者を"正規の状態"、後者を"ドラフトの状態"と定義します。ユーザーやドライバーには"正規の状態"が提示されますが、承認者には"ドラフトの状態"が提示されます。"ドラフトの状態"は、正規の状態から派生し、いくつかのステップを経て、正規の状態にマージされます。各運行においてそれに紐づく注文全てが承認になった時、それらの注文がマージされます。逆に、ここで枝分かれできないと、配車可否の間に追加の注文を受けられず機会損失になります。
ルーティングの各ステップにおいては、より良い最適化のため、注文同士はくっついたり、離れたりします。一旦くっついてても、他の注文とくっついた方がよい場合は離れることもあります。更新の影響範囲を考えると、入力した注文とそれにマッチした注文だけでなく、絞り込んだ注文全てにおいて、どの注文も変化する可能性があります。ルーティング結果の保存の際は、この変化した部分を抽出して差分更新しています。この幅広い影響範囲は後述するロック処理にも関わってきます。ただし、この運行跨ぎの注文の再配置はオペレーションが煩雑になる懸念もあり、配車未決定の注文に限定できるようにもしています。
補足として、このような逐次的な方法ではなく、あるタイミングで一気にルーティングを行うバッチ型の方法もあります。バッチ型の方が状態管理としてはシンプルです。また、逐次的でも現実的に妥当な解は得られていますが、バッチ型で一括で時間をかけて問題を解いた方がより良い解は見つかる可能性はあります。デメリットとしては、配車可否の判断がバッチのタイミングになってしまうので、ユーザーは配車可否が判明するまでより待たされることになります。また、バッチの後に入ってきた注文を処理するには、また別の仕組みが必要になります。
ロック処理
データベースの処理において注意しなければならないのが、データの整合性を保つためのロック処理（排他制御処理）です。 注文やキャンセル、配車可否といった非同期のリクエストを、 "ルーティングの状態"という共有したリソースに対して行う際にロックが必要になってきます。
簡単な例として、同じ注文に対して、ユーザーのキャンセルと運行管理者の注文承認を同じタイミングで行うとどうなるでしょうか。 本来、注文承認はキャンセルが行われたら処理できないというバリデーションで弾かれます。 ロックがないと、キャンセルと承認が同時にリクエストされたとき、それぞれまず同じ状態の注文を参照する可能性があります。この場合、未承認の注文です。その後、キャンセルリクエストが処理され、注文の状態がキャンセルになります。追って承認のリクエストが処理されると、このリクエストは未承認の注文として元の注文を参照しているので、先のバリデーションが効かず、注文の状態を承認にしてしまいます。ユーザーはキャンセルしたと思ってるのに、注文は承認されて処理されてしまうことになります。ロックがあるとこのようは不整合を防ぐことができます。
ロックの方法には、悲観的ロックと楽観的ロックがあります。悲観的ロックは、共有するリソースをロック対象として指示し、他リクエストの読み取りを防ぎます。先の例だと、キャンセルと承認が同時にリクエストされたとき、どちらか一方が先に処理されて状態を更新した後、もう片方が処理されます。キャンセルが先に処理された場合、非承認のリクエストは、キャンセルの状態を読み出すことになるので、バリデーションで弾かれます。楽観的ロックは、一旦、投機的にそれぞれのリクエストを実行しておいて、状態更新時に読み出した状態から変化があれば、その処理を破棄します。
悲観的ロックか楽観的ロックかという話は込み入るのですが、基本的には、悲観的ロックの方が単純で扱いやすいと考えています。楽観的ロックでは、変化を検出するためにバージョンを各レコードに追加するとともに（状況によってはタイムスタンプでも代替可能です）、データが競合し更新に失敗した時のリカバリ処理を考える必要があります。特に、リカバリ処理を自動で行うにはキューのシステムが必要で、こちらも注意深くケアする必要あります。競合が稀にしか起きず自動リカバリが必要ないとき、どうしてもスループットを上げたいとき（投機的実行が増えるのでシステム負荷は上がります）、また、データベースの特性上悲観的ロックが使えないときなどに利用されると思います。後から楽観的ロックを実装するというのも選択肢としてありだと思います。
前置きが長くなりましたが、注文全体で時系列に変化する"ルーティングの状態"の場合も、注文が入る度、キャンセルされる度にロックが必要です。前述したように、粒度の大きな絞り込み以降、どの注文が変化するかは基本的に解いてみないと分からないので、悲観的ロックの場合は、その絞り込みのところでロックをかける必要があります。実際には、ロック用のテーブルを用意し、日付xエリアをキーとするレコードを作成してロックをかけます。なおこの時点で、最適化アルゴリズムの処理速度からスループットの上限が決まってしまいます。現時点で、この値は問題ないレベルですが、もし限界が来たら更なる時間分割、エリア分割して、ロックの粒度を細かくする必要があります。
他方、"ルーティングの状態"に対して個々の注文でバージョン管理するような楽観的ロックを行うことも可能です。しかしこの場合、新たな懸念があります。例えば、新規注文とキャンセルが同時にリクエストされたとき、新規注文は、キャンセルが行われた運行に対してマッチできたところが、マッチされない可能性があるのです。キャンセルされてない"ルーティングの状態"を基に次の"ルーティングの状態"を求めているためです。このとき、前述した影響ありうる注文セット全体を悲観的にロックする場合はどうでしょうか。キャンセル→新規注文の順番で処理された場合は当然、新規注文はキャンセルが行われた運行に対してマッチします。新規注文→キャンセルの順番では、新規注文は一旦その運行にマッチしませんが、次にキャンセルが行われたときに、キャンセルの注文に"近い"注文で再配置されるので、先ほどマッチしなかった新規注文が今度はマッチする可能性があります。全体の最適化という観点では、このような悲観的ロックに分があると考えられます。
おわりに
NearMeで構築している配車ルーティングの状態管理について説明しました。サービス分割、データの絞り込み、逐次的な最適化、ドラフトの分岐、運行を跨いだ注文の再配置、ロック処理など、様々な考慮が必要でした。そして、それらがルーティングの性能に関わっていることを示しました。
最後になりますが、NearMeではエンジニアを募集しています！配車ルーティングの最適化についてさらに詳しく知りたい、また、自分ならもっと最適化できると思われた方はぜひ応募いただければと思います。
Author: Kenji Hosoda
