ソルバーを用いて効率的なチーム分けを自動生成する
この記事は、NAVITIME JAPAN Advent Calendar 2022の23日目の記事です。
はじめに
こんにちは、みたらし団子です。ナビタイムジャパンで高速道路料金エンジンの開発を担当しています。
突然ですが、みなさんはチーム分けをする際にどうやってチームを決めていますか？
チーム分けが小規模な場合はじゃんけんで決めたり、サイコロを振ってくれるWebのツールを使って決めたりするかもしれません。ところがチーム分けが中規模・大規模になってきたり、チーム分けが満たすべき条件が複雑になってくると、そうした簡易的な方法ではうまくチームを組めない場合が出てきます。ファシリテーションする立場からすると、できればそういう事態は避けてミーティングの成果を最大化したいもの・・・。
でも安心してください。実は、ある種の数学モデルに定式化してソルバーに投げることで、自動で効率的なチーム分けを組むことができるんです。
この記事では、私が業務で実際に遭遇した複雑なチーム分けと、効率的なチーム分けを自動生成した話をご紹介します。
課題設定
ナビタイムジャパンの研究開発部門では目標管理の仕組みとしてOKR(Objectives and Key Results)を採用しています。
OKRの特徴的なプラクティスとして、定期的にウィンセッションを行うことがあります。これは、OKRを追いかけるチームメンバー同士がお互いのやったことをひたすら承認し合う（褒め合う）会のことです。
私のいる組織では、下記の内容でウィンセッションを開催しています。
頻度：月に1回
内容：直近1か月の活動を中心にメンバー同士が承認し合う
参加人数：30人ほど
実施形態：参加者が6つのチームに分かれ、チームのメンバーを入れ替えながら15分×3回のウィンセッションを行う
実際にやってみると「メンバーを入れ替えながら3回行う」という部分で問題が発生しました。
褒め合うのは慣れていないと気恥しい行為なので、できれば毎回まったく違うチームで行いたいと考える人が多いと思います。ところが試しにチームの割り振りをランダムに行ったところ、1回目～3回目で同じメンバーが同じチームになるという事象が多発してしまいました。そのため「先ほど褒めたばかりのメンバーをすぐまた褒めなければならない」という状況が発生してしまい、その点をやりづらく感じるメンバーもいました。
同じメンバーが複数回同じチームにならないようなチーム分けを行うにはどうしたらよいか？
というのが今回の課題設定となりました。
整数計画問題としての定式化
今回はウィンセッションのチーム分けを整数計画問題として定式化します。
整数計画問題とは最適化問題のうち、目的関数と制約条件がともに線形（一次式として表せる）で、かつ解が整数解のみになるようなものを指します。
整数計画問題にはいろいろなソルバーが存在するため、定式化だけしてしまえば実装はソルバーにまかせることができます。
※ただし今回の課題設定では制約条件のみ満たせば良いため、目的関数は設定しません。与えた制約を満たす実行可能解を見つけるためにソルバーを利用します。
素朴な定式化
まず、各種変数を下記のように定義します。
$${I = \{1, 2, …, 30\}}$$：メンバーの集合
$${J = \{ 1, 2, 3\}}$$：ウィンセッションを行う回数の集合
$${K = \{ 1, …, 6 \}}$$：チームの集合
$${{c = 5}}$$：1チームあたりのメンバーの数の上限
ソルバーで解を求める対象の変数の意味を、下記のように定義します。
$${x_{ijk} \in \{0, 1\}}$$：1ならば、メンバー$${i \in I}$$が$${j \in J}$$回目のウィンセッションでチーム$${k \in K}$$に所属することを表す。0ならば所属しないことを表す。
最後に制約条件を下記のように組みます。
$${\forall i \in I, j \in J. \sum_{\substack{k \in K}} x_{ijk} = 1}$$：すべてのメンバーは各イテレーションで、一つのチームに所属する・・・①
$${\forall j \in J, k \in K. \sum_{\substack{i \in I}} x_{ijk} \leq c}$$：すべてのチームのメンバー数は、メンバー数の上限以下になる・・・②
すべてのメンバーのペア$${(a, b) \in I \times I}$$について、$${\sum_{\substack{j \in J}}\sum_{\substack{k \in K}} x_{ajk}x_{bjk} \leq 1}$$：どのメンバー同士も複数回同じチームにならない・・・③
今回の要件を素朴に定式化すると上記のようになりますが、③の制約は$${x}$$についての一次式になっていません。そのためこのままでは整数計画ソルバーを使うことができないため、ひと工夫必要になります。
制約条件を一次式にするための工夫
③の式を一次式にするために、$${x_{ajk}x_{bjk}}$$の部分を新しい変数$${z_{abjk} \in \{0, 1\}}$$で定義します。すると、③の式が成立することは、下記の4つの式のすべてが成立することと等価であることがわかります。
$${\forall a, b \in I, j \in J, k \in K. z_{abjk} \leq 1}$$・・・④
$${\forall a, b \in I, k \in K. z_{abjk} \leq x_{ajk}}$$・・・⑤
$${\forall a, b \in I, k \in K. z_{abjk} \leq x_{bjk}}$$・・・⑥
$${\forall a, b \in I, k \in K. z_{abjk} \geq x_{ajk} + x_{bjk} - 1}$$・・・⑦
④⑤⑥⑦はいずれも一次式なので、整数計画問題のソルバーに設定することができます。③と④⑤⑥⑦の等価性は$${x, z \in \{0, 1\}}$$だからこそ成り立つことに注意です。
この変換に関するアイディアは、10Xさんの素晴らしい記事を参考にさせていただきました。ありがとうございました。
最適化ソルバーを用いた実装
あとは上記の①②④⑤⑥⑦の制約式を整数計画問題のソルバーに設定するだけです。今回はGoogleが開発した無償の最適化ライブラリの『OR-Tools』を使って問題を解きました。開発言語はPythonです。
from ortools.linear_solver import pywraplp
import itertools
NUM_OF_MEMBERS = 30
NUM_OF_TEAMS = 6
NUM_OF_ITER = 3
def make_variables(solver):
x_dict = {}
z_dict = {}
# variable x
for iter_id in range(NUM_OF_ITER):
for person_id in range(NUM_OF_MEMBERS):
for team_id in range(NUM_OF_TEAMS):
x_dict[(iter_id, person_id, team_id)] = solver.IntVar(0, 1, "")
# variable z
for iter_id in range(NUM_OF_ITER):
for person_1_id, person_2_id in itertools.combinations(range(NUM_OF_MEMBERS), 2):
for team_id in range(NUM_OF_TEAMS):
z_dict[(iter_id, person_1_id, person_2_id, team_id)] = solver.IntVar(0, 1, "")
return x_dict, z_dict
def add_x_constraints(solver, x_dict):
# constraint 1
for iter_id in range(NUM_OF_ITER):
for person_id in range(NUM_OF_MEMBERS):
sum_target = [x_dict[(iter_id, person_id, team_id)] for team_id in range(NUM_OF_TEAMS)]
num_of_teams_belong_to = solver.Sum(sum_target)
solver.Add(num_of_teams_belong_to == 1)
# constraint 2
for iter_id in range(NUM_OF_ITER):
for team_id in range(NUM_OF_TEAMS):
capacity_per_team = int(NUM_OF_MEMBERS / NUM_OF_TEAMS)
sum_target = [x_dict[(iter_id, person_id, team_id)] for person_id in range(NUM_OF_MEMBERS)]
num_of_members_per_team = solver.Sum(sum_target)
solver.Add(num_of_members_per_team <= capacity_per_team)
def add_z_constraints(solver, x_dict, z_dict):
# constraint 4
for person_1_id, person_2_id in itertools.combinations(range(NUM_OF_MEMBERS), 2):
sum_target = []
for iter_id in range(NUM_OF_ITER):
for team_id in range(NUM_OF_TEAMS):
sum_target.append(z_dict[(iter_id, person_1_id, person_2_id, team_id)])
solver.Add(solver.Sum(sum_target) <= 1)
# constraint 5, 6, 7
for iter_id in range(NUM_OF_ITER):
for person_1_id, person_2_id in itertools.combinations(range(NUM_OF_MEMBERS), 2):
for team_id in range(NUM_OF_TEAMS):
z = z_dict[(iter_id, person_1_id, person_2_id, team_id)]
x1 = x_dict[(iter_id, person_1_id, team_id)]
x2 = x_dict[(iter_id, person_2_id, team_id)]
solver.Add(z <= x1)
solver.Add(z <= x2)
solver.Add(z >= x1 + x2 - 1)
def print_solution(x_dict):
for iter_id in range(NUM_OF_ITER):
print(f"------- {iter_id + 1}回目 -------")
for team_id in range(NUM_OF_TEAMS):
print(f"チーム{team_id}", end=" ")
team_members = []
for person_id in range(NUM_OF_MEMBERS):
target_variable = x_dict[(iter_id, person_id, team_id)].solution_value()
if target_variable == 1.0:
team_members.append(str(person_id).zfill(2))
print(",".join(team_members))
def main():
solver = pywraplp.Solver.CreateSolver('SCIP')
x_dict, z_dict = make_variables(solver)
add_x_constraints(solver, x_dict)
add_z_constraints(solver, x_dict, z_dict)
status = solver.Solve()
print_solution(x_dict)
if __name__ == "__main__":
main()実行結果
------- 1回目 -------
チーム0 01,14,21,23,29
チーム1 05,08,11,15,16
チーム2 00,12,13,17,27
チーム3 02,07,18,19,26
チーム4 04,06,24,25,28
チーム5 03,09,10,20,22
------- 2回目 -------
チーム0 04,08,09,21,27
チーム1 06,10,17,19,29
チーム2 00,16,22,23,26
チーム3 11,12,18,20,24
チーム4 01,03,07,15,28
チーム5 02,05,13,14,25
------- 3回目 -------
チーム0 00,02,03,11,29
チーム1 01,04,13,20,26
チーム2 08,10,12,23,28
チーム3 05,06,07,22,27
チーム4 09,14,15,19,24
チーム5 16,17,18,21,25あとは出力された2桁の数値にメンバーを好きに割り当てれば、「同じメンバーが複数回同じチームにならないようなチーム分け」の完成です！
おわりに
この記事では、私が業務で実際に遭遇した複雑なチーム分けと、効率的なチーム分けを自動生成した話についてご紹介しました。
最後に、自動生成したチーム分けを実際に業務に適用した所感を記載して、結びとしたいと思います。
うまくいったこと
初回のウィンセッションで挙がっていた「同じメンバーが複数回同じチームになる」というメンバーの不満解決することができました。これによって互いに承認し合うというウィンセッションの目的が、より効果的に達成できるようになったと感じています。
また、ウィンセッション直前で参加メンバーが欠席を表明した際にも、すぐにチーム分けを修正することができました。チーム分けを手動で作成していたらこうもスムーズにはいかなかったと思われるため、この点も自動化でうまくいった点かなと考えています。
今後改善したいこと
今回は「同じメンバーが複数回同じチームになる」という事象を回避することを目的に定式化を行いましたが、メンバーからのフィードバックを受けて、他にも考慮したほうが良い属性がある点に気づきました。
具体的には、各チームにできるだけいろいろなバックグラウンドをもつメンバーがいる方が望ましいという点です。例えば「異なるプロダクトを開発している」「異なる役割（PM、スクラムマスター等）を担っている」「異なる年齢層である」などです。今回はそれらの属性を考慮せずチーム分けを作成したため、同じプロダクトを開発しているメンバーが同じチームに集まってしまうという事象が発生してしまいました。
今回の整数計画問題への定式化では目的関数を設定していないため、上記の内容を目的関数に設定することでより良いチーム分けを作成できるのではないかと考えています。
最後まで読んでいただきありがとうございました。