内容

Googleの数理最適化ツールOR-Toolsのサンプルコードとして公開されている、シフトスケジュール問題を解くプログラムに、解説がついていなかったため、勉強がてら、解読してみました。
その1では、「シフトスケジュール問題を解くプログラムの概要」をまとめています。目次は、以下の通りです。
- シフトスケジュール問題の概要
- シフトの表現
- 目的関数
- 制約条件
  - ハード制約条件
  - ソフト制約条件
別途、制約条件をいくつか抜粋して、実装の仕方の例を紹介する予定です。
OR-Toolsのエキスパートの方には少々退屈な内容かもしれません。初心者の方であれば、参考になるかもしれません。

注意事項

当方、OR-Toolsの初心者です。おおむね理解したつもりで書いていますが、もしかしたら間違っているところがあるかもしれません。ご容赦下さい。

(1) シフトスケジュール問題の概要

シフトスケジュール問題を解くプログラムでは、以下の問題を解いている。
- 8人の従業員の、3週間分の、シフトスケジュールを作る。1日の勤務は、午前／午後／夜間の3交代勤務を想定。
- シフトスケジュールには、以下の制約条件を反映。
  1. 1人、1日、1シフトのみ(午前／午後／夜間のいずれか)の勤務とする(H)。
  2. あらかじめ指定した従業員のシフトを固定する(H)。
  3. なるべく、従業員のシフトの希望を反映する(S1)。
  4. 連続する休暇は、1-2日間とする(H)。
  5. 連続する夜間の勤務は、1-4日間とする(H)。なるべく、2-3日間とする(S1)。
  6. 一週間の休暇は、1-3日間とする(H)。なるべく、2日間とする(S2)。
  7. 一週間の夜間勤務は、0-4日間とする(H)。なるべく、1-4日間の範囲とする(S2)。
  8. なるべく、午後->翌日の夜間の勤務はしない(S1)。
  9. 夜間->翌日の午前の勤務はしない(H)。
  10. なるべく、曜日／シフト毎に必要となる最小の従業員数を確保する(S2)。必要以上の従業員数とせざるを得ない場合は、なるべく人数を減らす(S2)。
- (H)の項目は、必ず満たさなければならない条件(ハード制約条件)。
- (S1)、(S2)の項目は、必ずしも満たさなくても良いが満たした方が良い条件(ソフト制約条件)。
  - (S1)の項目は、シフトの組合せに応じて、反映される度合いが変わらない制約条件。
  - (S2)の項目は、シフトの組合せに応じて、反映される度合いが変わる制約条件。

(2) シフトの表現

ブール変数work[e, s, d]で、従業員eの、d日目の、シフトsの勤務の状態を表している。
- シフトsは、0:休暇／1:午前勤務／2:午後勤務／3:夜間勤務のいずれかを示す値。
  - 休暇もシフトの1つとして取扱うようにしている。
- work[e, s, d]=True(=1)となったら、従業員eが、d日目の、シフトsの勤務に割り当てられたことになる。

(3) 目的関数

ブール変数obj_bool_vars[i]や整数の変数obj_bool_int_vars[i]に、係数を掛けて、足し合わせた値を目的関数としている。この目的関数の値を最小化することにより、種々の制約条件を満たすシフトスケジュールを作るようにしている。

\sum_{i}{obj\_bool\_vars[i]*obj\_bool\_coeffs[i]} + \sum_{j}{obj\_int\_vars[j] * obj\_int\_coeffs[j]}

ブール変数obj_bool_vars[i]の項には、ブール変数workに、係数wを掛けて、足し合わせた値も含まれている。

\sum_{e}\sum_{d}\sum_{s}{work[e, s, d] * w}

取扱う制約条件によって、ブール変数obj_bool_vars[i]の項と整数の変数obj_bool_int_vars[j]の項を使い分けている。
- ブール変数obj_bool_vars[i]の項
  - ハード制約条件や(S1)のソフト制約条件を実装するのに用いる。
- 整数の変数obj_bool_vars[j]の項
  - (S2)のソフト制約条件を実装するのに用いる。

(4) 制約条件

(4.1) ハード制約条件

ハード制約条件は、基本的には、ブール変数work[e, s, d]の値に、直接制約を課すことにより、実装している。

　(例) あらかじめ指定した従業員のシフトを固定する(H)。

従業員eを、d日目の、シフトsに割り当てたい場合は、以下の通り、ブール変数work[e, s, d]をTrue(=1)に固定する制約を加える。

    # Fixed assignments.
    for e, s, d in fixed_assignments:
        model.Add(work[e, s, d] == 1)

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

(4.2) ソフト制約条件

ソフト制約条件は、基本的には、ブール変数obj_bool_vars[i]の値に、ペナルティを表す係数を掛けた値を、目的関数に加え、それを最小化することにより、実装している。

　(例) なるべく、従業員のシフトの希望を反映する(S)。

なるべく、従業員eを、d日目の、シフトsに割り当てたい場合は、以下の通り、ブール変数work[e, s, d]の値に、ペナルティwを掛けた値を、目的関数に加える。
目的関数を最小化するので、ペナルティwに、負の値を設定しておくと、指定したシフトに、優先的に、割り当てることができる。

    # Employee requests
    for e, s, d, w in requests:
        obj_bool_vars.append(work[e, s, d])
        obj_bool_coeffs.append(w)

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

シフトの組合せに応じて、反映される度合いを変えたい場合は

シフトの組合せに応じて、反映される度合いが変わる制約条件の場合は、ブール変数obj_bool_vars[i]の項の代わりに、整数の変数obj_int_vars[i]の項を用いる。整数の変数obj_int_vars[i]の値に、ペナルティを表す係数を掛けた値を、目的関数に加え、それを最小化する。
- 例：なるべく、曜日／シフト毎に必要となる最小の従業員数を確保する(S2)。必要以上の従業員数とせざるを得ない場合は、なるべく人数を減らす(S2)。
  - なるべく、曜日／シフト毎の従業員数が、必要最小の従業員数に近くなるようにしたい場合は、両者の差異excessを、整数の変数obj_int_vars[j]の値に設定し、そこにペナルティover_penaltyを掛けた値を、目的関数に加える。
  - 目的関数を最小化するので、ペナルティover_penaltyに、正の値を設定しておくと、曜日／シフト毎の従業員数が必要最小の従業員数を超える、シフトの組合せには、なりにくくなる。excessが大きくなるほど、その度合いが強くなる。

    # Cover constraints
    for s in range(1, num_shifts):
        for w in range(num_weeks):
            for d in range(7):
                works = [work[e, s, w * 7 + d] for e in range(num_employees)]
                # Ignore Off shift.
                min_demand = weekly_cover_demands[d][s - 1]
                worked = model.NewIntVar(min_demand, num_employees, '')
                model.Add(worked == sum(works))
                over_penalty = excess_cover_penalties[s - 1]
                if over_penalty > 0:
                    name = 'excess_demand(shift=%i, week=%i, day=%i)' % (s, w,
                                                                         d)
                    excess = model.NewIntVar(0, num_employees - min_demand,
                                             name)
                    model.Add(excess == worked - min_demand)
                    obj_int_vars.append(excess)
                    obj_int_coeffs.append(over_penalty)

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

参考資料

OR-Toolsのインストール
OR-ToolsのGet Started Guides
Employee Schedulingのサンプルコード(解説付き、ここで紹介しているものとは別のサンプルコード)