５等分のシフト埋め

# 背景
私が所属しているAI戦略室では、社内で"AIお悩み相談会"を開催し「こんなことってできない？」というニーズに対して既存のツールやライブラリを組み合わせて解決策を探る、という業務も行っています。

例えば、 [LIFULL HOME'S 住まいの窓口](https://www.homes.co.jp/counter/) というサービスがあります。これは、家づくりや住まい探しを、専属の住まい探しアドバイザーに無料で相談できるというサービスです。

この住まい探しアドバイザーのシフトを組む仕組みを自動化・最適化できないか？という問い合わせがあり、そこで見つけた[Google ORtools](https://developers.google.com/optimization) の使い方の一つを今日はご紹介します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12353/e5632ea0-56d0-4e94-c8b7-61192cad0c6b.png)

# 例題

* あなたは5人の住まい探しアドバイザーのシフトを組むことになりました。
    * 図示するときに便利なので、仮に一花、二乃、三玖、四葉、五月という名前をつけます。
* 問題を簡略化するため、1店舗のシフトだけを考えればいいとします。
* 1日3枠×7日間の予約可能な枠があります。
    * 相談室は1つしかなく、同時に2人が顧客対応する（予約を受ける）ことはできないとします。
    * 相談業務はハードなので、アドバイザーは1日1枠しかシフトを入れることができないとします。
* 5人の間には、なるべく時間の偏りが出ないほうが望ましいです。
* アドバイザーの出勤希望を、なるべく満たすようにシフトを組むのが望ましいです。

## 制約充足問題として解く

このようなスケジューリングの問題は、制約充足問題（CSP）として解けることがあります。

満たすべき条件がいくつか課されていますが、大きく

* その制約(constraint)を満たせば良い条件
* 最適化(optimize)したい条件

に分けて考えることができれば、あとはソルバを使って解けます。

制約条件を満たす解をソルバに算出してもらい、あとは最適化したい条件を指定すればよいのです。
ここでは、

* 同時に2人は同じシフトに入れない
* アドバイザーは1日1枠しかシフトに入れない
* なるべく時間の偏りが出ないようにする

という条件を制約条件にして、

* アドバイザーの出勤希望をなるべく多く叶える

という値を最適化することにします。

## モデルを宣言する
まず、ソルバーのモデルを用意します。
ここでは、CP-SATモデルを使います。
詳細は https://developers.google.com/optimization/cp/cp_solver をごらんください。

```{python}
from ortools.sat.python import cp_model

model = cp_model.CpModel()
```

## 変数を用意する
次に、スケジューリングのフラグに使うための変数を用意します。

n人のアドバイザーに対し、d日間、s枠のシフトを組んだとすると、例えば以下のようなシフト表ができますね。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12353/0eab3663-f806-6cfe-d425-f618679534ff.png)

上の表を計算結果として出力するために、以下のように分解して、`n, d, s` の「3次元配列状」にすれば、

* その要素に1が入っていれば出勤する
* 0が入っていれば出勤しない

とみなすことができます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12353/8947c365-64b4-6315-c210-b59a41074fce.png)

つまり、`n, d, s`の「3次元配列」のどこにフラグをたてるか、という問題に落とし込めたわけです。

今回の例題に沿って、定数を定義してみます。

```{python}
    num_advisers = 5
    num_shifts = 3
    days = ["日", "月", "火", "水", "木", "金", "土"]
    num_days = len(days)
    adviser_name = ["五月", "一花", "二乃", "三玖", "四葉"]
    all_advisers = range(num_advisers)
    all_shifts = range(num_shifts)
    all_days = range(num_days)
```

0 or 1のフラグを立ててソルバに解いてもらうための変数は、`'ortools.sat.python.cp_model.IntVar'`クラスのインスタンスとして作るので、dictを使って擬似的に多次元配列っぽく使えるものを用意します。

```{python}
    shifts = {}
    for n in all_advisers:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))
```

## 制約条件を入れる

制約条件は`model.Add()`で入れていきます。

**同時に2人は同じシフトに入れない：**
「3次元配列」の図を"上"から見たときに、1つしかフラグが立っていないようにします。

```{python}
    for d in all_days:
        for s in all_shifts:
            model.Add(sum(shifts[(n, d, s)] for n in all_advisers) == 1)
```

**アドバイザーは1日1枠しかシフトに入れない:**
「3次元配列」の図を"前"から見たときに、1つしかフラグが立っていないようにします。

```{python}
    for n in all_advisers:
        for d in all_days:
            model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 1)
```

**なるべく時間の偏りが出ないようにする:**
`3 × 7 = 21`枠あるのだから、`21//5 = 4` 枠を下限にして、
`(21//5) + 1 = 5`枠をアドバイザーごとの上限にすれば偏りが出なそうですね。
「3次元配列」の図で、アドバイザーごとの平面の表のフラグの数を全部足して、その結果が下限の制約値以上、上限の制約値以下になるようにします。

```{python}
    min_shifts_per_adviser = (num_shifts * num_days) // num_advisers
    max_shifts_per_adviser = min_shifts_per_adviser + 1
    for n in all_advisers:
        num_shifts_worked = sum(
            shifts[(n, d, s)] for d in all_days for s in all_shifts)
        model.Add(min_shifts_per_adviser <= num_shifts_worked)
        model.Add(num_shifts_worked <= max_shifts_per_adviser)
```

## 時間帯の希望を受け付ける

次に、「この日のこのシフトに入りたい！」という希望を数値化します。こちらは素の0 or 1の値でいいので素直に多次元配列として用意します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12353/1ef918c5-3e67-487f-24cb-5ece6ef93b60.png)

* その要素に1が入っていれば出勤希望
* その要素に0が入っていれば出勤希望ではない

ことにすると、以下のような3次元配列として５人分のシフト希望が数値化できます。

```
    shift_requests = [
            [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
            [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],   # 一花
            [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
            [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
            [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]
            ]
```

ここで、shiftsに値が入っているとき、`shift_requests[n][d][s] * shifts[(n, d, s)]` の計算を各要素ごとに行うと、
「その要素がアドバイザーの希望を満たせた場合」のみ計算結果が1になります。
これをmodel.Maximizeという関数に渡してあげることで、最適化条件をソルバに指示することができます。

```{Python}
    model.Maximize(
        sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_advisers
            for d in all_days for s in all_shifts))
```


https://developers.google.com/optimization/scheduling/employee_scheduling


# プログラム全体

```{python}
from ortools.sat.python import cp_model


def main():
    # This program tries to find an optimal assignment of advisers to shifts
    # (3 shifts per day, for 7 days), subject to some constraints (see below).
    # Each adviser can request to be assigned to specific shifts.
    # The optimal assignment maximizes the number of fulfilled shift requests.
    num_advisers = 5
    num_shifts = 3
    days = ["日", "月", "火", "水", "木", "金", "土"]
    num_days = len(days)
    adviser_name = ["五月", "一花", "二乃", "三玖", "四葉"]
    all_advisers = range(num_advisers)
    all_shifts = range(num_shifts)
    all_days = range(num_days)
    shift_requests = [
            [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
            [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],
            [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
            [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
            [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]
            ]
    # Creates the model.
    model = cp_model.CpModel()

    # Creates shift variables.
    # shifts[(n, d, s)]: adviser 'n' works shift 's' on day 'd'.
    shifts = {}
    for n in all_advisers:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

    # Each shift is assigned to exactly one adviser in .
    for d in all_days:
        for s in all_shifts:
            model.Add(sum(shifts[(n, d, s)] for n in all_advisers) == 1)

    # Each adviser works at most one shift per day.
    for n in all_advisers:
        for d in all_days:
            model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 1)

    # min_shifts_assigned is the largest integer such that every adviser can be
    # assigned at least that number of shifts.
    min_shifts_per_adviser = (num_shifts * num_days) // num_advisers
    max_shifts_per_adviser = min_shifts_per_adviser + 1
    for n in all_advisers:
        num_shifts_worked = sum(
            shifts[(n, d, s)] for d in all_days for s in all_shifts)
        model.Add(min_shifts_per_adviser <= num_shifts_worked)
        model.Add(num_shifts_worked <= max_shifts_per_adviser)

    model.Maximize(
        sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_advisers
            for d in all_days for s in all_shifts))
    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    solver.Solve(model)
    for d in all_days:
        print(days[d] + "曜日:")
        for s in all_shifts:
            for n in all_advisers:
                if solver.Value(shifts[(n, d, s)]) == 1:
                    if shift_requests[n][d][s] == 1:
                        print('Adviser', adviser_name[n], 'works shift', s, '(requested).')
                    else:
                        print('Adviser', adviser_name[n], 'works shift', s, '(not requested).')
        print()

    # Statistics.
    print()
    print('Statistics')
    print('  - Number of shift requests met = %i' % solver.ObjectiveValue(), '(out of', num_advisers * min_shifts_per_adviser, ')')
    print('  - wall time       : %f s' % solver.WallTime())


if __name__ == '__main__':
    main()
```

##出力結果:

```
日曜日:
Adviser 四葉 works shift 0 (not requested).
Adviser 二乃 works shift 1 (requested).
Adviser 三玖 works shift 2 (requested).

月曜日:
Adviser 一花 works shift 0 (not requested).
Adviser 二乃 works shift 1 (requested).
Adviser 四葉 works shift 2 (requested).

火曜日:
Adviser 三玖 works shift 0 (requested).
Adviser 一花 works shift 1 (requested).
Adviser 四葉 works shift 2 (not requested).

水曜日:
Adviser 二乃 works shift 0 (requested).
Adviser 一花 works shift 1 (requested).
Adviser 五月 works shift 2 (not requested).

木曜日:
Adviser 四葉 works shift 0 (requested).
Adviser 三玖 works shift 1 (not requested).
Adviser 五月 works shift 2 (requested).

金曜日:
Adviser 三玖 works shift 0 (requested).
Adviser 五月 works shift 1 (requested).
Adviser 一花 works shift 2 (not requested).

土曜日:
Adviser 二乃 works shift 0 (not requested).
Adviser 四葉 works shift 1 (not requested).
Adviser 五月 works shift 2 (requested).


Statistics
  - Number of shift requests met = 13 (out of 20 )
  - wall time       : 0.007237 s
```

アドバイザーのシフト希望をもっとも満たした解が出力できました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12353/0eab3663-f806-6cfe-d425-f618679534ff.png)

**Enjoy!**