はじめに
NearMeでは相乗りシャトルのサービスを展開していますが、その配車ルーティングを実装してきて気づいた点があります。 クラウドの基盤技術である"コンテナオーケストレーション"と似た構造がある点です。
コンテナオーケストレーションは、コンピューティング環境で動くアプリケーションをコンテナと呼ばれる単位で管理し、コンピューティングリソースを適切に割り当て、協調的に動作させる技術です。
コンテナオーケストレーションを実現する代表的なツールとしてKubernetes(クーバネティス、以降k8sと略します)があり、ここでは特にk8sと配車ルーティングとのアナロジーについて考えてみます。
構成要素
k8sでは、コンテナ・ポッド・ノードという階層的な構成要素があります。コンテナは単独のアプリケーションを動かす実行環境です。ポッドは、複数の密接に関連したコンテナをまとめたものです。コンテナはその共有リソースとともにポッド単位で管理されます。ノードは一つの物理サーバー、または、仮想マシンを表していて、複数のポッドがその上に配置され実行されます。
一方、配車ルーティングでは、乗客/荷物、注文、車両という階層的な構成要素があります。乗客/荷物は最小単位の積載物です。注文は、複数の乗客/荷物に対する運送を要求します。車両は、特に相乗りを許すと、複数の注文を束ねて運行します。
スケジューリング
k8sでは、各ポッドを様々な制約や評価を考慮して最適なノードに割り当てるスケジューラがあります。例えば、ポッド作成時に、リソースに空きのあるノードを探し、ノード間でリソース使用率に偏りがないように割り当てます。また、スケジューラはプラグイン的に拡張でき、ポッドを削除して再スケジュールするものもあります。
一方、配車ルーティングでは、各注文を様々な考慮のもと車両に割り当てるスケジューラがあります。例えば、注文が入ると、迂回時間や待ち時間、車両のキャパなどから配車可能な車両を探し、全体としてルートが短くなるように割り当てます（参考）。このとき、既存の注文も車両を跨いで再配置することもあります（参考）。
オートスケール
k8sでは、リソース不足でポッドがスケジューリングできない時に自動的にノードを追加することが可能です。逆に、負荷が低い時にノードを自動的に削除することも可能です。
一方、配車ルーティングでは、注文が増えていくと必要な車両も増えていきますが、特に事前予約型の注文の場合、"仮想的な車両"を自動的に増やして注文を割り当てることが可能です。後からその仮想的な車両を実際の車両に置き換えます。注文のキャンセルがあって車両が必要なくなった場合はその車両を減らします。
ただし、k8sではノードのみならずポッドもスケールしますが、配車ルーティングでは一般に車両のみがスケールします。一応、注文のスケールは保険的に複数の車両を確保するような状況として捉えられるかもしれません。
リソース管理
k8sでは、CPUやメモリなどコンテナが必要とする各リソースの量を指定することができます。そしてポッド作成時に、ポッドに紐づくコンテナのリソースの量を集計し、リソースが確保できなければポッドはそのノードに割り当てられなくなります。
一方、配車ルーティングでは、乗客や荷物が占有する座席数や容量があります。小さい子供や大きな荷物など単体で占有量が異なるものもあります。車両には、座席やトランクの最大数/量があり、注文が要求する数/量を確保できなければその車両に割り当てることはできません。
ただし、k8sのリソースの量には最小と最大を指定できますが、配車ルーティングの占有量の指定は一般に最小=最大となります。
アフィニティ
k8sでは、ノード上のポッドの配置の条件を、特にアフィニティと呼ばれる方法で細かく指定することができます。例えば、ノードとポッドそれぞれに任意のラベルをつけることができ、ポッドを特定のラベルがついたノードに強制的/優先的に割り当てたり（ノードアフィニティ）、特定のラベルがついてないノードに割り当てたりすることができます（ノードアンチアフィニティ）。また、ポッドを特定のラベルがついたポッドを含むノード（やゾーンなど）に共存させたり（ポッドアフィニティ）、避けたりすることができます（ポッドアンチアフィニティ）。さらに、ノードアフィニティとはある種逆に、特定のノードに特定のポッドのみを割り当てる機構もあります（ノードのテイントとポッドの容認）。
一方、配車ルーティングでは、例えば、注文に、チャイルドシート、ペット、車椅子などの要求があれば、特定の車両に割り当てた方がいいことがあります（車両アフィニティ）。また、営業区域の事情で、ある注文を特定の車両には割り当てないようにしたいこともありそうです（車両アンチアフィニティ）。さらに、なるべく親しい人同士で相乗りしたい（注文アフィニティ）、もしくはしたくない（注文アンチアフィニティ）といったことも考えられます。特定の注文しか受け付けない車両もあるかもしれません（車両のテイントと注文の容認）。
おわりに
コンテナオーケストレーション、特にk8sの構成要素やスケジューリング機構をはじめとする幾つかの要素技術において、相乗りシャトルの配車ルーティングとのアナロジーを見出してきました。
このアナロジーから、別分野ですが洗練されたk8sからの洞察を得て、配車ルーティングの実装の参考にしたり、概念を整理できればと思っています。実際、アフィニティの概念などはk8sから輸入して実装したところもあります。また、ここでは紹介してないですが、k8sの宣言的な作りも参考にしてきました。今後、k8sの自律分散的な挙動も参考にできるのではと考えています。
最後になりますが、NearMeではエンジニアを募集しています！カジュアルな面談も可能ですので、お気軽にご連絡ください。
Author: Kenji Hosoda
