Google OR-Toolsによる最適化プロジェクト入門をスケジュールナースで解く

1.この問題は、ナーススケジューリング問題ではありません。が、この問題の発展形として、ナーススケジューリング問題があります。そこで、スケジュールナースを用いて解く方法を紹介してみたいと思います。
2.この問題に、ある制約を追加すると、ナーススケジューリング問題になります。ナーススケジューリング問題の現状と課題について、思うところを述べてみたいと思います。

スケジュールナースによる解法

シフトの設定

最初に行うのは、シフトの設定です。上記記事からは、どのようなシフトが職場上ありうるのか明記されていませんが、下記のような勤務シフト希望から推定して、連続2コマ以上のあらゆる組み合わせがシフトとしてあり得る組み合わせと解釈しました。

これに休みもシフトと考えて計7個のシフトを定義します。

フェーズの設定

フェーズというのは、スケジュールナース独自の概念で一日をフェーズという細分化された時間帯に分けます。具体的には、一日4コマの授業があるようなので、フェーズ数4となり、下のようなテーブルで定義しています。

例えば、Workというシフトは、1限から4限まで勤務するシフトを表し、PH34シフトは3限と4限を勤務するシフトになります。これらのシフトは、常に、1日に一個です。0個でも2個以上でもないことに注意してください。

タスクの設定

各講師の担当課目をタスクとして表現します。

ここで注意するべきは、空時間タスクです。全てのコマが過不足なく埋まる状況が確約されていれば不要ですが、そうでなければ必要なタスクです。（タスクは、1フェーズ中に1個というスケジュールナース内部のルールがあります。）

スタッフ名の設定

タスクのスキル設定

担当可能な教科は決まっています。

このテーブルをそのままに指定します。

予定シフト

シフトの設定のテーブルをそのまま入力します。(ただし、全てソフト制約として入力)

各日、各フェーズにおける必要講師数

必要人員数は、下記のようにテーブルにまとめます。（Excelからインポートが可能なので、月が変わっても制約を変更する必要がありません。）

各教科、上段が最大、下段が最小です。

列制約

必要講師数テーブルを参照して制約します。全てソフト制約です。

行制約

空きコマを禁止として、ソフト制約とすることで、破ったときにペナルティが発生するようにしています。このこと自体は、列制約でも代替可能です。

求解

重み2のエラー（空きコマ1個に対して重み２が発生）が31個発生していることが分かります。トータルの目的関数値としては、62となります。

同じ動作をHiGHSで行っても同じ目的関数値となりました。

HiGHSは、エジンバラ大学Julian Hall教授率いるチームのMIPソルバで、最近のベンチマークでは、SCIPを凌駕することもあるようです。

スケジュールナースは、アルゴリズム2として、HiGHSを実装しているので、同じインスタンス、同一マシン上で簡単に比較が出来ます。

解

解としては、シフト解とタスク解の2種類出てきます。両方合わせた解の出力も可能です。

モデル変更

以上は、空きコマ最小化に対するモデリングでした。今度は、出勤する日数を最小化するようなモデルを考えます。そうすると、出勤にペナルティを与えればよいことに気付きます。
次のような行制約を追加します。

上図で、レは、補集合を現します。要するに出勤に対してペナルティを与える制約です。
ソフト制約レベル3とすることにします。

モデル変更した求解

手元のチェックを変えるだけで、モデル変更が可能です。

モデル構築とモデル変更のスピード

以上の記述において、特別難しい記述は一つもなかったのではないでしょうか？。一つ一つのGUI記述は、ごくごく当たり前のことを記述しているに過ぎません。モデル変更も、2-3分で出来ました。

ナーススケジューリング問題の現状と課題

ナーススケジューリング問題化

狭義的には、看護師の勤務表作成問題だと思われていますが、実際的には、介護師の勤務表も同じ類の問題です。私的には、縦横に多数の制約が入り混じった勤務表作成問題と捉えています。上の問題では、実は、横方向の記述は一つもないことから、その意味でナーススケジューリング問題ではありません。

実際、縦方向だけの制約の場合、解くのは、難しくありませんが、横方向に制約が入ってくると途端に難しくなります。横方向の制約、例えば、連続勤務回数制約とかトータルシフト回数等を沢山入れて込むと、上記問題も、ナーススケジューリング問題になります。

ナーススケジューリング問題は、現状どこまで解けているか？

ナーススケジューリング問題は、組み合わせ最適化の一分野であり、規模が大きくなれば、組み合わせ爆発の現象が生じ、現実的な時間内に解くことは難しくなります。

それでは、現状、どの程度解けているものでしょうか？　2014年ノッティンガム大学のTim Curtoisさんは、ベンチマークテストを発表しました。24のテストインスタンスの内、発表当時に解けていたものは、半分にも満たなかったのですが、現在では、未解決の問題は、残り二つとなっています。

インスタンス名	週	スタッフ数	シフト数	発見年	備考
Instance1	2	8	1	2014
Instance2	2	14	2	2014
Instance3	2	20	3	2014
Instance4	4	10	2	2014
Instance5	4	16	2	2014
Instance6	4	18	3	2014
Instance7	4	20	3	2014
Instance8	4	30	4	2017
Instance9	4	36	4	2017
Instance10	4	40	5	2014
Instance11	4	50	6	2014
Instance12	4	60	10	2014
Instance13	4	120	8	2017
Instance14	6	32	4	2017
Instance15	6	45	6	2022
Instance16	8	20	3	2017
Instance17	8	32	4	2017
Instance18	12	22	3	2017
Instance19	12	40	5	2020
Instance20	26	50	6	2020
Instance21	26	100	8	2021	菅原システムズ
Instance22	52	50	10	2022	菅原システムズ
Instance23	52	100	16
Instance24	52	150	32

実務的によく遭遇する問題規模は、インスタンス8ですが、それでも最適化解が確定したのは、2017年です。マシンやスレッド数、さらにテスト時間に至るまで不問という状況下での解で、いわばF1レース仕立てのような環境でもそうなのですから、市井のナーススケジューリング問題をリーズナブルな時間内に厳密に解くというは、難しそうだ、ということがご理解いただけると思います。

数理的手法で問題を解く場合、連続系ソルバが必要となってきますが、Simplex法では、規模が大きくなってくると、とんでもなく時間がかかります。そこで、規模が大きくなってきたら内点法に切り替える実装が一般的だと思います。

HiGHSが並列Simplexの他に内点法による実装も備えていたため、利用しようかと思ったのですが、マルチスレッド化されていませんでした。Julian Hall教授にマルチスレッド化をお願いしてみましたが、つれない返事しか頂けなくて仕方なく自作の内点法ソルバを実装しています。具体的には、Instance20付近から、マルチスレッド化した内点法に切り替えています。

解の確認は、AutoRosterというTim Curtoisさんらがスピンアウトした会社の製品で行います。スケジュールナース解をAutoRosterのフォーマットに合わせて読み込ませ、破綻が生じていないことが要件になります。

下部にSearch Space 10^18953という記述が見えますが、問題の規模を現しています。Tim Curtoisさんにこの計算法を尋ねたところ、全てのシフトを全ての人日に割り当てたと仮定したときの推定値、ということでした。

恐らく、
(ShiftTypes+1)＾(Days x Employees)
を計算した指数部を持ってきた値のようです。

宇宙の全原子数は、10^100程度以下らしいので、解の候補空間が膨大です。で、その空間中、それよりも良い解は存在しない！、と言い切れるということは、実に素晴らしいことではないかと思います。これが、現時点における「どこまで解けているか？」に対する回答になります。

残った問題のアプローチ方法

残った問題の問題規模は、さらに巨大です。10年間未解決の問題です。これを解いたら論文が一つ書けると思うので、我こそはと思う方は、取り組んでみてください。私の場合、自作連続系ソルバは、限界を超えているので、COPT等の商用ソルバを使うことを考えています。

メタヒューリスティクス開発

INRC2の8Weeksに関して、つい最近、一番大きい120人スタッフのインスタンスが求まりました。いずれのプロジェクトもValidator付きで公開しており解を見ることは出来ます。（Windowsを英語モードにしてスケジュールナースGitHubViewerでダウンロードが可能です。）メタヒューリスティクスを開発してる方の参考になるかと思います。

MIPソルバは、万能か？

近年、MIPソルバの向上は著しいのですが、ナーススケジューリング問題でも、その能力を発揮できる機会は確実に増えています。しかしながら、決して万能という訳でもありません。具体的には、こちらをご覧ください。特に、INRC2(Second International Rostering Competition)のデータで見ると、これらの問題に対してMIPソルバは、現状において、ほぼ無力と言ってよいと思います。ナーススケジューリング問題という限られた領域に区切っても、一つのソルバで全てをこなすのは難しい、ということではないかと思います。

ナーススケジューリング問題は終わっていない

実務で、色々な勤務表に目を通していますが、厳密解が得られるのは、それほど高い比率ではないという印象を持っています。確かに、ベンチマーク群を解く能力は向上していますが、必ずしも、それが実問題を解く能力に結びついていない、ということです。ベンチマークがEU主体で開発されてきており、EUと日本で働き方が全く異なる、あるいは、実務では、より雑多な制約が入り込む、ことも要因のひとつだと思います。いずれにせよ、実用的な規模の問題において、リーズナブルな時間内に、厳密解を示せることが理想であることは変わりありません。この点において、道半ばと言わざるをえません。

ナーススケジューリング問題の課題

最終的な利用者(看護師長や管理者)にとって、アルゴリズムやベンチマークはどうでもよいことであって、自職場にとって最適・最速・最新性能のソルバをブラックボックスとして使えばよいだけです。問題を解くのは、最適化ソルバの仕事であって管理者の仕事ではありません。

難しいのはモデリング

難しいのは、仕様から制約に落とし込むモデリングです。上記問題でも見たように、スケジュールナースに落とし込むのに、何ら難しいところはなかったように思えても、例としてその実現方法を示されないと、想像するのは難しいのではないでしょうか？　

ナーススケジューリング問題のプラットフォーム　

スケジュールナースで記述する方法を紹介しました。GUIで記述し切れない場合は、Pythonで追加の制約を書くことも出来ます。ユニークなのは、GUIで記述した集合定義が自動的にPython記述に置き換わるので、最小限の制約追加で済むことです。

スケジュールナースが考える解決策

多種多様の職場があり、その分ルールも異なります。介護関係だけでも数十の違うルールがあります。もし、自職場に近いプロジェクトがあったらそれをインポートして改修する方が一から記述するよりも、ずっと早く記述できるでしょう。その意味で、スケジュールナースと拙著、および、GitHub公開が、助けになる可能性があります。

スケジュールナースは、無償版はなくなり有償のサブスク製品となりました。その月額は、看護師長、1時間の残業代の1/3~1/4位です。条件を満たすと、無料でお使いになることも可能です。

まとめ

■ナーススケジューリング問題は、終わっていません。まだまだ能力向上が必要で、そのための研究開発は、継続して行う必要があると思います。

■日本では、未だ紙やExcelで勤務表を作っておられる方が大勢いらっしゃいます。もし奥さまや知人がそういうことで悩んでおられたら、難しいモデリングを助けてあげていただけると、日本のシフトが、少しづつでも良くなるのではないかと思います。