OR-Toolsを使ってシフトの最適化を試す

執筆日

2025/9/20

ライブラリ

pip install ortools

問題1: OR-Toolsの基本を学ぶ - 1日間のシンプルシフト

まずは、OR-Toolsの基本的な使い方を理解するために、最もシンプルなシフト問題から始めます。

問題設定

• 期間: 1日
• 従業員: Aさん、Bさん、Cさんの3人
• シフト: 早番（S1）、遅番（S2）の2種類

制約

• S1、S2シフトにはそれぞれ1人ずつ必要。
• AさんはS2シフトには入れない。

この問題を解くには、CP-SATソルバーを使います。CP-SATソルバーは、Yes/No（真偽）で答えられるような組み合わせ問題の解決に非常に優れています。

コードと解説

main.py

from ortools.sat.python import cp_model
# モデルを生成
model = cp_model.CpModel()
# データ
employees = ['A', 'B', 'C']
shifts = ['S1', 'S2']
# 変数を定義
# `x[e][s]` は、従業員 `e` がシフト `s` に入る場合に True (1)
x = {}
for e in employees:
    for s in shifts:
        x[(e, s)] = model.NewBoolVar(f'x_{e}_{s}')
# 制約条件の追加
# 1. 各シフトに必ず1人割り当てる
for s in shifts:
    model.Add(sum(x[(e, s)] for e in employees) == 1)
# 2. 従業員 A は S2 シフトに入れない
model.Add(x[('A', 'S2')] == 0)
# 3. 各従業員は1日に1つのシフトにしか入れない
for e in employees:
    model.Add(sum(x[(e, s)] for s in shifts) <= 1)
# ソルバーの生成と実行
solver = cp_model.CpSolver()
status = solver.Solve(model)

# 結果の表示
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print('最適なシフトが見つかりました:')
    for e in employees:
        for s in shifts:
            if solver.BooleanValue(x[(e, s)]):
                print(f'{e}さんが{s}シフトを担当します。')
else:
    print('シフトを作成できませんでした。制約条件を確認してください。')

実行結果

最適なシフトが見つかりました:
AさんがS1シフトを担当します。
CさんがS2シフトを担当します。

この結果は、AさんがS2シフトに入れないという制約を満たしつつ、残りのBさんとCさんでシフトを割り当てたものです。今回はCさんが選ばれました。BさんもS2に入ることができますが、この問題は「制約を満たす解を一つ見つける」ことなので、Cさんが選ばれたことになります。

問題2: 複数の制約とコストの最小化 - 3日間のシフト

次に、より現実的な要素、具体的にはコストと公平性を考慮したシフト作成に挑戦します。

問題設定

• 期間: 月曜〜水曜の3日間
• 従業員: 新人Aさん（時給1,000円）、中堅Bさん（時給1,200円）、ベテランCさん（時給1,500円）
• シフト: 早番（S1）4時間、遅番（S2）4時間

制約

• 各シフトに毎日1人ずつ必要。
• 新人AさんはS1シフトのみ、ベテランCさんはS2シフトのみ担当可能。
• 3日間のうち、全員が最低2つのシフトに入る必要がある。

目標

• 総人件費を最小化する。

コードと解説

main.py

from ortools.sat.python import cp_model

# モデルを生成
model = cp_model.CpModel()

# データ
employees = ['新人_A', '中堅_B', 'ベテラン_C']
shifts = ['S1', 'S2']
days = ['Mon', 'Tue', 'Wed']

# 時給と勤務時間
hourly_rates = {
    '新人_A': 1000,
    '中堅_B': 1200,
    'ベテラン_C': 1500
}
shift_hours = {
    'S1': 4,
    'S2': 4
}

# 変数を定義
# `x[(e, d, s)]` は、従業員 `e` が曜日 `d` のシフト `s` に入る場合に True (1)
x = {}
for e in employees:
    for d in days:
        for s in shifts:
            x[(e, d, s)] = model.NewBoolVar(f'x_{e}_{d}_{s}')

# 制約条件の追加
# 1. 各シフトに必ず1人割り当てる
for d in days:
    for s in shifts:
        model.Add(sum(x[(e, d, s)] for e in employees) == 1)

# 2. 各従業員は1日に1つのシフトにしか入れない
for e in employees:
    for d in days:
        model.Add(sum(x[(e, d, s)] for s in shifts) <= 1)

# 3. 専門性に基づくシフト制限
# 新人（Aさん）はS1シフトのみ
model.Add(sum(x[('新人_A', d, 'S2')] for d in days) == 0)
# ベテラン（Cさん）はS2シフトのみ
model.Add(sum(x[('ベテラン_C', d, 'S1')] for d in days) == 0)

# 4. 各従業員は3日間のうち最低2つのシフトに入る
for e in employees:
    model.Add(sum(x[(e, d, s)] for d in days for s in shifts) >= 2)

# 目的関数: 総人件費を最小化する
total_cost = model.NewIntVar(0, 100000, 'total_cost')
# コストの合計を計算
cost_sum = sum(x[(e, d, s)] * hourly_rates[e] * shift_hours[s] for e in employees for d in days for s in shifts)
model.Add(total_cost == cost_sum)

# コストを最小化
model.Minimize(total_cost)

# ソルバーの生成と実行
solver = cp_model.CpSolver()
status = solver.Solve(model)

# 結果の表示
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'最適なシフトが見つかりました。総人件費: {solver.ObjectiveValue()}円')
    for d in days:
        print(f'\n--- {d}曜日 ---')
        for s in shifts:
            for e in employees:
                if solver.BooleanValue(x[(e, d, s)]):
                    cost_per_shift = hourly_rates[e] * shift_hours[s]
                    print(f'{e}さんが{s}シフト（{shift_hours[s]}時間）を担当します。 → 費用: {cost_per_shift}円')
else:
    print('シフトを作成できませんでした。制約条件を確認してください。')

出力結果

最適なシフトが見つかりました。総人件費: 29600.0円

--- Mon曜日 ---
新人_AさんがS1シフト（4時間）を担当します。 → 費用: 4000円
ベテラン_CさんがS2シフト（4時間）を担当します。 → 費用: 6000円

--- Tue曜日 ---
新人_AさんがS1シフト（4時間）を担当します。 → 費用: 4000円
中堅_BさんがS2シフト（4時間）を担当します。 → 費用: 4800円

--- Wed曜日 ---
中堅_BさんがS1シフト（4時間）を担当します。 → 費用: 4800円
ベテラン_CさんがS2シフト（4時間）を担当します。 → 費用: 6000円

この問題では、全員が最低2シフト入るという制約があるため、新人Aさん、中堅Bさん、ベテランCさんがそれぞれ2日分のシフトを分担し、人件費が最も安くなる組み合わせが算出されます。

問題3: 希望休と公平性の考慮 - 1週間のシフト

最後に、より現実のバイト管理に近い、希望休と公平性を考慮した複雑なシフトを作成してみましょう。

問題設定

• 期間: 1週間（7日間）
• 希望休: Aさん（水曜、土曜）、Bさん（金曜）

目標

• 希望休や専門性などの制約を満たす。
• 各従業員の勤務日数の差を最小化し、その上で、人件費を最小化する。
  この問題は、2つの目的（公平性の最大化とコストの最小化）を同時に解決する多目的最適化です。OR-Toolsでは、これを段階的に解くことで対応できます。

コードと解説

main.py

from ortools.sat.python import cp_model

# モデルを生成
model = cp_model.CpModel()

# データ
employees = ['新人_A', '中堅_B', 'ベテラン_C']
shifts = ['S1', 'S2']
days = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun']

# 時給と勤務時間
hourly_rates = {
    '新人_A': 1000,
    '中堅_B': 1200,
    'ベテラン_C': 1500
}
shift_hours = {
    'S1': 4,
    'S2': 4
}

# 希望休のデータ
requested_off = {
    '新人_A': ['Wed', 'Sat'],
    '中堅_B': ['Fri'],
    'ベテラン_C': []
}

# 変数の定義
x = {}
for e in employees:
    for d in days:
        for s in shifts:
            x[(e, d, s)] = model.NewBoolVar(f'x_{e}_{d}_{s}')

# 制約条件の追加
# 1. 各シフトに必ず1人割り当てる
for d in days:
    for s in shifts:
        model.Add(sum(x[(e, d, s)] for e in employees) == 1)

# 2. 各従業員は1日に1つのシフトにしか入れない
for e in employees:
    for d in days:
        model.Add(sum(x[(e, d, s)] for s in shifts) <= 1)

# 3. 希望休の考慮
for e, off_days in requested_off.items():
    for d in off_days:
        model.Add(sum(x[(e, d, s)] for s in shifts) == 0)

# 4. 専門性に基づくシフト制限
model.Add(sum(x[('新人_A', d, 'S2')] for d in days) == 0)
model.Add(sum(x[('ベテラン_C', d, 'S1')] for d in days) == 0)

# 5. 各従業員の勤務日数の公平性を確保
employee_workdays = {}
for e in employees:
    employee_workdays[e] = model.NewIntVar(0, len(days), f'workdays_{e}')
    model.Add(employee_workdays[e] == sum(x[(e, d, s)] for d in days for s in shifts))

max_workdays = model.NewIntVar(0, len(days), 'max_workdays')
min_workdays = model.NewIntVar(0, len(days), 'min_workdays')
model.AddMaxEquality(max_workdays, list(employee_workdays.values()))
model.AddMinEquality(min_workdays, list(employee_workdays.values()))

fairness_gap = model.NewIntVar(0, len(days), 'fairness_gap')
model.Add(fairness_gap == max_workdays - min_workdays)

# 目的関数
total_cost = model.NewIntVar(0, 200000, 'total_cost')
cost_sum = sum(x[(e, d, s)] * hourly_rates[e] * shift_hours[s] for e in employees for d in days for s in shifts)
model.Add(total_cost == cost_sum)

# 実行
solver = cp_model.CpSolver()

# 1. 勤務日数の差（不公平さ）を最小化する
model.Minimize(fairness_gap)
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    # 勤務日数の最小差を整数で取得
    fairness_solution = int(solver.ObjectiveValue())
    print(f'ステップ1: 勤務日数の差を最小化する最適な解を見つけました。最小差: {fairness_solution}')
    
    # 2. 勤務日数の差を固定し、総コストを最小化する
    model.Add(fairness_gap <= fairness_solution)
    model.Minimize(total_cost)
    
    status = solver.Solve(model)

# 結果の表示
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'\n--- 最終的な最適なシフトが見つかりました ---')
    print(f'総人件費: {solver.ObjectiveValue()}円')
    print(f'勤務日数の最大差: {solver.Value(fairness_gap)}日')
    for d in days:
        print(f'\n--- {d}曜日 ---')
        for s in shifts:
            for e in employees:
                if solver.BooleanValue(x[(e, d, s)]):
                    cost_per_shift = hourly_rates[e] * shift_hours[s]
                    print(f'{e}さんが{s}シフト（{shift_hours[s]}時間）を担当します。 → 費用: {cost_per_shift}円')
    
    print('\n--- 各従業員の総勤務日数 ---')
    for e in employees:
        print(f'{e}: {solver.Value(employee_workdays[e])}日')
else:
    print('シフトを作成できませんでした。制約条件を確認してください。')

出力結果

ステップ1: 勤務日数の差を最小化する最適な解を見つけました。最小差: 1

--- 最終的な最適なシフトが見つかりました ---
総人件費: 68000.0円
勤務日数の最大差: 1日

--- Mon曜日 ---
新人_AさんがS1シフト（4時間）を担当します。 → 費用: 4000円
ベテラン_CさんがS2シフト（4時間）を担当します。 → 費用: 6000円

--- Tue曜日 ---
新人_AさんがS1シフト（4時間）を担当します。 → 費用: 4000円
中堅_BさんがS2シフト（4時間）を担当します。 → 費用: 4800円

--- Wed曜日 ---
中堅_BさんがS1シフト（4時間）を担当します。 → 費用: 4800円
ベテラン_CさんがS2シフト（4時間）を担当します。 → 費用: 6000円

--- Thu曜日 ---
新人_AさんがS1シフト（4時間）を担当します。 → 費用: 4000円
中堅_BさんがS2シフト（4時間）を担当します。 → 費用: 4800円

--- Fri曜日 ---
新人_AさんがS1シフト（4時間）を担当します。 → 費用: 4000円
ベテラン_CさんがS2シフト（4時間）を担当します。 → 費用: 6000円

--- Sat曜日 ---
中堅_BさんがS1シフト（4時間）を担当します。 → 費用: 4800円
ベテラン_CさんがS2シフト（4時間）を担当します。 → 費用: 6000円

--- Sun曜日 ---
新人_AさんがS1シフト（4時間）を担当します。 → 費用: 4000円
中堅_BさんがS2シフト（4時間）を担当します。 → 費用: 4800円

--- 各従業員の総勤務日数 ---
新人_A: 5日
中堅_B: 5日
ベテラン_C: 4日

この例では、公平性を優先し、その上でコストを最小化するという段階的な最適化を行っています。

まとめ

OR-Toolsを初めて使ってみました。面白い。
LLM×OR-Toolsで数理最適化ができないか検証しよ。