Pythonによるpulpの組合せ最適化を使用したシフト作成について

Question

前提・実現したいこと

Python初心者です。宜しくお願いいたします。
稚拙な説明で申し訳ありませんが、ご指導いただけますと幸いです。

Pythonにてpulpの組合せ最適化を使用しシフト作成を行うことを検討しています。作成するシフトについての条件は次のとおりとなります。
・１チーム５名（A～E）で成り立っています。
・日勤→夜勤→明け→休暇　のローテーションで繰り返される勤務となります。
・日勤でも早番と遅番がありますので、日勤シフトの場合、早番で勤務するメンバーと遅番で勤務するメンバーにわかれています。
作成するシフトについて「0」「1」「2」で表現することとし、「0：休暇」「1：早番」「2：遅番」としたいです。
例として6/20が日勤で「1：早番」が2名「2：遅番」が2名（１名は休暇）のシフト場合、その日の数値の合計値は「6」となりますが、1名は休暇でありますので、4名で「6」を表す場合の組合せは「1」が2名「2」が2名（「0」が1名）となるので、これを制約式で表現したいと思っています。

発生している問題・エラーメッセージ

元々存在していたソースは「0：休暇」「1：出勤」の組合せを制約式にしたものだったのですが、この制約式を修正し、０～２の値を取り得ることと、該当の日における「0：休暇」の人数を制約式として追加することを試みました。
######0~2の値を取り得る

for i in range(n_members):
    for j in range(n_days):
        model.addConstraint(a.iloc[i,j] <= 2) 

######該当の日における「0：休暇」の人数

for i in range(n_days):
    n_rest = num_rest_members[duty_list[i]]
    for j in range(n_members):
        if value(a.iloc[j,i]) == 0:
           x += 1
    model.addConstraint(x <= n_rest)

実行すると後半部分の制約式に誤りがあり、次のようなエラーが発生します。
TypeError: Can only add LpConstraint objects

該当のソースコード

import numpy as np
import pandas as pd
from pulp import *
from ortoolpy import addvar, addvars, addbinvars
import random
import string

model = LpProblem()

n_members = 5
members = list(string.ascii_uppercase[:n_members])
days = range(1, 31)
n_days = 30

"""
変数の準備
"""
a = pd.DataFrame(addvars(5, 30), index=members, columns=days)
members = list(string.ascii_uppercase[:n_members])

num_required_members = {'日勤': 6, '夜勤': 7, '明け': 5, '休暇': 0}
num_reｓｔ_members = {'日勤': 1, '夜勤': 0, '明け': 0, '休暇': 5}

duty_list = ['明け', '休暇', '日勤', '夜勤', '明け', '休暇', '日勤', '夜勤', '明け', '休暇', '日勤', '夜勤', '明け', '休暇', '日勤', '夜勤', '明け', '休暇', '日勤', '夜勤', '明け', '休暇', '日勤', '夜勤', '明け', '休暇', '日勤', '夜勤', '明け', '休暇']

t = 30
y = addvar()
x = addvar()
"""
目的関数と制約式
"""
model.setObjective(y)
"""
各メンバーの出勤日数をなるべく小さくする
"""
for i, s in enumerate(a.sum()):
    model.addConstraint(s - t <= y)
    model.addConstraint(s - t >= -y)

"""
取り得る値は0~2
"""
for i in range(n_members):
    for j in range(n_days):
        model.addConstraint(a.iloc[i,j] <= 2)        

"""
該当の日の数値の合計が一致する。
"""   
for i in range(n_days):
    n_mem = num_required_members[duty_list[i]]
    model.addConstraint(a.iloc[:,i].sum() == n_mem)

"""
該当の日の休暇（0）の数が一致する。
"""            
for i in range(n_days):
    n_rest = num_rest_members[duty_list[i]]
    for j in range(n_members):
        if value(a.iloc[j,i]) == 0:
           x += 1
    model.addConstraint(x <= n_rest)

model.solve()

試したこと

前述でも記載させていただきましたが、０～２の値を取り得ることと、該当の日における「0：休暇」の人数を制約式として追加することを試みましたが、休暇（0）の数の制御がうまく動作しませんでした。

補足情報（FW/ツールのバージョンなど）

Comments

[tiitoi]

Python のコードの記載はマークダウン記法を使っていただけますでしょうか。(インデントが崩れてしまうため)

[k-shiokawa]

大変失礼いたしました。マークダウン記法にてコードを修正いたしました。

[tiitoi]

訂正ありがとうございます。
すみませんが、質問のコードは定義されていない変数等があり、動きません。
一旦コードは置いておいて、文章でルール (制約条件) を整理していただけますか？
シフトは「早番、遅番、夜勤、休暇」の4種類だと解釈したのですが、「明け」とはどういう意味でしょうか。
また、日勤→夜勤→休暇を繰り返すということは、日勤、夜勤、休暇が連続したりすることはないということでしょうか。

[k-shiokawa]

ご質問有難うございます。コードについては主に制約条件をピックアップして記載させていただいておりまして、うまく動作しないとのことで失礼いたしました。
またシフト勤務ですが、日勤（早番または遅番）は8時間勤務となるのですが、夜勤については前日から翌日朝までの16時間（２日分）勤務し、勤務が終了した日については「明け」扱いとなり、出社しないで良いルールとなっています。なお「明け」は休暇ではありませんので、「休暇」とは別扱いのシフトとしています。
そのため夜勤→夜勤といった連続した勤務はありません。日勤（早番または遅番）→夜勤→明け→休暇→日勤・・・を繰り返す形式となります。
（厳密には他のチームのメンバーの都合等により日勤→日勤となる場合もありますが、初めからそこまで考慮すると難解となってしまうとの考えから対象外とさせていただいています）

[tiitoi]

> TypeError: Can only add LpConstraint objects

pulp に model.addConstraint() で制約を追加する際、引数が pulp.pulp.LpConstraint でないというエラーです。
print(type(x <= n_rest)) を入れた場合、pulp.pulp.LpConstraint 型になっていますか？

[k-shiokawa]

改めてご指摘いただいた点を元にコードを見直ししましたところ、同様のエラーは発生しなくなりました。有難うございました。また次の点について修正を試みました。
①元来の仕様では「0」,「1」のみをシフトの対象としていたのですが、今回「2」も対象となるので以下のとおり「1」を外しました。
for i, s in enumerate(a.sum(1)):
→for i, s in enumerate(a.sum()):
②該当の日の数値の合計が一致する必要がありますので、以下のとおり等号に修正しました。
model.addConstraint(a.iloc[:,i].sum() <= n_mem)
→model.addConstraint(a.iloc[:,i].sum() == n_mem)

一応動作はするのですが、明けの日の場合、５名全員に「1」が入って欲しいのですが、「2」「2」「1」「0」「0」といったシフトになってしまいます。また日勤の日も、「2」「2」「1」「1」「0」となって欲しいのですが、、「2」「2」「2」「0」「0」となってしまいます。
「該当の日の数値の合計が一致する」の制約は守られているのですが、追加した「該当の日の休暇（0）の数が一致する」の制約が全く反映できない状況に陥っています。
また今回うまく動作しない形式でのソースで質問させていただきましたが、問題ありましたら改めて動作するソースで投稿し直させていただきたいとも思います。

[k-shiokawa]

ソースについてそのままでは動作できなかったため、載せ替えさせていただきました。

[k-shiokawa]

丁寧なご説明とサンプルコードのご提供をありがとうございました。当方が作成したいシフトの説明が悪かったようですので、改めてご説明させていただきます。
・１チーム５名で成り立っていて、チーム制のシフト勤務を行っています。
・日勤→夜勤→明け→休暇　のローテーションで繰り返される勤務となります。
　同じチームに所属する５名は全員同じローテーションを行います。（日勤であれば５名全員が日勤シフト、夜勤でれば全員が夜勤シフト、同様に休暇であれば全員が休暇）
・仮に上述のチームをAチームとした場合、Aチームが休暇の場合、日勤や夜勤が不在となってしまいますが、それはBチームやCチームのメンバーが行うこととなります。
・最終的には全チームのシフトを作成する必要がありますが、一旦はAチームに限定して検討したいです。
・元々のソースは出勤「1」or休暇「0」の２択だったのですが、日勤の日については早番or遅番の別がありますので、それを「１」or「２」で区別したいです。
・Aチームでは当日がどのシフトとなるかは予め判明していますので、「明け」や「夜勤」は「1」で表せれば問題ありません。
・上述のソースの「duty_list 」がAチームのシフトとなっています。日々のシフトを満たすにはどのような人数構成となっていればよいかを「num_required_members 」や「num_reｓｔ_members 」でうまく制約がつけられれば良いと考えました。

お手間を取らさせてしまい申し訳ありませんが、可能でありましたらお力添えいただけますと幸いです。

[tiitoi]

人数は5人で全員が同じシフトで動くのだとすると、何を最適化したいのでしょうか。
例えば、30日分のシフトを作るとして、各日付の '日勤', '夜勤', '明け', '休暇' のパターンも決まっているのだとすると、日勤のシフトの日に5人がそれぞれ早番、遅番のどちらにするかしか選択肢がないように思えますが、いかがでしょうか。

また「５名は全員同じローテーション」という説明と質問文に記載がある以下は矛盾しませんか。

> 「1：早番」が2名「2：遅番」が2名（１名は休暇）

[k-shiokawa]

制約に記載させていただかなかったのですが、勤務地が２か所ありまして、夜勤シフトでA勤務地、B勤務地に分かれるのですが、これも「1」「2」等で表せればと考えていました。他休日の場合は出勤人数も少なくなるのですが、出勤日にばらつきが出ないようにしたいと考えています。
ご指摘の件もっともなのですが、条件を色々と出すと複雑になってしまうかと思い、また今回のケースがクリアできれば自ら検討ができるかと思った次第です。
申し訳ありません。

[tiitoi]

簡易的な条件から取り組む方針はよいと思いますよ。
しかし、現状の問題設定ですと、日勤の日に早番、遅番のどちらかを選択するかどうかしか選択肢がないので、早番2名必要、遅番3名必要となっていたら、2名を早番に割り当てる、3名を遅番に割り当てるだけなので、最適化する要素がありません。

あと、選択肢がA, B, C あったとして、0, 1, 2 の値をとる変数1つで表すという方式だと制約式が書けません。
基本的にその場合はAするかどうか、Bするかどうか、Cするかどうかの3つの2値変数で表すのがよいかと思います。
(2値変数というのは、取る値が0,1ということ。1だったら ～ する、0だったら ～ しない を意味する。)

まずは類似問題などで変数定義、制約条件の書き方等を勉強してみてはどうでしょうか。

「集合被覆問題」
http://www.msi.co.jp/nuopt/docs/v19/examples/html/02-06-00.html
「スケジューリング問題」
https://tech.unifa-e.com/entry/2019/06/21/064243?utm_source=feed

[k-shiokawa]

ご回答ありがとうとございました。教えていただいたリンク先の内容を確認して再考いたします。

Answer 1

問題設定について

元々出勤 or 休暇の2択を2値変数で表されていたのを "早番", "遅番", "夜勤", "明け", "休暇" の5種類に拡張するのであれば、変数は (日付の数, 従業員の数, 5) だけ変数が必要になるのではないでしょうか。

質問にあるような変数を整数にして早番なら0、遅番なら1、夜勤なら2、... のようなやり方だと、「各時間帯で必要な人数以上が割り当てられている」という制約や「早番 or 遅番 → 夜勤 → 明け → 休暇のパターンのみ OK」という制約を数式で表す方法が思いつきませんでした。

まずはコードは一旦置いておいて、要求を満たすようにするにはどのようなモデルを作成すればいいか数式で考えたほうがよいかと思います。

必要な情報を定義

目標関数

制約条件

サンプルコード

必要な情報を定義

import itertools

import pandas as pd
from pulp import LpProblem, LpVariable, lpSum, LpMinimize

# 入力
num_employees = 20

days = pd.date_range("2019-06-01", "2019-06-30")  # 日付一覧
employees = pd.Series([f"employees{i}" for i in range(num_employees)])  # 従業員一覧
shifts = pd.Series(["早番", "遅番", "夜勤", "明け", "休暇"])  # シフト一覧

# 形状が (日付, 3) の DataFrame。(i, k) 成分は日付 i のシフト k の必要人数を表す。
need = pd.DataFrame([[2, 2, 2]], index=days, columns=["早番", "遅番", "夜勤"])
need

# 許可するパターン
# 早番 or 遅番 → 夜勤 → 明け → 休暇のパターンのみ OK
ok_patterns = [
    ("早番", "夜勤"),
    ("遅番", "夜勤"),
    ("夜勤", "明け"),
    ("明け", "休暇"),
    ("休暇", "早番"),
    ("休暇", "遅番"),
]

モデルの作成及びソルバー実行

# モデルを作成する。
model = LpProblem(sense=LpMinimize)

# 変数を作成する。
X = [
    [[LpVariable(f"{d}_{e}_{s}", cat="Binary") for s in shifts] for e in employees]
    for d in days
]

# 目的変数及び制約を作成する。
###########################################
objective = 0
for i in range(days.size):
    for k in range(need.columns.size):
        # 日付 days[i] のシフト k に実際に働いた人数
        actual = lpSum(X[i][j][k] for j in range(employees.size))
        # 日付 days[i] のシフト k に必要だった人数
        expected = need.iloc[i, k]
        # 余剰人数を目的関数に足す。
        objective += actual - expected
        # (制約1) シフト k の必要人数は満たす制約
        model += actual >= expected
model += objective  # 余剰人数を最小化する。

# (制約2) 一人が同じ日に複数のシフトはできない。
for i in range(days.size):
    for j in range(employees.size):
        model += lpSum(X[i][j]) == 1

# OK のパターンをインデックスに変換する。
name_to_idx = {v: i for i, v in shifts.items()}
ok = [tuple([name_to_idx[name] for name in p]) for p in ok_patterns]

# NG のパターンを作成する。
ng = [p for p in itertools.product(name_to_idx.values(), repeat=2) if p not in ok]

# (制約3) NG のパターンが出ないように制約に追加する。
for j in range(employees.size):
    for pattern in ng:
        for i in range(days.size - len(pattern) + 1):
            model += (
                lpSum(X[i + k][j][pattern[k]] for k in range(len(pattern)))
                <= len(pattern) - 1
            )


# モデルを解く。
ret = model.solve()
assert ret == 1, f"No Solution found, status: {ret}"

結果を元にシフト表作成

# 結果を取得して、データフレームを作成する。
schedule = pd.DataFrame(index=days, columns=employees)
for i in range(days.size):
    for j in range(employees.size):
        # one-hot 表現からインデックスを取得する。 例: [0, 0, 1, 0] -> 2
        binary_repr = [X[i][j][k].value() for k in range(len(shifts))]
        assert np.sum(binary_repr) == 1
        k = np.argmax(binary_repr)
        schedule.iloc[i, j] = shifts.iloc[k]

schedule.to_csv("schedule.csv")

出力結果

,employees0,employees1,employees2,employees3,employees4,employees5,employees6,employees7,employees8,employees9,employees10,employees11,employees12,employees13,employees14,employees15,employees16,employees17,employees18,employees19
2019-06-01,明け,夜勤,休暇,遅番,夜勤,明け,明け,明け,明け,遅番,早番,明け,明け,休暇,明け,夜勤,休暇,夜勤,早番,休暇
2019-06-02,休暇,明け,早番,夜勤,明け,休暇,休暇,休暇,休暇,夜勤,夜勤,休暇,休暇,遅番,休暇,明け,遅番,明け,夜勤,早番
2019-06-03,遅番,休暇,夜勤,明け,休暇,遅番,早番,早番,早番,明け,明け,遅番,早番,夜勤,遅番,休暇,夜勤,休暇,明け,夜勤
2019-06-04,夜勤,遅番,明け,休暇,早番,夜勤,夜勤,夜勤,夜勤,休暇,休暇,夜勤,夜勤,明け,夜勤,遅番,明け,早番,休暇,明け
2019-06-05,明け,夜勤,休暇,遅番,夜勤,明け,明け,明け,明け,遅番,早番,明け,明け,休暇,明け,夜勤,休暇,夜勤,早番,休暇
2019-06-06,休暇,明け,遅番,夜勤,明け,休暇,休暇,休暇,休暇,夜勤,夜勤,休暇,休暇,早番,休暇,明け,遅番,明け,夜勤,早番
2019-06-07,早番,休暇,夜勤,明け,休暇,遅番,早番,遅番,早番,明け,明け,早番,遅番,夜勤,早番,休暇,夜勤,休暇,明け,夜勤
2019-06-08,夜勤,早番,明け,休暇,遅番,夜勤,夜勤,夜勤,夜勤,休暇,休暇,夜勤,夜勤,明け,夜勤,早番,明け,遅番,休暇,明け
2019-06-09,明け,夜勤,休暇,早番,夜勤,明け,明け,明け,明け,遅番,早番,明け,明け,休暇,明け,夜勤,休暇,夜勤,遅番,休暇
2019-06-10,休暇,明け,遅番,夜勤,明け,休暇,休暇,休暇,休暇,夜勤,夜勤,休暇,休暇,早番,休暇,明け,遅番,明け,夜勤,早番
2019-06-11,早番,休暇,夜勤,明け,休暇,早番,遅番,遅番,遅番,明け,明け,早番,早番,夜勤,遅番,休暇,夜勤,休暇,明け,夜勤
2019-06-12,夜勤,早番,明け,休暇,早番,夜勤,夜勤,夜勤,夜勤,休暇,休暇,夜勤,夜勤,明け,夜勤,遅番,明け,遅番,休暇,明け
2019-06-13,明け,夜勤,休暇,早番,夜勤,明け,明け,明け,明け,遅番,早番,明け,明け,休暇,明け,夜勤,休暇,夜勤,遅番,休暇
2019-06-14,休暇,明け,遅番,夜勤,明け,休暇,休暇,休暇,休暇,夜勤,夜勤,休暇,休暇,早番,休暇,明け,早番,明け,夜勤,遅番

以下略

3つの制約に関しては満たされていることは確認しました。

所感

早番 or 遅番 → 夜勤 → 明け → 休暇のパターンのみ OK という制約のため、ある程度の人数がいないとそのようなパターンが存在しなくなってしまうし、余剰人数が出る日が出てきてしまうので、日勤 (早番 or 遅番) は2回までは OK にする等もう少し制約を緩めたほうが無駄が出ないかもしれません。

---

最適化については専門ではないので、間違い等ありましたらすみません。
意図と違いましたら、コメントしてください。

Comments

[k-shiokawa]

ご連携いただいたリンク先の資料を基に再考したところ、実現することができました。ご丁寧に説明等くださり大変お世話になりました。感謝申し上げます。