🍣

Pulpでシフト作成を自動化したりした

2023/01/06に公開

Python

pulp

ナーススケジューリング問題

tech

はじめに

大学でシフトを組まねばならないことになったので自動化した。
自動でシフトを組む部分だけ(エクセルファイルの集計などを除いて)まとめてコードにしたものがこれ。

import pulp

n = 2  # 一度に入る人数
members = ["A", "B", "C", "D", "E"]  # 　入る人
days = ["月", "火", "水", "木", "金"]  # 入る時間

# request_table[i][j]はdays[i]におけるmembers[j]の希望度
request_table = [
    [3, 1, 1, 2, 3],
    [2, 3, 1, 1, 2],
    [2, 3, 3, 1, 1],
    [1, 1, 1, 3, 3],
    [2, 2, 2, 2, 2],
]

# 問題定義
problem = pulp.LpProblem("schedule", sense=pulp.LpMaximize)

# 変数定義
x_dm = [[pulp.LpVariable(f"x_{m}{d}", cat=pulp.LpBinary) for m in members] for d in days]

# 目的関数定義
problem += pulp.lpSum([pulp.lpDot(request_table[i], x_dm[i]) for i in range(len(days))])

# 制約関数定義
for i, d in enumerate(days):
    problem += pulp.lpSum(x_dm[i]) == n

for j, m in enumerate(members):
    problem += pulp.lpSum(list(zip(*x_dm))[j]) >= n * len(days) // len(members)
    problem += pulp.lpSum(list(zip(*x_dm))[j]) <= n * len(days) // len(members) + 1

# 解決
problem.solve()

# 後処理
shift = [list(map(lambda x: int(x.value()), x_d)) for x_d in x_dm]
for i, d in enumerate(days):
    print(f"{d} :", *[members[j] for j, x in enumerate(shift[i]) if x == 1])

一つずつ見ていく前に、どのようなシフトを組む必要があったのかを整理する。

シフトに入る日は月、火、水、木、金の5日
シフトに入る人はA、B、C、D、Eの5人
1日あたり2人がシフトに入る

というシフトを組みたい。
また、各メンバーがある曜日にシフトに入ることに対する希望度が行列で与えられている。
(希望度は1〜3の整数で、高いほどその日に入りたいことを表す。)

これらの前提を踏まえた上でコードを上から見ていきます。

解説

準備

import pulp

n = 2  # 一度に入る人数
members = ["A", "B", "C", "D", "E"]  # 　入る人
days = ["月", "火", "水", "木", "金"]  # 入る時間

# request_table[i][j]はdays[i]におけるmembers[j]の希望度
request_table = [
    [3, 1, 1, 2, 3],
    [2, 3, 1, 1, 2],
    [2, 3, 3, 1, 1],
    [1, 1, 1, 3, 3],
    [2, 2, 2, 2, 2],
]

ここでは今後使う変数を準備している。
実際に自動化する際はExcelを集計してこれらの情報を抽出したが、今回は簡単のためにこのように簡略化してある。

定義

ここら辺は主にpulpをどのように使ったかという説明なので、この辺を読むと理解しやすいと思う。

この自動化をやるためにpulpを初めて触ったが、「目的関数を追加するのが"+="なの？！？！」となってしまった。
びっくり

問題定義

# 問題定義
problem = pulp.LpProblem("schedule", sense=pulp.LpMaximize)

後述するが、今回は最大化問題をときたいのでsense=pulp.LpMaximizeを指定している。

変数定義

# 変数定義
x_dm = [[pulp.LpVariable(f"x_{d}{m}", cat=pulp.LpBinary) for m in members] for d in days]

${x_d}_m$ はメンバー $m$ が曜日 $d$ にシフトに入る時に1、そうでない時に0を取る変数である。
これらの変数を最適化することで、誰がいつ入るかというシフトが得られる。

目的関数定義

# 目的関数定義
problem += pulp.lpSum([pulp.lpDot(request_table[i], x_dm[i]) for i in range(len(days))])

${x_d}_m$ が1であるような $d$ 、 $m$ に対して与えられた希望度の合計が最大化するように目的関数を設定している。
具体的にはすべての $d$ 、 $m$ に対して、 ${x_d}_m$ と希望度の積を求め、それの総和を目的関数としている。
ここら辺はちょっと丁寧に説明するスキルが足りず、いい感じにならないのでこの記事とかを読んでください、、、

制約関数定義 1

for i, d in enumerate(days):
    problem += pulp.lpSum(x_dm[i]) == n

一日あたり2人がシフトに入って欲しいので、各行ごと(1日ごと)のシフトの人数が2( $=n$ )となるように制約関数を定める。任意の $d$ に対して、任意の $m$ についての ${x_d}_m$ の総和が $n$ となれば良い。

制約関数定義 2

一人あたり入らないといけないシフトの数を考えたい。
全部で入らないといけないシフトはn * len(days)である。
それをmemberで割るのだから一人最低でもn * len(days) // len(members)回入らないといけない。
また、最大でもそれより一回多いだけになるはずである。

for j, m in enumerate(members):
    problem += pulp.lpSum(list(zip(*x_dm))[j]) >= n * len(days) // len(members)
    problem += pulp.lpSum(list(zip(*x_dm))[j]) <= n * len(days) // len(members) + 1

基本的にさっきとやっていることは似ているが、list(zip(*x_dm))とかいうよくわからんのがいる。
これはx_dmの転置行列で、それの $j$ 番目を取得することで $j$ 人目のシフトを取り出せる。嬉しい。
転置行列についてはこの辺を読んでください。

これにて定義編終わり！
あとは解くだけ！

解決

problem.solve()

はい

後処理

shift = [list(map(lambda x: int(x.value()), x_d)) for x_d in x_dm]
for i, d in enumerate(days):
    print(f"{d} :", *[members[j] for j, x in enumerate(shift[i]) if x == 1])

この辺は動けば良かろうをしている。
shiftはx_dmの値を取り出したもの。
(pulp.LpVariable型の変数はインスタンスメソッドのvalueを呼び出すことで値を取り出せる。)
その下のfor文はいい感じに出力するためのもの。
各曜日に対して曜日名とその日シフトに入る人の名前を出力している。
出力結果はこうなる。

月 : A E
火 : A B
水 : B C
木 : D E
金 : C D

いい感じにシフトが組めてる。とても嬉しい。

おわりに

これを実装できたおかげでタスクがだいぶ楽になった。よかった。
最適化周りの話も大変勉強になった。
これまで組合せ最適化、、、？はて、、、？みたいな感じだったのが初めてまともに手を動かして理解した気がする。
それはそれとして記事は書くのが初めてだったりとわかりづらかったかもしれないし、間違いだらけかもしれない。
優しくご指摘いただければ幸いです、、

そういえばエクセルの集計とかまとめてもうちょっと実装したのがこれです。
お見せできるようなクオリティかはさておき一応置いておきます。
https://github.com/uekann/shift