こんにちは。プロダクト執行役員の片田です。

今回の記事は先月の勉強会の発表内容の一部を元に書いています。経営分析チームリーダーの大澤による「勤務スケジューリング問題 モデリングの基礎」についてです。

弊社ではコンシェルジュ（こちらで仕事内容などを紹介しています）がシフト勤務制のため、勤務スケジューリング問題によるシステムでのシフト生成を行なっています。
その秘密の一部を今回ご紹介しようと思います。

2024年3月現在、コンシェルジュは約60名ぐらい(?)いるっぽいので、シフトすべてを手作業で行うととんでもない工数がかかってしまいます（且つ出てきたシフトが最適だとは保証されません）。また組織がさらにスケールした時には、シフト担当が複数人必要になることも考慮して、可能な限り汎用的な仕組みにしています。

ということで今回は、シフト自動生成の根幹を担っている「組み合わせ最適化問題の概要」から「勤務スケジューリング問題の基礎」までをご紹介していきます。

組み合わせ最適化問題とは

モデリングの基礎ということなので、まずは構成要素について説明です。

$$
\begin{align*}
目的関数: & f(\boldsymbol{x}) & \to 最小化 \\
制約条件: & g_i(\boldsymbol{x}) \le 0 & (i = 1, \dots, l) \\
& h_j(\boldsymbol{x}) = 0 & (j = 1, \dots, m) \\
\end{align*}
$$

制約付き最適化は、制約条件 $${g_i(x) \le 0}$$ , $${h_j(x) = 0}$$ を守りながら 目的関数 $${f(x)}$$ を最小化するような決定変数 $${x}$$ を見つけよという問題です。そして「組み合わせ最適化問題」とは、最適化問題のうち、決定変数に離散値をとるものを含む問題のことを言います。

例えば、下記が組み合わせ最適化問題の例となります。

• 最短経路問題

• 巡回セールスマン問題

• 勤務スケジューリング問題

• 安定マッチング問題

組合せ最適化問題は「様々な制約の元で、ある指標を最もよくする変数の組み合わせを求める」ということです。

勤務スケジューリング問題のモデリング

ここからは簡単な例をもとに、勤務スケジューリング問題をどのようにモデリングするのかを見ていきます。

決定変数

勤務スケジューリング問題における決定変数は、誰がいつ、どのシフトに割り当てられるかを表現したものです。例えば、シフト種別が以下の4種類であると仮定すると、どのように決定変数を表現すべきでしょうか？

1. 早番

2. 遅番

3. 通し

4. 休み

この表現には何通りかの方法が考えられます。試しに、「Aさんの2/1のシフトは早番(1)」「Bさんの2/2のシフトは通し(3)」という具合に、コンシェルジュと日付の組に対して整数値を割り当てて表現してみます。

その場合の数理表現は次のようになります。

$$
x_{e,d} = \begin{cases} 1 & 早番 \\ 2 & 遅番 \\ 3 & 通し \\ 4 & 休み\end{cases}
$$

先ほどの「Aさんの2/1のシフトは早番(1)」という例で表すと、 $${x_{A,2/1} = 1}$$　ということです。

制約条件

次に、この決定変数を使用して「通し(3)の人数は毎日2人以上必要」という制約条件を不等式で作ってみます。「このシフトにはこれだけの人数が必要」という類の制約条件は、勤務スケジューリング問題をモデリングする際によく現れます。$${ x_{e,d} = 3}$$ のとき「1」、そうでないときに「0」である関数 $${f_3(x_{e,d})}$$ の和を数えることでモデリングすると次のようになります。

$$
\forall d \in D \quad \sum_{e \in E} f_3(x_{e,d}) \ge 2
$$

$${f_3}$$ をグラフで表すとこのようになります。

このように、コンシェルジュと日付の組に対して整数値を割り当てる表現を使うと、ある日のシフト人数を数えるだけで非線形な関数が必要になってしまいました。次に述べるように、これはあまり望ましくありません。

線形最適化問題

目的関数 $${f}$$ と制約条件 $${g, h}$$ がすべて決定変数について線形であるとき、それを「線形最適化問題」といい、次のような形で書くことができます。

$$
f(\boldsymbol{x}) = b + \sum_{i=1}^{n}w_ix_i
$$

線形最適化問題は、非線形最適化問題と比べて、離散・連続問わずに簡単に解ける傾向にあります。そのため、最適化問題をモデリングする際は、線形の問題としてモデリングできないかを検討すべきです。homieのシフトも、線形最適化問題を解くことで生成されています。

0-1整数による表現

さて、先ほど検討した「通し(3)の人数は毎日2人以上必要」という制約条件を線形の不等式で表現するには、どのようにモデリングすれば良いでしょうか。

勤務スケジューリング問題のように割り当て構造がある問題では、0-1整数を使うとうまくいくことがあります。0-1整数とは、0と1しか取らない変数のことを指します。0-1整数を使うと、従業員 $${e}$$ が 日付 $${d}$$ においてシフト $${s}$$ に割り当てられるとき1、そうでないとき0を取る変数 $${x_{e, d, s}}$$ を決定変数として使うことになります。

0-1整数を使用した制約条件

0-1整数を使用した決定変数 $${x_{e, d, s}}$$ を使って、先ほどの制約条件を表現すると、以下のようになります。

$$
\forall d \in D \quad \sum_{e \in E} x_{e,d,3} \ge 2
$$

こちらは線形の不等式になるため、線形最適化問題として解くことができます。
先ほどの図で表すと、日付（横軸）とシフト（奥行きの軸）を固定して、全従業員について青い部分を足し合わせていく形になります。

実際のモデルでは、計算量などを考慮しながら、もっと複雑な制約条件を追加したり、多数ある制約条件の扱いを工夫していきます（今回は記事のボリューム的に割愛）。

ここまでが勤務スケジューリング問題のモデリングの触りとなります。数理最適化に基づく問題解決の大まかな枠組みを知りたいという方は、以前大澤が執筆した記事もありますのでご覧ください。

おわりに

今回は勤務スケジューリング問題の基礎についてご紹介しました。リアルを数理モデルに落とし込むには知識ももちろん必要ですが、実態を把握しベストな落とし所を見つける能力、その落とし所を関係各所とすり合わせる能力などもデータサイエンティストには必要になってきます。日々地道に調整を積み重ねて、事業の根幹を作り上げられるのが面白みとも言える役割です。

homieではエンジニア採用を行なっているので、リアルで使えるデータサイエンスがやってみたいという方は是非一度お話しできたらと思います。