内容
- AddBoolOrメソッドによる制約条件の実装の例を紹介しています。OR-Toolsのサンプルコードとして紹介されている、シフトスケジュール問題を解くプログラムを題材としています。
- 備忘のため、Googleの数理最適化ツールOR-Toolsの、cp_modelモジュールのCpModelクラスのAddBoolOrメソッドの使い方を、簡単にまとめてみました。
- OR-Toolsのエキスパートの方には少々退屈な内容かもしれません。初心者の方であれば、参考になるかもしれません。
注意事項
- 当方、OR-Toolsの初心者です。おおむね理解したつもりで書いていますが、もしかしたら間違っているところがあるかもしれません。ご容赦下さい。
- 制約条件の実装の仕方は、シフトスケジュールの表現の仕方や目的関数の設定の仕方によって、大きく変わってきます。ここで記載されたソースコードを流用する場合は、適宜変更した上で、ご利用下さい。
シフトスケジュール問題
- OR-Toolsのサンプルコードとして紹介されている、シフトスケジュール問題を解くプログラムを題材とする。
- シフトスケジュール問題では、以下のような問題を解いている。
- 8人の従業員の、3週間分の、シフトスケジュールを作る。1日の勤務は、午前／午後／夜間の3交代勤務を想定。
- シフトスケジュールには、以下の制約条件を反映する。
- 1日1シフトのみ(午前／午後／夜間のいずれか)の勤務とする(H)。
- あらかじめ指定した従業員のシフトは固定する(H)。
- なるべく、従業員のシフトの希望を反映する(S)。
- 連続する休暇は、1-2日間とする(H)。
- 連続する夜間の勤務は、1-4日間とする(H)。なるべく、2-3日間とする(S)。
- 一週間の休暇は、1-3日間とする(H)。なるべく、2日間とする(S)。
- 一週間の夜間勤務は、0-4日間とする(H)。なるべく、1-4日間とする(S)。
- なるべく、午後->翌日の夜間の勤務はしない(S)。
- 夜間->翌日の午前の勤務はしない(H)。
- なるべく、曜日／シフト毎に必要となる従業員数を確保する(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)より引用)