OR-ToolsのAddBoolOrの使い方(シフトスケジュール問題の制約条件の実装)

内容

• AddBoolOrメソッドによる制約条件の実装の例を紹介しています。OR-Toolsのサンプルコードとして紹介されている、シフトスケジュール問題を解くプログラムを題材としています。
• 備忘のため、Googleの数理最適化ツールOR-Toolsの、cp_modelモジュールのCpModelクラスのAddBoolOrメソッドの使い方を、簡単にまとめてみました。
• OR-Toolsのエキスパートの方には少々退屈な内容かもしれません。初心者の方であれば、参考になるかもしれません。

注意事項

• 当方、OR-Toolsの初心者です。おおむね理解したつもりで書いていますが、もしかしたら間違っているところがあるかもしれません。ご容赦下さい。
• 制約条件の実装の仕方は、シフトスケジュールの表現の仕方や目的関数の設定の仕方によって、大きく変わってきます。ここで記載されたソースコードを流用する場合は、適宜変更した上で、ご利用下さい。　　

シフトスケジュール問題

• OR-Toolsのサンプルコードとして紹介されている、シフトスケジュール問題を解くプログラムを題材とする。
• シフトスケジュール問題では、以下のような問題を解いている。
  • 8人の従業員の、3週間分の、シフトスケジュールを作る。1日の勤務は、午前／午後／夜間の3交代勤務を想定。
  • シフトスケジュールには、以下の制約条件を反映する。
    1. 1日1シフトのみ(午前／午後／夜間のいずれか)の勤務とする(H)。
    2. あらかじめ指定した従業員のシフトは固定する(H)。
    3. なるべく、従業員のシフトの希望を反映する(S)。
    4. 連続する休暇は、1-2日間とする(H)。
    5. 連続する夜間の勤務は、1-4日間とする(H)。なるべく、2-3日間とする(S)。
    6. 一週間の休暇は、1-3日間とする(H)。なるべく、2日間とする(S)。
    7. 一週間の夜間勤務は、0-4日間とする(H)。なるべく、1-4日間とする(S)。
    8. なるべく、午後->翌日の夜間の勤務はしない(S)。
    9. 夜間->翌日の午前の勤務はしない(H)。
    10. なるべく、曜日／シフト毎に必要となる従業員数を確保する(S)。
  • (H)の項目は、必ず満たさなければならない条件(ハード制約条件)を示している。(S)の項目は、必ずしも満たさなくても良いが満たした方が良い条件(ソフト制約条件)を示している。

AddBoolOrメソッドによる制約条件の実装の例

• 上記の制約条件の一部は、AddBoorOrメソッドを使って実装されている。以降では、いくつか簡単なものを抜粋して、制約条件の実装の例を示す。いずれも必要なモジュールのインポートやクラスオブジェクトの生成等 制約条件の実装と直接関係しない事前準備の手順は、省いて記載するようにしている。

　制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」の実装の方法

• 最適化したい変数(ブール変数)を定義する。
• 変数Work[e, s, d]で、「従業員eの、d日目の、シフトs(休暇(=0)／午前(=1)／午後(=2)／夜間(=3) のいずれか)」の勤務の有無を表す。work[e, s, d]=True(=1)なら、従業員eは、d日目の、シフトsの勤務に従事することとなる。

work[e, s, d] = model.NewBoolVar('work%i_%i_%i' % (e, s, d))

([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

• 禁止したいシフトの組合せを反転したリストを作る。
• ここでは、「従業員eの、d日目の、夜間の勤務」と「翌日の、午前の勤務」が続くのを禁止するため、変数Work[e, previous_shift(=夜間(=3)), d]とWork[e, next_shift(=午前(=1)), d + 1]の組合わせを反転したリストを作るようにしている。

transition = [work[e, previous_shift, d].Not(), work[e, next_shift, d + 1].Not()]

([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

• 制約条件を加える。

model.AddBoolOr(transition)

([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

　制約条件「8. なるべく、午後->翌日の夜間の勤務はしない(S)。」の実装の方法

• 最適化したい変数(ブール変数)を定義する。上記の、制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」の実装と同じ。

work[e, s, d] = model.NewBoolVar('work%i_%i_%i' % (e, s, d))

([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

• なるべく禁止したいシフトの組合せを反転したリストを作る。上記の、制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」の実装と同じ。
• ここでは、「従業員eの、d日目の、午後の勤務」と「翌日の、夜間の勤務」が続くのを禁止するため、変数Work[e, previous_shift(=午後(=2)), d]とWork[e, next_shift(=夜間(=3)), d + 1]の組合わせを反転したリストを作るようにしている。

transition = [work[e, previous_shift, d].Not(), work[e, next_shift, d + 1].Not()]

([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

• 制約条件「8. なるべく、午後->翌日の夜間の勤務はしない(S)。」を加えるための新たな変数(ブール変数)を定義する。
• 変数trans_varで、「従業員eの、d日目の、シフトスケジュールの、制約条件の逸脱」の有無を表す。trans_var=True(=1)なら、従業員eは、d日目の、シフトスケジュールが制約条件を満たしていないことになる。

trans_var = model.NewBoolVar('transition (employee=%i, day=%i)' % (e, d))

([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

• 制約条件「8. なるべく、午後->翌日の夜間の勤務はしない(S)。」を逸脱した場合に、目的関数にペナルティを加えられるようにするため、transitionに、trans_varを加える。

transition.append(trans_var)

([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

• 制約条件を加える。上記の、制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」の実装と同じ。ただし、transitionに、trans_varが加えられているため、動作が若干異なる。
• transition = [work[e, previous_shift, d].Not(), work[e, next_shift, d + 1].Not(), trans_var]の組合せを指定しているため、[work[e, previous_shift, d]=True(=1), work[e, next_shift, d + 1]=True(=1), trans_var=False(=0)]の組合せが禁止される。この場合、なるべく禁止したいシフトの組合せ[work[e, previous_shift, d]=True(=1)、work[e, next_shift, d + 1]=True(=1)]は、禁止されないことになる。その代わり、該当の組合せになった場合は、必ずtrans_var=True(=1)となるようになる。他の組合わせの場合は、trans_varの値だけが異なる組合せが2つ存在することになるため、単純に、trans_var

model.AddBoolOr(transition)

([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

• 目的関数に、trans_varを加える。併せて、制約条件を逸脱した場合のペナルティcost(>0の整数)を加える。
• 目的関数は、以下の通り、work[e, s, d]やtrans_var等の変数に、ペナルティを加味するための係数を乗じて、積算した値となっている(変数obj_bool_varsの中にwork[e, s, d]やtrans_varが含まれている。また、変数obj_bool_coeffsの中に、両者に対応する係数が含まれている。)。この目的関数を最小化することで、可能な限り、制約条件を満たすシフトスケジュールを作れるようにしている。

obj_bool_vars.append(trans_var)
obj_bool_coeffs.append(cost)

([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

　サンプルコード

• 上記の制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」と制約条件「8. なるべく、午後->翌日の夜間の勤務はしない(S)。」を実装した箇所のサンプルコードの抜粋。

  • パラメータを設定している箇所

    # Penalized transitions:
    #     (previous_shift, next_shift, penalty (0 means forbidden))
    penalized_transitions = [
        # Afternoon to night has a penalty of 4.
        (2, 3, 4),
        # Night to morning is forbidden.
        (3, 1, 0),
    ]

• 制約条件を実装している箇所

    # Penalized transitions
    for previous_shift, next_shift, cost in penalized_transitions:
        for e in range(num_employees):
            for d in range(num_days - 1):
                transition = [
                    work[e, previous_shift, d].Not(), work[e, next_shift,
                                                           d + 1].Not()
                ]
                if cost == 0:
                    model.AddBoolOr(transition)
                else:
                    trans_var = model.NewBoolVar(
                        'transition (employee=%i, day=%i)' % (e, d))
                    transition.append(trans_var)
                    model.AddBoolOr(transition)
                    obj_bool_vars.append(trans_var)
                    obj_bool_coeffs.append(cost)

([シフトスケジュール問題を解くプログラムのソースコード]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)より引用)