「マス目埋め」タイプのモデル:アルバイトの担当決め問題

いわゆる「シフト表」は「人」を行、「日付」を列とするマス目の形をしています。 5人のアルバイトさんＡ，Ｂ，Ｃ，Ｄ、Ｅの一週間のシフト表を数理最適化で作ってみます。 この職場では各人は「レ」(レジ打ち)、「日」(日勤)、「夜」(夜勤)、「休」(休暇) 、 のいずれかを担当します。

職場の事情はこの表を縦に見ることで定義します。各日一定の役割の人は必要です。

個人の事情は横に見れば定義できます。人間、休みが必要ですし、しんどい夜勤は そんなに偏ってはなりません。

なんだか求人広告みたいですが、これでも立派な数理最適化モデルで、 もう解くことができます。このとっつきの良さがマス目タイプの問題の一つの特徴です。 果たしてその回答は？

制約をチェックしてみてください。満たしてますね。 一秒もかからずこれを出せるのが今時の数理最適化の実力。 数理最適化を解く手法として特にマス目タイプに強い、 「メタヒューリスティクス」アルゴリズムの威力です。

皆さんどんどん使いましょう、じゃあまた来週 !

・・・とは行かないのが、この「マス目埋め」タイプのモデルの難しさで、 とっつきが良かった分、思いもよらない苦労をすることになります。 上のシフト表、E さんいきなり 2 連休ですね。 不公平だと文句が出そうだと思ってもう一度解くことにしてみました。 同じ問題なのだから同じ答が出るだけだろうって？ ええ、普通はそうなのですが、 じつは「メタヒューリスティクス」をアルゴリズム（解き方）として採用している場合には 初期値を乱数で作ってから解を改良する方法なので、 (存在すれば)制約を満たす「別解」を得ることができます。 これが最初の別解。さて、どうでしょう。

今度は A さんに夜勤が割りあたらず、レジも一回しかありません。 もう一度。

これでは A さん B さん連続夜勤の過酷勤務です。これも没。

C さん夜勤やらないわ、3人が連続夜勤をやるわ、 ある意味極めつけのシフト表が出てきてしまいました。 確かに最初に言った制約は満たしているんですが。

じつは10回やると10回とも違うシフトが出てきて、 うち 9回が連続夜勤や夜勤割り当てがされない人が居る、 何かしらの問題を抱えた結果が出力されてしまうことことが判りました。 実はこの「マス目埋め」タイプのモデルは、解が沢山出るが、 使えるものが少ないという状態に陥りがちなので注意が必要なのです。 どうすればよいでしょう。そうです。変な解が出るのは制約が足りないから。

• 夜勤は続いてはならない
• 各人 1 回は夜勤をする

という制約を入れれば、すぐさま次の答に行きつくことができます。

もう大丈夫でしょうか。 D さんにレジが入らないのが気になる？ 連続でレジは困る？ わかりました。また制約を追加しましょう・・・

これまでのケースのようにモデルを定義する本質的な制約を入れて 答が出れば OK、だったのとはちょっとノリが違いますよね。 制約を満たす答が沢山ありすぎることと、どういう制約が必要なのかが あらかじめ予見しにくいのでどこまでも「アジャイル」にモデルの改変が続くのが このタイプの特徴と言えます。

特にこのケースは人的スケジューリングにおいて暗黙のうちに重視される「平準化」を 機械に意識させることが意外と難しい、という実例になっています。 でもちょっと待ってください。 「メタヒューリスティクス」アルゴリズムは 乱数を使っているから誰も特別扱いしていないので出る結果は 偏らないはずですよね・・・

じつは意外とそうでもないのです。 皆さん 1,2,3,4,5 の数字をランダムに 10 個並べてみてください。 私の手元のプログラムは

2,2,5,1,3,1,5,1,3,1

を出してきました。4 がないのが不自然でランダムとは思えない？ いえ。数字の出方が均等でも特定の数字 1つが欠ける確率は 0.8 の 10 乗 = 10.7% です。 1 から 5 までのいずれかの 1 つの数字が欠ける確率だともっと多くなって、 計算がちょっと面倒ですがじつは 「47.7%」 と大体半分に迫る確率となります。 人間が自然に備えている「均等化」の感覚が働いて おそらく皆さんの作成された列には 1 から 5 までのすべてが現れたのではないでしょうか。 解が多すぎるとき、どこまでも自由な機械の振舞いを強制するためには制約が必要になる、 というお話でした。

この数理最適化モデルはかなり特殊なタイプとも言えますが、 実務的な利用価値が非常に高いので タイプの一つとして紹介させていただきました。 ここでは名前だけ出した「メタヒューリスティクス」って一体何なのか、 マス目タイプのモデルを使って質の高いシフト表を得るための悲喜こもごものお話はまた別途お話ししたいとと思います。

さて、次はいよいよ最後の「対応付け」タイプです。