こんにちは、ＭＡＭ開発グループの椎橋です。 ＭＡＭとはマーケティングオートメーションの略で、マーケティングに関する機械学習アルゴリズムを作ったり、データ分析をして改善につなげたりしています。
今回は社内制度のクリエイターの日を2日間利用して、社員旅行の班分けの最適化モデルを作りました。 以前はこの制度を利用してサーバ・ミドルウェアの勉強をしました。 nextdeveloper.hatenablog.com
弊社の社員旅行は多くの社員が参加し、最高に盛り上がる大イベントです。 社員旅行委員が予算の見積もりからスケジュールまで計画を立ててくれるのですが、 そのスケジュールの中にアクティビティと呼ばれるイベントがあります。 これは班に分かれて観光やスポーツなどを楽しむというもので、私は昨年そば打ちを体験しました。 複数あるアクティビティのうち参加できるのは一つだけな上に、人数の上限が設定されているために希望したアクティビティに参加できるかどうかは分かりません。 昨年は社員旅行委員が抽選と手動調整によって班分けを行いましたが、数時間かかったらしいので最適化モデルを作ることにしました。
データ抽出
まずは、計算に用いるデータを準備します。 Google フォームで社員の希望調査を行い、集計結果を以下のように変換します。
| 名前ID | 性別 | group_1 | group_2 | group_3 | group_4 |
|---|---|---|---|---|---|
| id_1 | 1 | 1 | 3 | -1 | 2 |
| id_2 | -1 | 2 | 3 | 1 | -1 |
| id_3 | -1 | 3 | 1 | 2 | -1 |
性別カラムは男性なら1,女性なら-1を取るようにし、各アクティビティの希望順位をgroupカラムに記します。希望していないアクティビティには-1を割り当てました。
定式化
次にこの問題を数式に変換します。
定数
まずは定数を以下のように定めます。
| 説明 | 表記 |
|---|---|
| 参加する社員[人] | $N$ |
| 班(アクティビティ)の種類 | $ M $ |
| 班 $j$ の上限人数[人] | $g_j$ |
| 社員 $i$ の班 $j$ への希望度 | $h_{ij}$ |
| 社員 $i$ が男性なら 1, 女性なら -1 を取る | $s_i$ |
$h_{ij}$は希望順位から算出した定数で、算出方法は割愛します。また、添え字集合を以下のように定義しておきます。 $$I \mathrel{\mathop:}= \{1,\ldots,N\}$$ $$J \mathrel{\mathop:}= \{1,\ldots,M\}$$
変数
次に、問題を解くための変数を以下のように設定します。
| 説明 | 表記 |
|---|---|
| 社員 $i$ が班 $j$ へ参加するなら 1, 不参加なら 0 を取る | $x_{ij}$ |
これにより、$x_{ij}$を任意の $i$, $j$ に対して定めることで班分けを一意に決定できます。
モデリング
上記を用いてモデリングします。 まず、$x_{ij}$は 0 もしくは 1 を取る変数で、参加できる班は 1 つのみであることから、
$$ x_{ij} \in \{ 0, 1\},\ \forall i\in I,\ \ \forall j \in J $$ $$ \sum_{j \in J}{x_{ij}} = 1, \ \ \forall i \in I $$
という式を作れます。これは以下のような行列形式で考えるとわかりやすいです。
| group$_1$ | group$_2$ | $\cdots$ | group$_{M}$ | |
|---|---|---|---|---|
| 社員 $i$ | $x_{i1}$ | $x_{i2}$ | $\cdots$ | $x_{iM}$ |
社員 $i$ は一つの班に属するのでいずれかが 1 でそれ以外はすべて 0 になり、それを上記の式で表しています。そして、すべての社員に対してこの式を満たさなければいけないので、各 $i$ に対して制約が設定されています。
各班には人数の上限が設けられているために、 $$ \sum_{i\in I}{x_{ij}} \leq g_j, \ \ \forall j \in J $$ を加えます。今度は班 $j$ についての制約で行列形式のデータを列で見るとわかりやすいです。
| group$_j$ | |
|---|---|
| 社員 $1$ | $x_{1j}$ |
| $\vdots$ | $\vdots$ |
| 社員 $N$ | $x_{Nj}$ |
列で和を取れば班 $j$ に属する人数を計算できるので、これが班 $j$ の上限人数以下になるようにします。 そして、目的は希望度を最大化しつつ班の男女の人数の比率をできるだけ等しくすることで、以下のようにします。 $$maximize: \sum_{i\in I}\sum_{j\in J}h_{ij}{x_{ij}} - \alpha\max_{j\in J}\left({\left|\dfrac{\displaystyle \sum_{i\in I}{s_ix_{ij}}}{g_j}\right|}\right)$$
第一項は希望度の総和、第二項は疑似男女比差を表しています。 班 $j$ に属する男性、女性の比率の差は $\displaystyle \left|{\sum_{i\in I}{s_ix_{ij}}}\big{/}{\sum_{i\in I}{x_{ij}}}\right|$ で表せますが、計算を容易にするために班の合計人数を班の上限人数に置き換えて疑似男女比差とみなし、定数 $\alpha>0$ を掛けています。標準形に変換する際は新たな変数 $y$ と以下の制約を加えれば実現できます。
$$ y \geq \dfrac{\displaystyle \sum_{i\in I}{s_ix_{ij}}}{g_j}, \ \ \forall j\in J$$ $$ y \geq -\dfrac{\displaystyle \sum_{i\in I}{s_ix_{ij}}}{g_j}, \ \ \forall j\in J $$
これにより $y$ は $\displaystyle \max_{j\in J}\left(\ {\left|\sum_{i\in I}{s_ix_{ij}}\big{/}g_j\right|}\ \right)$ 以上の値を動くことができますが、目的関数値を極力下げないようにするために最適解で $y^*$ は$\displaystyle \max_{j\in J}\left(\ {\left|\sum_{i\in I}{s_ix_{ij}}\big{/}g_j\right|}\ \right)$ になります。
以上をまとめますと、以下のモデルで書けました。
\begin{align} maximize && \sum_{i\in I}\sum_{j\in J}h_{ij}{x_{ij}} - \alpha y && \\ subject\ to && \sum_{j\in J}{x_{ij}} = 1, && \forall i \in I\\ && \sum_{i\in I}{x_{ij}} \leq g_j, && \forall j \in J\\ && g_jy \geq \sum_{i\in I}{s_ix_{ij}}, && \forall j \in J\\ && g_jy \geq - \sum_{i\in I}{s_ix_{ij}}, && \forall j \in J\\ && x_{ij} \in \{ 0, 1\}, && \forall i\in I,\forall j \in J\\ && y \in \mathbb{R} && \end{align}
実装
設計ができたので、Pythonで実装します。
import pulp '''省略''' problem = pulp.LpProblem("problem", pulp.LpMaximize) x = pulp.LpVariable.dicts("x", (range(n), range(m)), 0, 1, "Continuous") '''省略'''
ポイントは$x_{ij}$を0-1変数(Binary)ではなく$[0,1]$ の実数変数(Continuous)にしていることです。理由は行列のユニモジュラ性を利用していて、最適解で $x_{ij}$ は整数になることが保証されているためです。組み合わせ問題は変数を増やすと爆発的に計算量が増加しますが、この緩和を適用できると変数が増えても比較的容易に最適解を求められます。
結果
最後に最適化と抽選式で結果を比較します。抽選式は、希望人数を加えても班の上限に達しないならば抽選せずに確定させ、そうでなければ抽選によって班に加えるメンバーを選出する決め方です。比較は希望した班に割り当てられた人数を集計して行い、実行環境はIntel® Core™i5-6200U CPU @2.3GHz, メモリ8GB でした。
昨年の社員旅行で用いられたデータ（一部加工, $N=411, M=14$）で計算すると以下のようになりました。
| 最適化 | 抽選式 | |
|---|---|---|
| 第一希望 | 339 | 349 |
| 第二希望 | 62 | 20 |
| 第三希望 | 10 | 13 |
| 希望外 | 0 | 29 |
| 最大男女差比 | 30% | 15% |
| 計算時間 | 0.6秒 | 0.3秒 |
抽選式では希望外の班に割り当てられた社員がいるので、この後手動で調整する必要があります。一方で最適化の結果ではその現象は起きていません。次にデータの規模を大きくして$N=10000, M=100$としました。
| 最適化 | 抽選式 | |
|---|---|---|
| 第一希望 | 8318 | 8512 |
| 第二希望 | 1591 | 620 |
| 第三希望 | 91 | 270 |
| 希望外 | 0 | 598 |
| 最大男女差比 | 33.3% | 30% |
| 計算時間 | 162秒 | 16秒 |
この規模になると最適化の効果が顕著になりますね。
まとめ
クリエイターの日を利用して社員旅行の班分け最適化モデルを作りました。整数条件を不要としたモデルにすることで変数が増えても比較的容易に計算できるのが特徴でした。エンジニア支援制度が充実したネクストでは鋭意エンジニア採用中です！新卒・中途問わず、ご興味を持たれた方は是非下記ページを御覧ください。
