モデル構造を一部変えれば、より複雑なシナリオに対応できる　交通運行サービスにおける強化学習の活用

うまく自動化させたいと考えている機能

細田謙二氏：ここまでが今までのサービス紹介で、ここから先が強化学習をどのように使ったらいいかを着目したところです。

（スライドを示して）この図は、1日の注文がどんどん入ってきたところの図です。これは一つひとつのブロックをMaskしていますが、1つの運行になります。1つの運行で、すでに相乗りマッチした運行も入っています。

上側に「未アサイン」とありますが、下側の各行が1車両になっていて、それを未アサインの運行車両にアサインする作業を、裏側で実は手作業でやっている状況です。なぜ手作業かというと、けっこういろいろ変数があって、それを考慮しなければいけない部分があるからです。今のところ自動化はまだできていないのですが、ここをうまく自動化させたいです。

特に考慮したいところは、オレンジで囲った部分です。この例でいうと、羽田空港に行く運行と羽田空港から帰る運行がペアになっていますが、そういった運行のペアがあると、行って帰って両方とも運行を埋められる効率が良い運行になるので、そういった運行をなるべく増やしたいというのが改善する余地がある部分ではあります。これは今は手作業でがんばって見つけながらやっている状況です。

今のところ実装した機能は手作業でやるとはいえ、少しでもその負担を下げたいところではあるので、例えば未アサインの運行をクリックしたら連続的に運行できるものをハイライトする機能も作っていたりはします。この機能自体は単純にクライアントサイドだけの単純なロジックで完結するようなものですが、そういったものを作っています。

他にもう1つ作った機能は機械学習を用いているんですが、もう少し時間が経つと、未アサインの運行に追加してシェア乗りが加わる確率を求めることができて、追加でシェア乗りをする確率が高いものをハイライトして優先的に取ることによって、在庫に限りがある場合は効率が良い運行にしています。

（スライドを示して）右側の図は、偶数日と奇数日で機能を出し分けて取れた運行数みたいなものを比較して。実際に有意に差が出ているので「この機能はありかな」と今は本番にデプロイされている状況です。

将棋のような、テトリスのような

こういった感じでけっこう考慮する要素がいっぱいあって。自分の中のイメージとしては将棋みたいなイメージもあります。「将棋みたいに」というのは、1つの運行が1つの駒みたいになっていて、どこに指すか、それがどの車両にアサインするかみたいな問題になって。

そういったところがかなり似ているのかなと思います。複雑さは将棋ほどではないとしても、組み合わせ、最適化の問題ではあるので、ある程度複雑なものなので、単純には解けないかもというところです。

あとは、どんどん注文が入ってくるので、注文が入ってきた中で密に運行をかたち作るということで、ある種テトリスみたいな感じで。ブロックがどんどん落ちてきて、それを良い感じに並べていって、縦棒があることが確実にわかっていたらそこをちょっと空けて待ってみたりするような要素もあるので、けっこう複雑な感じかなと思っています。

将棋もテトリスも強化学習を用いて解かれてはいるので、それを利用できないかを今探っている状況です。

どういった感じに探るか、調査したかというと、配車組自体は今までの配送計画問題と構造的には結局同じで。「どの注文でどの車両をアサインするか」みたいなところをなるべく効率良く最短で決めるというのは変わらないので、ここはベースにしていきたいと思っています。

強化学習×VRPのアプローチ

実際に強化学習×配送計画問題のVRPによるアプローチが今注目されているということが、調査してわかっています。今のVRPの問題もアプローチというか3つの解く方法があって。1つは厳密解を求めるようなもので、これはノード数が数十であれば求まるのですが、もうちょっといくと時間的に解けないようなところがあります。

よく用いられているのが、ヒューリスティックな手法です。これは我々も先ほどのOR-Toolsを用いて使っているのですが、これを用いれば現実的な時間ですぐに解けます。実際に有効活用されていますが、細かいところや、よりダイナミックな問題に応用できるかというと、限界があるかなとは考えています。

そこで今注目されているのが機械学習というか、学習ベースの最適化のアプローチです。その中でも深層強化学習を用いたアプローチが今注目されています。

実際に論文は直近でかなりパッと見ただけで数十本出ていて、その中でいろいろ探ってきた中で、わりと筋が良く、かつGitHubとかにもコードが載っていて使いやすそうだったモデルをピックアップして、それをベンチマークにして調査している状況です。

このモデルはGraph Neural Networkをうまく活用したモデルですが、いわゆる配送計画問題の入力があって、それをGraph Neural Networkでエンコードして、そのあといわゆる大規模言語モデルで最近よく用いられるAttentionモデルでデコードして、配送計画問題を解いているというモデルです。

それを最後に報酬ベースで学習をしているようなモデルで、右側の図の上にTSPと書いているのは、配送計画問題の一番シンプルなモデルで、いわゆる巡回セールスマンモデル問題と呼ばれるようなものに還元できるのですが、それを解いた結果です。

同じ仕組みでより複雑なCVRPと書いてあるものがありますが、容量制限付きの配送計画問題を解いたやつが右側のちょっとカラフルな図になっていて、こういった問題も解けていることが示されています。

実際にパフォーマンスもいろいろ検証されていて、既存のヒューリスティックな手法よりもパフォーマンスが出ていると示されています。「なるほど」と思って、これをベンチマークしていろいろカスタマイズしている状況です。

Graph Neural Networkについて

（スライドを示して）先ほどちょっとGraph Neural Networkに言及したのですが、これについても簡単に説明します。グラフ上の各点と各エッジみたいなものが特徴量になっていて、それらをグラフのエッジに沿って集約していきます。その集約したものを、メッセージ伝播関数というもので再帰的に次の最適のグラフの特徴量として定義して、それをどんどん重ねていくモデルになっています。

この良いところは、メッセージ伝播関数1つを学習すれば、どんなグラフがあってもグラフの大きさや構造に依存せずに適用できるのが良いかなと思っていて。そういったところを活用して、グラフの構造を抽出している仕組みになっています。

もう1個、デコーダーのAttentionとMaskについて。「ウッ……」となる図かもしれないですが、やっていることは、1つのステップごとに学習を進めています。ノードの点の最終的なグラフの特徴量を入力していくのですが、それを点をたどるごとに、同じように入力をしていきます。たどった時に、そのたどった点をMaskして、また次のものを求めるような仕組みになっています。

ノード数が増えても1つの学習モデルを学習するだけで適用できるという点で、けっこう汎用性が高いかなと思っています。

実際にGitHubのコードがあったので、それを評価してみて、どんなものかを実験してみました。ノード数20のものとノード数50のものとでそれぞれ良い結果が出ていて。

左側が今回の論文の実装で、真ん中がOR-Toolsのもので、一番右がGreedyと呼んでいるのですが、単純に1個の点を取ったら次に一番近いものをたどるノードを繰り返すようなロジックです。

Greedyのほうは交差があってぐちゃぐちゃになって、明らかに効率の悪いルートになっていることがわかると思います。OR-Toolsの結果が比較的良さそうで、それよりもわずかに強化学習を利用したものの方が良くなっています。学習としては小規模なものを利用したので、全体の結果はOR-Toolsと五分五分ぐらいでした。

そもそもちゃんと学習しているのがすごいなと思っていて、ここをスタートラインに、いろいろモデルを探っていきたいなと思っています。

強化学習に着目した理由

強化学習に着目した理由は、先ほど言ったように、より複雑で動的なシナリオへの対応ができるかなと思うからです。（スライドを示して）左の図は深層強化学習というわけではないのですが、単純な強化学習の例で、ピンクのエリアが、ちょっと渋滞を考慮して遅くなるみたいな時に最短経路を求めた結果です。

右図では示されていませんが、点が時間とともに出たり入ったり、消えたり出現したりするような状況と、あとはエッジの長さが渋滞で時間とともに変化するようなモデルで解いたものです。

これは深層強化学習を用いていて、他の手法よりも性能が上回ったという結果が示されています。そういうわけで、強化学習のポテンシャルに着目しています。

私ももうちょっとカスタマイズできるようにしたくて、先ほどベンチマークをしたモデルで基本的な構造はあまり変えず、変えやすいところでGraphの要素の特徴量を変えたり、報酬の設計を変えたり、AttentionモデルでのMaskの仕方を変えることで、けっこう複雑な問題には対応できるのではないかと今調査しています。

今回は、少しだけリアルなシナリオを設定して解いてみました。普通の点をたどって一番ルートが短くなるような問題＋すべての点をたどらなくても良い制約にして、かつ、その報酬をたどった点の数－ルートの長さみたいな感じにして。たどった点が、いわゆる注文を取って売上が上がった状態です。

ルートの長さは「そこまで行くのにちょっとコストがかかるよね」みたいなところがあって。運行効率が悪いものは無視することもやりたかったので、そういった問題も設定しました。実際に解いてみて学習も収束したので、こんな結果が出ています。

（スライドを示して）左の図の代表的な例でいうと、右上の点が独立していますが、これがわりに合わない運行で無視されたものです。逆に、下側に2つ点があって、その2つの点を取れると、点が集まってるエリアに来たほうがより多くの点をたどれるので、こういったルートになっているのかなというところがあります。他にもこういう感じで良い感じの結果が得られたので、これに関してはうまくいったかなと思っています。

ただし、報酬とかの設計で、ある程度経路の学習を進めてからじゃないと売上－コスト＝報酬というのがうまく効かないところがあるので。その報酬を時間とともに変えるのはちょっとテクニックが必要だったので、そのへんはちょっと難しいかなと感じました。

こういったところまでは調査をしていて、今は先ほどの応用例のところに向けて実装というか調査・言及を進めていっているところです。

深層強化学習は学習にすごく時間がかかる

（スライドを示して）最後に、AWSの「SageMaker」もまだ使っていなかったのですが、これを機に使ってみました。Jupyter Notebookが動く環境で普通に動きました。

深層強化学習は学習にすごく時間がかかってしまうので、例えばM2のmacでノード数50の学習をしようとすると、今の小規模のモデルでも……。1epochが336秒と書いてあるのですが、全部で100epochあって。そうすると、9時間とか10時間かかってしまう感じになるので、かなり検証しづらいです。

GPUを使えばそこが5倍とかになる、お昼に行って帰ってくれば結果がわかるみたいな状況にはなるので、これから強化学習をやっていくにはGPUが必須だなというところで、それを手軽に用意できるSageMakerは使っていきたいです。

SageMakerの他に良いところは、インスタンスのタイプの種類がいろいろあるので、強化学習のどのサイズで学習しようとしても、良い感じのインスタンスが見つかるのかなと思っています。以上です。

モデルの一部を変えることでより複雑なシナリオに対応できる

（スライドを示して）まとめとして、最初は逐次的な組み合わせ最適化をコアに、相乗りサービスを構築しました。相乗り後の運行をどの車両にアサインするべきかみたいな問題が、サービスを進めるうちにわかってきて。将棋やテトリスのような複雑さがあったので、強化学習のアプローチで探りました。

探っていく中で、深層強化学習×配送計画問題も近年活発に研究されていて、従来のヒューリスティックな手法に匹敵、もしくは超えるような結果が得られることがわかってきました。

モデルの本質的な構造は変えずに一部変えることで、より複雑なシナリオに対応できることを示しました。学習は非常に時間がかかるので、GPU必須です。AWS SageMakerで手軽に利用できました。

以上です。ご清聴ありがとうございました。