• 強化学習
• スケジューリング
• 工程最適化
• 経路最適化

ソリューションについて

ソリューションの概要

『組合せ最適化ソリューション』は、要素の組合せによって生じる大量の選択肢の中から最も良いものを選択するという「組合せ最適化問題」を、強化学習技術を使って解決することを目指したソリューションです。

組合せ最適化問題の具体例としては、調理工程のスケジューリング、配達経路の選択、工事計画の策定、積荷配置計画の策定、製造ラインの工程スケジューリングなどさまざまなものが想定されます。これらの組合せ最適化問題に一般的な手法ではなく、強化学習を用いるメリットとしては、一度モデルを作ってしまえば最適化に要する時間を短縮できること、汎用的な問題に対応しやすいことの２点が挙げられます。

組合せ最適化問題とは

組合せ最適化問題とは、与えた条件下で最も良い目的値を得られる組み合わせを選択する問題です。ここでは、調理工程のスケジューリング問題、配達経路の選択問題、運行ダイヤへのバス割当問題、工事計画の策定問題の３事例を使って説明します。

調理工程のスケジューリング問題

スケジューリング問題の例の一つに、調理工程の最適化があります。例えば、調理者１名が全部で4つの料理を作る場合には、各料理に“野菜を切る” “コンロで煮る”といった決められた調理手順があり、さらに調理器具としてコンロ、オーブン、包丁、まな板、炊飯器を1つずつ使用できることなどが想定されます。調理工程の最適化問題は、そうした制約条件のもとで、調理終了までの時間を最も短くする調理工程を選択する問題です。

制約条件を考慮すると、最適な調理工程は下図のようになります。この程度の大きさの問題なら簡単に解くことができる一方で、さらに多くの料理を多人数で作る場合などには、組合せの数が増え、より問題の難易度が上がっていくことになります。

配達経路の選択問題

複数トラックでの配送ルートを決定する配達経路の最適化も、組合せ最適化問題の一つとして挙げられます。その問題設定は、配送対象の住宅に対して複数トラックで配送するという内容になり、制約条件としては荷物のお届け日時の指定があるほか、トラックに一度に詰め込める積載量制限などが考えられます。配達経路の最適化問題は、そうした制約条件を満たして配達時間を最小化する配達順序を決定する問題であり、配達対象の住宅の数が増え、トラックの台数も増えるなど、問題がより大きくなる場合には最適化が難しくなっていきます。

工事計画の策定問題

工事計画も最適化問題のひとつです。例えば、不整形な土地を区画整形する圃場（ほじょう）整備計画を策定する際には、地形による制約条件を多数加味しながら最小コストでの工事計画を策定する必要があります。制約条件の例としては、土地の高低差による各建機の走行可能範囲、建機の使用台数に応じた可動範囲、建機の積込ステーションのスペースなどがあげられます。その中で、土の掘り出しの作業時間、土の運搬にかかる往復時間なども加味しながら、コストを最小化のためにはどのような建機をどのような順番で何日間用いるべきるかを決めることは難しい問題です。

工事を行う土地の大きさ、形、高低差や使用可能な建機の利用条件が複雑化するにつれ、工事計画の策定の難易度は高くなります。

これらの例の他にも、アルバイトのシフト計画、船舶の積荷配置計画、製造組立ラインでの工程スケジュールといった問題も考えられますが、これらは、これまで「数理最適化」と呼ばれる技術を使って解かれることが一般的でした。数理最適化による解法では、問題に応じて職人技とも呼べる定式化やアルゴリズム開発が必要になることが多く、開発に時間がかかる傾向がありました。また、せっかく開発したアルゴリズムが、問題のほんの少しの変更で使えなくなってしまうケースもあり、問題設定の変化に対するロバスト性に課題がある場合があります。

強化学習について

強化学習とは

『組合せ最適化ソリューション』で採用している強化学習とは、エージェントと呼ばれる主体が、試行錯誤を通して最適な行動を実現する機械学習手法の一つです。エージェントは、一連の行動を通して得られる報酬を最大化するように学習することで、自らの行動を最適化していきます。

強化学習のイメージを掴むため、ロボットの歩行制御を例として、ロボットができるだけ遠くまで歩けるよう制御を実現したいケースを考えた場合、強化学習の枠組みでは、ロボットがより遠くに歩けるほどより多くの報酬を与えます。機械が試行錯誤を通してより大きな報酬を得られるよう行動を学習していくため、学習するにつれてロボットはより遠くまで行ける良い歩き方を身につけていきます。良い歩き方を学習しさえすれば、似たような状況においては短い推論時間で歩行制御を行えるようになります。

仮にロボットの歩行制御を教師あり学習で行うとすると、ロボットの右足や左足をどう動かすのかといった行動一つ一つに良い/悪いといったラベルをつける必要がありますが、一方、強化学習では、歩いた距離という一連の行動を通して得られる報酬を設定すれば、あとは機械が自動で制御機能を獲得していくことが可能となります。

強化学習×最適化問題のメリット

近年のディープラーニングの発展に伴い、組合せ最適化問題でも、強化学習とディープラーニングを組み合わせた深層強化学習を用いて解くことが行われるようになってきており、応用例も出てくるようになりました。

最適化問題に強化学習を適用することのメリットとしては２点挙げられます。１点目は、最適化問題が大きくなっても、強化学習では最適化に要する時間（推論時間）が大きくなりにくいという点です。強化学習では、学習データを元にして様々なパターンを機械が自動で学び、その学んだことを生かすことができるため、推論時に問題を解くためにかかる時間がそこまで長くならないことが期待でき、それを示す研究も報告されています。その結果、頻繁に状況が変わり、その度に最適化が必要になるような状況においては強化学習を適用する意味が出てくると考えられます。

２点目は、強化学習を用いると様々な最適化問題に対してほぼ一つの枠組みでアルゴリズムを構築することが可能になる点です。数理最適化アルゴリズムでは問題ごとに職人技による定式化やアルゴリズム開発が必要になることが多い一方、強化学習では共通したフレームワークや技法を使った上で、必要に応じて問題ごとにチューニングすることで対応できます。強化学習を適用するコツとしては、学習を促進する報酬の設計、最適化途中の価値関数の設計、高速なサンプリングのための実装上の工夫といった事があげられます。

組合せ最適化問題への3つのアプローチ

組合せ最適化問題を解くにあたっては、大きくは、ルールベース、数理最適化、強化学習の３つのアプローチが考えられます。どれかが優れているということではなく、解決したい問題の内容や難易度に合わせて使い分けることが重要です。それぞれの特徴を簡単に示すと次のとおりです。

ルールベースは、高速かつ低負荷な処理が可能な反面、文字通り、そのルール・ロジックを定義する必要があるため、制約条件が多い複雑な問題への対応力は低い手法です。そのため、比較的シンプルな組合せによる問題で、かつ説明性が求められるような場合での利用が向いています。

数理最適化は、ルールベースよりも複雑性への対応力がやや高い手法です。一方、用いるデータ量に応じて計算処理時間と負荷がかかる特徴があるため、制約条件がある程度ありながらもロジックが組める、中程度の複雑性をもつ問題への利用が向いています。

強化学習は、複雑な問題への対応力が非常に高く、計算処理時間も短く済む点にメリットがあります。ただし、シミュレータなどを含めた開発期間に時間がかかる上、説明性が低い特徴があります。そのため、中長期的なスパンで解決が必要な複雑性の高い問題、かつ説明性がそれほど求められないケースでの利用が向いています。

ソリューションご提供にあたって

本ソリューションは汎用的にご利用いただけるAIプロダクトとして販売するものではなく、貴社のビジネス課題をヒアリングの上、オーダーメイドで開発いたします。

Laboro.AIでは、強化学習を使った取り組みに積極的に取り組んでおり、工程スケジュール最適化などの領域で実績を積んでいます。本ソリューションの提供においては、問題の性質や条件に合わせ、強化学習に加えて適宜、数理最適化の技術も応用しながら高いビジネス成果へとつなげていくことを目指します。

（※ なお、組み合わせ最適化問題を強化学習で解く前提として、シミュレータ環境の設計が必須になる場合があります。シミュレータ環境の実装方法、最適な技術選択、問題に応じた技法のチューニングについては、 詳細をお伺いした後、弊社からご提案させていただきます。）

活用シーン

ソリューションのポイント