配車組作業（6時間 / 日）を自動化した話

はじめに

NearMeエンジニアの柿野上拓真です。私は今年４月に新卒としてNearMeに入社いたしました。担当領域としては、主にデータサイエンスやMLOps、新規機能のPOCを担当しています。本記事では、私が設計・実装している自動配車システムの概要および今後の展望として深層強化学習の導入について解説します。

NearMeでは事前予約で注文を集めて、時間的・距離的に近い注文同士をAIによって自動的にマッチング（相乗り）させて乗車人数 / 移動距離を最大化しています。マッチングした注文の集合、あるいは、マッチングしなかった単独の注文をトリップと呼んでいます。車両へのアサイン（トリップに対して運行する車両を紐づけること）はトリップ単位で行います。自動配車システムでは、トリップを最適な車両にアサインし、効率的な運行計画を作成することを目標にしています。

本記事では、自動配車システムを理解して頂くためのイントロとして、システムの概要および配車組ロジック、監視手法、そして、深層強化学習の導入計画という順で述べていきます。

自動配車システム構築の背景

従来のオペレーションと課題

配車組とは、トリップを車両にアサインすることを繰り返し、運行計画を作成することを指します。配車組をする際、車両のキャパシティや運行可能時間、既にアサインされている時間的に近いトリップとの移動時間などを考慮する必要があります。従来は、配車組を人手によって行っていました。例えば羽田空港送迎では１日３回（１回当たり約２時間）の配車組を行っていました。人手で配車組を行う際、現在の運行計画および新規トリップを表示する下記の様な画面上で作業します。

従来のオペレーションには以下に挙げる課題が存在します。

人手なので工数がかかる（１日約６時間費やす計算）
担当者の技量によって作成する運行計画の良し悪しに差がある（上手な人はパズルの様にトリップを車両間で組み替えて１日でより多くのトリップを周れる「効率的な運行計画」を作る）

横軸は時間（0時〜23時）を表しており、各行が各車両の１日の運行計画に該当します。未アサイン欄にある赤色のトリップが新規トリップ（処理対象のトリップ）となります。

自動配車による課題解決

上記の課題を解決するために自動配車システムを構築しました。自動配車システムによって、配車組の工数を削減できるだけでなく、人手だと発生していた配車ミスも防ぐことができます。加えて、注文確定までの応答時間を短くすることができるので、結果的にUXの改善も期待できます。

また、「効率的な運行計画」を作成するために、「トリップの乗車人数」や「相乗りしやすさの予測値」などをもとにトリップをスコアリングし、スコアの高い順にアサインするといったルールベースのアルゴリズムも実装しました。現在は、深層強化学習を用いて、より最適な配車組を行うアルゴリズムの導入も進めています。

配車組をシステムで自動化した場合、人手のオペレーションでは発生していた配車組の属人性の高さを排除できる上に、配車組画面のUI設計・構築の工数も削減できます。そして、「効率的な運行計画」を作成することによって収益向上も期待できます。

自動配車システムの概要

自動配車システムの概略図

自動配車システムはKubernetes上にデプロイされています。また、自動配車システムは、現行のNearMeのメインシステムとは独立に開発しています。自動配車システムは以下の一連のバッチ処理を定期的に実行します。

NearMeのデータベースにアクセスして、車両データおよびトリップデータを取得します
取得したデータに対して、次の章で解説する「配車組バリデーション」および「トリップスコアリング」を行い、アサインを実行するトリップIDと車両IDの組を求めます
NearMeの配車情報を管理するAPIにアクセスし、アサイン処理を実行します（APIとのやり取りにはGraphQLを用いています）

配車組バリデーションロジック

現在の自動配車システムでは、入ってきたトリップを車両のキャパシティや運行可能時間、前後のトリップとの間隔を考慮して自動でアサイン可能な車両を割り出し、配車管理APIを叩くことで車両アサインおよび承認処理を実行します。細かい考慮事項を挙げればキリがないですが、例えば以下に示す内容を考慮して配車組バリデーションを行っています。

車両のキャパシティ（乗車定員と荷物積載容量）
車両の運行可能時間
同じ時間帯に既にトリップがアサインされていないか
既にアサインされている前後の運行との移動時間

また、各車両に対してどのサービスに属すトリップをアサインの対象にするかも設定可能です。具体的には、車両IDとサービスIDの紐付けを指定します。

※サービスIDとは、例えば「羽田空港送迎」や「那覇空港送迎」のようなサービス単位で一意のIDのこと

トリップスコアリングロジック

効率の良い運行計画を作成するためにルールベースなトリップのスコアリングも行っています。以下の要素を複合的に考慮した上で、新規トリップをスコアリングし、高いスコアのトリップから順にアサインしています。「相乗りの発生しやすさの予測値」は既にクラウド上のエンドポイントにデプロイされている機械学習の予測モデルから結果を取得しています。

人数
荷物数
前後の運行との間隔（間隔が中途半端に長いとスカスカな運行計画になってしまう）
相乗りの発生しやすさの予測値

自動配車に関するパラメータ

配車組を管理するオペレータは、管理画面のUI上からパラメータを設定・変更することによって自動配車システムの挙動を操作することが可能です。以下に設定可能なパラメータの例を挙げます。サービスによって自動配車システムに求められる要件が異なるので、将来的にはJsonLogicなども取り入れて柔軟なシステムにすることを目標にしています。

自動配車を適用するかしないかのトグル
自動配車を行う間隔（分）
何日後のトリップまで自動配車の対象にするか
自動配車の対象にする車両ID
移動時間に対する補正係数

自動配車システムの監視方法

自動配車システムの監視対象メトリクス

自動配車システムが正常に稼働しているかの指標として、いくつかのメトリクスを定義しています。メトリクスは、日付とサービスID、車両IDの組ごとにラベリングして監視しています。メトリクスの定義に関しては、実際に自動配車システムを使いながら必要な値を洗い出していくアプローチを取っています。以下はメトリクスの例です。

最後に処理を実行した時刻
処理の実行時間
処理中の内部エラーの回数
アサインに成功したトリップ数
アサインを試みたが配車管理APIからエラーが返されたトリップ数
データ自体に問題があり処理できなかったトリップ数

Prometheus + Grafanaによる監視システム

上記のメトリクスを監視するために自動配車システムでは、PrometheusおよびGrafanaという監視プラットフォームを用いています。PrometheusはPull型の監視システムです。Grafanaはメトリクスをグラフなどでビジュアライズするために使っています。余談ですが、PrometheusおよびGrafanaについては社内勉強会でハンズオンを行ったので、その際のスライドも是非ご覧ください。メトリクスは、以下の図の様にグラフ化されます。ダッシュボードを事前に作成しておけば、ブラウザからGrafanaにアクセスすれば直ぐに最新のメトリクスを見ることができます。

今後の展望

深層強化学習の導入

深層強化学習を使って配車組を最適化するロジックを研究中です。深層強化学習は、巡回セールスマン問題（TSP）や配送計画問題（VRP）において、既存のアプローチよりも良い性能を発揮できる可能性があることが示されています（論文１、論文２）。現在、私は問題設定やアルゴリズムを自動配車に応用可能な形へと拡張し、学習実験を行っております。

おわりに

本記事では、自動配車システムと効率的な運行計画作成に向けての機械学習の導入について述べてきました。個人的な感想ですが、自動配車システムの開発を通じてKubernetesやPrometheusなどのクラウドネイティブ時代の礎となる技術についても学べており、日々成長を実感できています！NearMeでは、週１で勉強会（資料）を開催しており、自身が学んだ技術について他のエンジニアに説明したり議論することを通して、互いに切磋琢磨しています！最後になりますが、NearMeではエンジニアを募集しています！ご興味のある方はぜひ以下をご覧ください。