居酒屋シフトモデル化いろいろ (1. 「マス目埋め」タイプの適用)

数理最適化問題のタイプ分けのご紹介が一通り終わったところで、 これらを用いてよく実務で現れる数理最適化のモデルの組み立て方について具体的に解説しましょう。 オフィス街でランチ営業しているある居酒屋のアルバイトスタッフ 12 人の 勤務シフトを決定する問題を解いてみます。彼らの勤務は一日 4 時間で出勤時間は 朝 9:00 から夕方 16:00 の間とします。

一時間ごとに、現場を回すために必要な人数がおおむね次のようにわかっているとします。 朝方は 4 人、昼時に向けてじわじわと忙しくなり、 昼時に 8 人というピークを迎え、そして同じ形で減衰しています。

結果のシフト表は人と時刻のマトリックス、他ならぬマス目ですから、 まずは「マス目埋め」タイプとしてモデル化してみましょう。 「マス目埋め」タイプの紹介記事 での各列のインデックスを「週」を「時刻」と解釈すればほぼモデルは同じ。 勤務は 1 種類(するかしないか)、なのでかなり単純です。

果たして結果は? 数理最適化では勤務する/しないを 0 と 1 で表現しますが、 1 と出たところを塗りました。

確かに各人の勤務は丁度4時間、縦に見たときの必要人数も満たしています。 こういう結果に直面した場合における、率直な心情を人間代表として数理最適化にぶつけるとすると次のセリフになるでしょうか。

「人数が居れば、勤務時間を満たせば、良いっていうもんじゃない !」

先日の記事では偏りが気になる、といった程度でしたが今回は「使えない」 度合いがパワーアップしています（例えばＢさんとかひどいものです）。 常識的に各人 4時間は連続して働く、 すなわち「1時間外してまた戻ってくる」といった勤務があり得ないことを数理最適化モデルには教えてやる必要があることがわかりました。 こういうときに我々が繰り出すのが、数式で実務的な制約を表現する「小技」です。 古くから様々なテクニックが知られており、大抵の実務的な条件は適宜余計な変数など定義が必要な場合がありますが一次式に書き下すことができます（ちょっと数式っぽくなるので詳細は別の機会に）。 ここでは「一度帰ったら職場に復帰してはならない」という制約を入れることにしましょう。 具体的には横に連続したマス目が 1 (勤務) -> 0 (非勤務) という並びになっているならば、 その右にはすべて 0 が並ぶ、という制約を入れます。

この制約と各人の勤務時間が 4時間であることを合わせると 所望の形の勤務形態となるはずです。

今度は無事、意図した形のスケジュールが出力されました。 このように「マス目埋め」タイプのモデルは、基本の縦と横の制約のみが入っている状態だと 解の自由度に比べて制約が少ない(解の自由度は行と列の数の積ですが、制約の数は和)ので通り一編の答はぱっと出すことができますが、実務的に使えるようにするには様々な小技を駆使した制約を追加して 所望の答をいわば「彫り出す」操作が必要になります。

次回は対照的に「彫り出す」やり方から「組み立てる」やりかたで同じ問題を解いてみましょう。 「重ね合わせ」タイプの出番です。