初心者のためのPythonを用いたシフトスケジューリング問題

シフトスケジューリング問題の解法の一つに、制約プログラミング（Constraint Programming） が挙げられます。

制約が増えるとモデルが大きく複雑化する整数線形計画法と異なり、複雑な論理制約の表現・組み込みに強い手法です。

今回は簡単なケースを用いて、人員配置計画を立てるシフトスケジューリング問題を制約プログラミングを用いて解いてみます。

※以下のコードはChatGPTによる生成コードの例と解説です。

0. 主要ライブラリのインポート

必要に応じてターミナルからダウンロードしましょう。

scheduling

pip install ortools

scheduling

from ortools.sat.python import cp_model
import random
import pandas as pd

1. 従業員・日・シフトを設定する

scheduling

workers = ["Alice", "Bob", "Chika", "Dave", "Emma"]
days = [1,2,3]
shifts = ["Morning", "Afternoon", "Night"]

2. シフトに入れない日を設定する

scheduling

availability = {}
for w in workers:
    for d in days:
        for s in shifts:
            availability[(w,d,s)] = 1  # デフォルトでは可=1

# 特定の日程は不可=0
availability[("Alice",1,"Night")] = 0
availability[("Bob",2,"Morning")] = 0
availability[("Chika",3,"Afternoon")] = 0

3. 時間帯ごとのシフト希望度を設定する

0.5~2.0の間でランダムに決まるようにしています。

scheduling

cost = {}
for w in workers:
    for d in days:
        for s in shifts:
            if availability[(w,d,s)]:
                cost[(w,d,s)] = random.uniform(0.5, 2.0)  # 小さいほど希望度が高い
            else:
                cost[(w,d,s)] = 1e6  # 不可は大きなコスト

4. モデルを定義する

scheduling

model = cp_model.CpModel()

# 変数: x[w,d,s] = 1 if worker w assigned to day d, shift s
x = {}
for w in workers:
    for d in days:
        for s in shifts:
            x[(w,d,s)] = model.NewBoolVar(f"x_{w}_{d}_{s}")

xの中身は以下のようになっています。

出力

{('Alice', 1, 'Morning'): x_Alice_1_Morning(0..1), ('Alice', 1, 'Afternoon'): x_Alice_1_Afternoon(0..1), ('Alice', 1, 'Night'): x_Alice_1_Night(0..1), ...

5. 制約条件を追加する

以下の3つの条件を加味したスケジューリングを行うことにします。

• 各時間帯には1人のみシフトに入ることができる。
• 各スタッフは1日1回のみシフトに入ることができる。
• シフトに入ることができない日（変数availabilityの値が0）は入れない。

scheduling

# 各シフトに1人
for d in days:
    for s in shifts:
        model.Add(sum(x[(w,d,s)] for w in workers) == 1)

# 各人は1日1シフトまで
for w in workers:
    for d in days:
        model.Add(sum(x[(w,d,s)] for s in shifts) <= 1)

# シフトに入れない日は考慮しない
for w in workers:
    for d in days:
        for s in shifts:
            if availability[(w,d,s)] == 0:
                model.Add(x[(w,d,s)] == 0)

6. 目的関数の最小化

今回は、希望度などを総合した「総コスト」を作り、1つの目的関数として最小化しています。

scheduling

objective_terms = []
for w in workers:
    for d in days:
        for s in shifts:
            objective_terms.append(int(cost[(w,d,s)]*100) * x[(w,d,s)])  # 小数を整数化
model.Minimize(sum(objective_terms))

7. ソルバーで解く

scheduling

solver = cp_model.CpSolver()
status = solver.Solve(model)

8. 結果表示

データフレームの形で表示しています。

scheduling

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    schedule = []
    for d in days:
        for s in shifts:
            for w in workers:
                if solver.BooleanValue(x[(w,d,s)]):
                    schedule.append({"Day":d, "Shift":s, "Worker":w, "Cost":round(cost[(w,d,s)],2)})
    df = pd.DataFrame(schedule)
    df = df.sort_values(["Day","Shift"]).reset_index(drop=True)
    print(df)
else:
    print("解が見つかりませんでした")

上記のコードを実行すると、以下のような結果が得られました。
（乱数が入っているので上記のコードを実行しても必ずしも同じ値にはなりません。ご了承ください。）

計算結果

Day      Shift Worker  Cost
0    1  Afternoon   Emma  0.78
1    1    Morning    Bob  0.53
2    1      Night  Chika  0.84