塾講師問題を再考

 GitHub化したサンプルプロジェクトを何にしようか？考えていて、塾講師問題が身近でよさそうだ、と思い付きました。Readme.mdの内容を考えてみます。

オリジナルの仕様を眺めてみました。

Google OR-Toolsによる最適化プロジェクト入門 - Qiita

プロジェクトは、以下をいじります。

＞空きコマの数を最小化したり、同じシフト数でも出勤する日数を最小化するようなモデル

これについて考えてみます。

＞空きコマ数最小化

下で空きタスクにソフトレベル１を設定しています。

現在の設定は、

ですが、予定の重みを7として予定が変更されないようにします。これで、ほぼ、空きコマ数最小のモデルとなります。

これで、UB=62が求まりました。つまり、31個の空きコマは必然です。

しかし、アルゴリズム２で求解するとUB=61になっています。

これは、予定が変更されていることによります。アルゴリズム２は、完全な最適解を求めるまで終了しません。（アルゴリズム１は、準最適解です。）いずれにせよ、予定の重みをより重くすれば、予定が変更されることはなくなり、上と同じになるはずです。

アルゴリズム３でも同じUB=61となりましたが、解の出方は違います。別解があるということです。

＞出勤する日数を最小化

制約を追加します。休日でない＝出勤です。出勤にペナルティを与えるものとします。

予定および空きコマペナルティを排するために当該部をアンチェックして、求解します。

結果は、全て同じUBとなりました。最適解が求まりました。

タスク解

シフトとタスク解

着目して頂きたいのは、モデル変更のスピードです。Qiitaの仕様を読んで、モデル変更して求解、最適解を得るのに、2-3分で完了しました。ナーススケジューリング問題は、毎月モデリングしているようなもので、月々に何らかの変更が入るのが常です。なので、大枠は決まっているけれども、少々の変更なら、直ぐに手元で変更できることが大事な要件です。本プロジェクトは、ナーススケジューリング問題ではありませんが、組み合わせ最適化の一例であり、モデリング方法は似ています。