シフト最適化への応用が期待される強化学習を用いた組合せ最適化の解法

こんにちは、調和技研研究開発部 AIコンサルティンググループの但野です。

主にAIを用いた最適化プロジェクトを担当していますので、最適化に関する課題や最新動向などをお伝えしていきたいと思います。今回は強化学習を用いた組合せ最適化の解法のうち、ナーススケジューリング問題を強化学習で解く方法に関する論文をご紹介します。

組合せ最適化とは

組合せ最適化は数理最適化の一種であり、さまざまな選択肢から最適な組み合わせを見つける問題を解決する技術です。例えば、最短ルートを見つける問題や、最適な業務シフトを作成する問題など、私たちの日常生活やビジネスにおいて幅広く利用されています。しかし、この組合せ最適化はしばしば非常に複雑な問題として知られており、実社会に適応するには様々なハードルがあります。

組合せ最適化の難しさ

組合せ最適化の難しさは、選択肢が増えるにつれて組み合わせが指数関数的に増大することに起因しています。例えば、10個のアイテムがある場合、組み合わせは約1024通りも存在します。これが100個、1000個と増えていくと、計算機にとって解くのがほぼ不可能なレベルになります。

シフト最適で考えるなら、5名の職員について3交代制で1ヶ月分シフトを考えると、その組み合わせは3^(5*30)≒3.7e+71という膨大な数となります。

従来の解決方法〜メタヒューリスティック手法

組合せ最適化の難しさについては近似解法（メタヒューリスティック手法）で対応することが一般的であり、これまでに様々な手法が研究されてきています。

メタヒューリスティック手法は、厳密な解を求める代わりに、近似的な解を高速に見つけ出すための手法です。代表的なメタヒューリスティック手法としては、遺伝的アルゴリズム、タブーサーチ、焼きなまし法などがあります。これらの手法は、組合せ最適化問題に対して優れた性能を発揮し、実用的な解を提供することができるとされています。

ただ、私自身の経験としてはメタヒューリスティック手法を用いたエンジンでも、実際にお客様の要求する精度、計算時間に届くのは難しい場合があります。実際の案件ではメタヒューリスティック手法を用いると（もちろん問題によるのですが）十数分〜数時間くらいの計算時間となることが多いですが、実際にユーザーの使用を考えると画面の前で待てるのは数分が限度ということもあります。

強化学習を使用した組合せ最適化

より効率的に解を見つける手法はないかということで、機械学習、特に強化学習を用いた解法に注目しています。

強化学習とは

強化学習とは、自分の行動によって得られる報酬を最大化するように学習するAIのことです。強化学習の基本的な考え方は、エージェントと呼ばれる学習主体が、環境と呼ばれる外界と相互作用しながら、試行錯誤を繰り返し、自らの経験から最適な行動戦略を見つけ出すというものです。強化学習は、教師あり学習や教師なし学習とは異なり、正解のラベルやデータの分布が与えられない問題に対して有効です。代表的なアルゴリズムとして、Q学習や方策勾配法などがあります。

ナーススケジューリング問題を強化学習で解く方法

ナーススケジューリング問題はシフト最適化問題の一つであり、複数の看護師の割り当て可能な勤務や休日、スキルなどの条件を満たしたシフトを作成する問題となります。今回はこのナーススケジューリング問題に強化学習を適用した事例として、M.Nagayoshiらの2022年の論文[1]（以下、文献1）の手法を紹介します。

1. 前提

文献1では、倉重らの2005年の論文[2]で用いられている構造型探索で作成されたシフトについて、シフト修正方法をベースに複数の条件を満たさない箇所についてどの勤務に着目して交換するかという交換手順を強化学習（Q学習）を用いて学習しています。

構造型探索で作成されたシフトは、1日目から順番に作成されるために、日付単位の制約条件は満たしているが、看護師単位の制約条件は満たしていない可能性がある、という特徴があります。そのため、目的関数は看護師単位の制約違反の最小化を目指す以下の式で表されます。

minΣnΣwVwn

ここで、Vnwとは、看護師nの勤務wにおける違反数を表し、シフトにおけるnへのwの割り振り回数の上限値UTnwを超えた日数とします。

また、シフト交換の手順も定められていますが、ここでは割愛いたします。

2. 状態、行動、報酬の定義

ナーススケジューリング問題を強化学習に適用するために、以下のように問題を定式化しています。

状態：前の交換日（1〜30）、全ての看護師における深夜勤、準夜勤、休日の違反数合計
行動：準夜勤、深夜勤、休日のどれを交換対象とするか
報酬：目標状態に到達した時にrt=10の報酬を与え、それ以外は０とする
目標：ΣnΣwVnw=0、または、それ以上改善できる行動がない

3. 学習方法

強化学習アルゴリズムの中で、Q学習やDeep Q-Network（DQN）などが用いられることが多いですが、論文ではQ学習を使用しています。

4. 実験と結果

参考論文では以下の設定で実験を行っています。
看護師23名
3交代制（日勤、準夜勤、深夜勤）
役職3種（看護師長、副看護師長、一般）
2チーム（A,B）
スキルレベル3種（ベテラン、中堅、新人）
制約条件
- 割り当て可能な勤務数、スキルレベル、休暇など13件
評価値
- 下記Table1にて定義

引用元：文献1

下図のFigure3は実験の結果、学習したAIがどのような手順でシフトの修正を行っているかを表しています。縦方向が職員番号、横方向が日付となっており、各ナンバリングの手順で同一日の2名の勤務を交換しています。右側の数値が各勤務の人数を表しており、赤の箇所が条件違反を表しています。Figure4はAIが組み替え終えた最終的なシフト結果を表しており、Figure3の6回の組み替えによって違反数が2件にまで削減できていることが分かります。

文献1ではメタヒューリスティックなど既存の手法との比較はなく時間や精度的な効果は分からないですが、強化学習を用いて勤務の修正ができることが示されています。

引用元：文献1