結果の理由が分かるAIで計画最適化「活用イメージ」

著者: 高久 隆史, 株式会社日立製作所

# はじめに
本稿では、「[結果の理由が分かるAIによる計画最適化](https://qiita.com/t-takahisa/items/6cb1287f97a5139bffbc)」で投稿した[Red Hat Decision Manager](https://www.redhat.com/ja/technologies/jboss-middleware/decision-manager)を利用した計画最適化の特長について、具体的なモデルケースと活用イメージを紹介します。
上記記事を読んでいない方は、先に読んで頂くことをお勧めします。

投稿一覧：
1. [結果の理由が分かるAIで計画最適化](https://qiita.com/t-takahisa/items/6cb1287f97a5139bffbc)
2. 結果の理由が分かるAIで計画最適化「活用イメージ」(本投稿)

# モデルケース(機器検査計画)
今回のモデルケースでは、大型機器の年間検査計画を最適化します。

## 背景
次の理由から、人手で実施していた検査計画の立案作業をシステム化します。
・検査対象機器の数や種類の増加に伴い、計画立案に大きな時間がかかるようになった。
・大型機器のため、1台当たりの検査費用が高く、回帰日数(検査間隔)を許容範囲内で大きくすることで、コストの大幅削減が見込める。(これまでの人手による計画では、守るべき制約を考慮するだけでも大変で、効率まで考慮できなかった。)

## 計画の概要
当該年度の検査対象の機器一覧、および、最適化計算で利用する関連するデータを入力とし、各機器の検査開始日、検査エリア(検査を実施する場所)を計算して出力します。
機器種別ごとの検査日数は予め決まっているものとします。
検査は平日のみ実施できるものとします。
１つの検査エリアで複数の機器を同時に検査できないものとします。

## 構成
今回のモデルケースでは、次の構成で実装しています。
![normal_flow.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/e2ff2bbe-e665-5934-68b4-119b4bc16396.png)

## 制約条件/評価指標(Excelルール)
今回のモデルケースでは、次の制約条件を設定しています。

■絶対制約(必ず守りたい制約)
　・1日あたりの同時検査台数制限：1日x台までしか検査できない。
　・限度日数制限：前回検査終了日からx日以内に検査しなければならない。
■考慮制約(可能な限り守りたい制約)
　・繁忙期の同時検査数考慮：特定の分類の機器は、繁忙期に検査に出す数をx台以内に抑えたい。
　・同一機器の検査体制考慮：同一種別の機器は、検査開始日をx日以上空けたい。
■評価指標(より良い組合せを算出するための指標)
　・回帰日数最大化：回帰日数(検査間隔)は大きいほど良い。(検査コストを下げる＆非稼働期間を減らすため)
　・各月の作業平準化：各月の機器種別ごとの検査数を平準化する。

**Excelルール**
![excel_rule.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/bb42bfd0-0d2f-0d6c-8521-98f9d28816a4.png)

■ルール間の優先度調整について
優先度は、レベル＋重み係数で定義し、結果はレベルごとのスコア値として評価します。高いレベルのスコア値(上の例だとHard)から順に評価され、高いレベルのスコア値が同じ場合は次のレベルのスコア値で評価される仕組みで、最もスコア値の良い組合せを最適解とします。
今回の例では、絶対制約は必ず守りつつ、考慮制約の遵守度合いと評価指標が良くなるように最適化するために、Hard、Softの2つのレベルを利用しています。

レベルは、今回の例ではHard,Softの2段階ですが、3段階以上にすることもできます。
考慮制約の遵守度合いと評価指標が良くなることを総合的に評価するのではなく、考慮制約の遵守を評価指標が良くなることよりも必ず優先させたい、という場合は、考慮制約をMediumレベルにすることで実現できます。

重み係数は、同じレベルのルールにおける優先度調整の係数になります。
今回の例では重み係数を整数で指定していますが、BigDecimal型の値を指定できます。例えば、「12.345」、「0.02」のような値も指定できます。
優先度の高いルールの重み係数を大きくしますが、各ルールのスコアの基礎値も考慮して設定します。
例えば、絶対制約#1は検査台数制限をオーバーした台数、絶対制約#2は限度日数をオーバーした日数を基礎値としており、基礎値は#2の方が大きくなりやすいため、#1の係数を大きくしています。
絶対制約の場合はどれも必ず守りたいので、Hardレベルの重み係数はあまり意識しなくていいのですが、今回は守るのが難しい入力データが来た場合に、どちらも平均的に検出できることを考慮して、調整しました。
Softレベルの重み係数は、良い計画を立てるために、よく検討して決定する必要があります。ただ、いつでも変更できるため、最初は大まかな値を指定しておいてもかまいません。

## 入力データ
計画対象機器やマスターデータは入力データとして受け取ります。制約ルールのしきい値も入力データとして受け取ることで、後から変更しやすくします。
入力データは全部記載すると長くなってしまうため、抜粋して記載します(他にも参照するマスターデータがいくつかあります)。

**検査対象機器データ**

| 機器種別 | 機器名 | 前回検査終了日 |
| :------ | :----- | :----------- |
| A       | A01    | 2017/9/15    |
| A       | A02    | 2017/4/20    |
| …       |        |              |

**定義データ**

| キー                      | 値  |
| :------------------------ | :-- |
| 1日あたりの同時検査台数制限 | 5   |
| 限度日数                  | 900 |
| …                        |     | 

**検査日数データ**

| 機器種別 | 検査日数 |
| :------ | :------ |
| A       | 16      |
| B       | 16      |
| …       |         | 

## 業務アプリケーション
今回のモデルケースでは、入力データの読み込み、制約ルールから参照する一部制約条件の評価処理、Red Hat Decision Managerの最適化計算の呼び出し、最適化計算結果の出力、スコアデータの出力などを実装した業務アプリケーションを作成しています。
最も重要、かつ、難しいAIの最適化計算自体は、Red Hat Decision Managerが実施してくれるため、業務アプリケーションのステップ数は1.2Ksと簡単な実装となっています。

## 最適化計算(Red Hat Decision Manager)
Red Hat Decision Managerの最適化計算は、以下の①～③の処理を繰り返し実行して行います。
①各機器と検査開始日&検査エリアの組合せを生成
②生成された組合せに対して、Excelルールとして定義された制約条件/評価指標のスコアを計算
③今回の組合せのスコア値と、過去の最適解の組合せのスコア値と比較し、良い方を最適解に設定

ここで①の組合せ生成のアルゴリズムや①～③の繰り返し時間(計算時間)は、Red Hat Decision Managerの設定ファイルに定義します。
最適な計算時間やアルゴリズムの設定は、データ量、制約条件/評価指標の数などに依存しますが、今回のモデルケースでは、以下の設定で利用しています。
初期解生成アルゴリズム：First Fit
局所探索アルゴリズム：Late Acceptance
最適化計算時間：60秒

```xml:今回の最適化アルゴリズムの定義内容
<termination>
	<secondsSpentLimit>60</secondsSpentLimit>
</termination>
<constructionHeuristic>
	<constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
</constructionHeuristic>
<localSearch>
	<acceptor>
		<lateAcceptanceSize>80</lateAcceptanceSize>
	</acceptor>
	<forager>
		<acceptedCountLimit>1</acceptedCountLimit>
	</forager>
</localSearch>
```

■最適化アルゴリズムについて
Red Hat Decision Managerの最適化アルゴリズムは、初期解生成アルゴリズムと局所探索アルゴリズムを組み合わせるのが基本となっています。
初期解生成アルゴリズムで1回目の組合せを生成し、局所探索アルゴリズムで2回目以降の組合せを生成していく形になります。

初期解生成アルゴリズムは、今回は最も簡単に利用できるFirst Fitを採用しています。より性能を向上させたいという場合は、初期解の組合せ方法の優先順位を指定できるFirst Fit Decreasingなどの他のアルゴリズムの採用も検討します。

局所探索アルゴリズムは、スケーラビリティの高さ、最適解の見つけやすさ、に加えて、チューニングが容易、という理由で今回はLate Acceptanceを採用しています。他にもTabu Search(タブーサーチ)やSimulated Annealing(焼きなまし法)という有名なアルゴリズムもサポートされており、必要に応じてそれらも検討します。

Late Acceptanceは、acceptedCountLimitを1(場合によっては4)に固定し、lateAcceptanceSizeのみをチューニングすればOKです。
また、lateAcceptanceSizeは、指定値が大きいほど、対象となる組合せ数が多くなり、問題を解く時間が長くなりますが、最高スコアが高くなる、という傾向が見られます。このため、入力データの規模(今回だと、検査対象機器の数、検査開始日の候補日の数、検査エリアの数)と計算時間に応じて値を調整する形になります。入力データが毎回異なるようなケースでも、入力データの規模に応じてlateAcceptanceSizeに指定する値を動的に設定するという使い方ができます。

Tabu Searchは、2つのパラメタを組み合わせてチューニングする必要があり、また、指定する値の範囲もLate Acceptanceと比べて大きな範囲でのチューニングが必要です。

Simulated Annealingは、チューニングパラメタの指定値で、入力データの規模や計算時間の他に、制約ルールのスコアを考慮する必要があり、制約ルールの追加や重み係数に変更が発生すると、そのチューニングパラメタも見直しが必要になります。

Red Hat Decision Managerの計画最適化機能は、OptaPlannerというOSSがベースとなっています。
Red Hat Decision Managerで利用できるアルゴリズム一覧や詳細仕様を確認したいという方は、[OptaPlanner User Guide](https://docs.optaplanner.org/latest/optaplanner-docs/html_single/)を参照してください。

■計算時間とスコアの収束について
計算時間は、長くすれば良い結果が得られますが、時間とともにスコアは収束してほとんど向上しなくなっていきます。目標とするスコア(最適化の度合い)や性能要件も考慮しながら、どの程度の時間とするか決めます。
単純な時間による計算終了だけでなく、特定のスコアに到達したら計算終了、一定時間スコアが向上しなければ計算終了、複数の終了条件のどれかを満たしたら計算終了、とすることもできます。

**時間経過とスコアの収束例**
![best_soft_score_statistic_example.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/18e796ce-0f47-5966-1ad9-cbfa06a49531.png)

## 結果データ
・最適化結果データは検査対象機器に対して、検査開始日、検査エリアを割り当てたデータです。
・検査エリアは、1日あたりの同時検査台数制限の数だけ用意し、各機器がどの検査エリアを利用するかを割り当てています。
・検査終了日は、検査開始日と検査日数から自動計算した値を出力しています。
・回帰日数は、検査開始日と前回検査終了日から自動計算した値を出力しています。

**結果データ(抜粋)**

| 機器種別 | 機器名 | 検査開始日 | 検査終了日 | 検査エリア | 回帰日数 |
| :------ | :----- | :-------- | :-------- | :-------- | :------ |
| E       | E09    | 2019/4/25 | 2019/5/24 | 5         | 735     |
| A       | A07    | 2019/4/26 | 2019/5/24 | 4         | 599     |
| …       |        |           |           |           |         |

**可視化した結果データ(抜粋)**
![visualize_result.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/e281ed68-3842-b99d-eaa7-8f539f959d49.png)

## スコア情報データ(結果の理由)
制約条件の遵守度合いと評価指標による評価をスコアとして出力したデータです。
今回のスコアはすべてのルールで減点方式としており、0に近いほど良い評価となります。
今回の業務アプリケーションでは、Excelファイルに出力しています。

**サマリ シート**
![score_summary.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/7d310a07-c401-3be8-0dbf-b22345291e5e.png)

**ルール＋機器単位 シート(抜粋)**
![score_rule_device.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/66028cc6-8f00-13e6-ec24-45b07605fec3.png)

**ルール＋計画開始年月 シート(抜粋)**
![score_rule_yearmonth.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/3685dbe4-578e-ebc5-c28f-b83749dae503.png)

# スコア情報データ(結果の理由)の活用イメージ
## 期待通り動作していることの確認
絶対制約、考慮制約は上の「サマリ シート」で、スコアが「0hard/0soft」となっていて、違反がない(守れている)ことが分かります。

評価指標#1については、「-(限度日数-回帰日数)」*「Excelルールの重み係数1」をスコア値としています。
上の「ルール＋機器単位 シート(抜粋)」を見ると、「スコア」列の値と「限度日数-回帰日数」の値が「0hard/-109soft」と「109」のように、どの行も一致しており、正しく動作していることが分かります。

評価指標#2については、同一機器種別の機器に対して、「-(合計機器数 / 12 - 当月機器数)^2」*「Excelルールの重み係数100」をスコア値としています。
割り算の端数は、小数第2位を四捨五入としています。
上の「ルール＋計画開始年月 シート(抜粋)」を見ると、「スコア」列の値が上記の計算式で計算した値と、どの行も一致しており、正しく動作していることが分かります。
例：-(13 / 12 - 1)^2 * 100 = -(1.08333... - 1)^2 * 100 = -(1.1 - 1)^2 * 100 = -(0.1)^2 * 100 = - 0.01 * 100 = -1 ⇒ 「0hard/-1.00Soft」と一致。

## 入力データや制約条件の課題検出
入力データの内容によっては、制約がどうしても達成できず、計画が立案できないという場合があります。
例えば以下のようなケースです。
・2019年度(2019/4/1以降)の検査計画を立案する。
・前回検査終了日は、2016/3/1。
・絶対制約#2の限度日数は900日。
このようなケースでは、検査開始日を最も早い2019/4/1に計画しても、絶対制約を守れずに計画が立案できません。(計画年度、前回検査日、限度日数の設定ミスなどが考えられます。)
スコア情報データで、どのデータが違反しているかがすぐ分かるため、こういった課題を発見しやすくなります。

**限度日数違反時のスコア情報(サマリ シート)**
![score_NG_example1a.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/ea9f9cfe-48dd-23d3-c497-00cefe28cc42.png)
**限度日数違反時のスコア情報(ルール＋機器単位 シート(抜粋))**
![score_NG_example1b.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/96761370-84af-4f5f-f9cb-c02bbd02e33a.png)

## 過去計画との比較
過去計画と新計画のスコアを比較し、過去の計画よりも良い計画になっているか確認できます。
通常の最適化計算用に作成した業務アプリケーションとExcelルールをそのまま利用して、入力データに計画済データを指定することで、過去計画のスコア情報を出力できます。
計画済データは、入力データ(検査対象機器データ)に、計画済の「検査開始日」、「検査エリア」の値を追加したものになります。

**計画済データのスコア情報出力の構成**
![planned_data_flow.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/202399f5-15b3-88e3-152b-1e79ca9dd5e9.png)

**過去計画の計画済データ**

| 機器種別 | 機器名 | 前回検査終了日 | 検査開始日 | 検査エリア |
| :------ | :----- | :----------- | :-------- | :-------- | 
| A       | A01    | 2017/9/15 | 2019/4/22 | 1         | 
| A       | A02    | 2019/4/26 | 2019/7/25 | 1         | 
| …       |        |           |           |           | 

**過去計画のスコア情報データ**
![past_planning.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/24fad34c-1b8b-d3db-8c54-fe09ccd79571.png)
**Red Hat Decision Managerによる新計画のスコア情報データ**
![new_rhdm_planning.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/624448/bb97014e-17c8-97b6-872c-ddb3aa0d941f.png)

この例では、過去計画も新計画も制約条件はすべて守れていますが、評価指標のスコアが新計画の方が良くなっており、より効率の良い計画が立てられていることがわかります。

また、Softスコアの重みをコストで調整している場合、改善されたスコアから、どのくらいのコスト削減につながったか定量的に判断できます。
例えば、回帰日数最大化による検査回数の削減や、作業平準化による残業代などの検査追加費用削減などから、Softスコア1あたり2万円のコスト削減と換算した場合、
(過去計画のスコア - 新計画のスコア) * (Softスコア1あたりのコスト削減費用)
= (10426 - 6979) * 2 = 3447 * 2 = 6894
と、「過去計画に比べて6894万円のコスト削減ができた」と推定できます。

このように過去計画と新計画のスコアを比較することで、どの程度最適化されたか定量的に判断できます。
また、万が一、過去計画の方が良いスコアとなってしまっている場合は、考慮できていない仕様があることや、計算時間＆アルゴリズムチューニングの課題などの気づきを得られます。

# おわりに
本稿では、結果の理由が分かるAIによる計画最適化の活用イメージを紹介しました。
結果の理由であるスコア情報データを活用して、どの程度最適化されたか定量的に判断することや、より良い最適化ができるように改善していくことができます。是非活用を検討して頂ければと思います。