Top View
Author Yasuaki Hamano

Fixstars Amplify でナーススケジューリング問題を解く

2021/03/17

量子アニーリングとは？

最適化問題を解くことができると期待されている量子コンピュータです。量子コンピュータには量子ゲート方式と量子焼きなまし方式の2種類があり(他にももっとあるかも)、そのうちの一つです。鉄鋼の焼きなましから着想された手法だと言われています。

私自身が大学院で鉄鋼を使った研究をしていたことも有り、少し懐かしい気がします。また、実際に量子アニーリングを使って見るに当たり、研究室時代の先輩に鉄鋼の焼きなましについての授業をしてもらったりして、イメージを膨らませました。

Amplify を使って問題を解くとは？

  • 定式化

    • 制約条件を決める
    • コスト関数(制約条件を満たした上で、最小化したい値)を決める

  • コスト関数や制約条件の寄与度を決める (ハイパーパラメータチューニング)

  • 問題を解く

という流れです。詳細は、document をご覧ください。チュートリアルに、数独の解き方など面白い題材が載っています(これやった後、数独にハマって大変だった。。。たぶん、10時間ぐらい溶かした。。。)。

ナーススケジューリング問題とは？

看護師の勤務表を作ることが大変 という実課題を解くために設定された問題です。シフト制約とナース制約という2種類の制約を考える必要があります。

シフト制約

ある勤務日に、何人の看護師が出勤する必要があるか？ という、病院都合の制約です。特定の資格を持った看護師がX人、その他の看護師がY人 などの制約を加えると、より問題が複雑になります。

ナース制約

看護師個人に対する制約です。例えば、週末は連休を取りたい、とか、この日は休みたいとか、夜勤を4日連続で行うのはだめ、といった制約がこれに当たります。この人と働きたい などという制約を加え始めると、こちらもとても複雑な問題になっていきそうです。

問題

今回は、以下の問題を解いてみようと思います。 問題は、「ナース・スケジューリング：問題把握とモデリング シリーズ：最適化モデリング」 という本のp.24 、表2.3 に掲載されています。

この本は、ナーススケジューリング問題の重要性やそのアプローチが載っていてとても参考になるので、興味が有る方はぜひ手にとって御覧ください。

以下が、問題設定です。

------

シフト制約条件

  • 各日のシフト(昼・夜)で、2人のナースが出勤する必要がある

ナース制約条件

  • 休みは7回以上
  • 週末の連休は1回以上
  • 連続勤務は4日まで
  • 夜勤(N)の翌日の昼(D) は休みにする
  • 夜勤は3連続まで

可能であれば

  • 前後の日が休みとなる、一日だけの孤立勤務は避ける
  • 4連続勤務を避ける。避けられない場合は、直後の2日を休みにする

------

シフト制約条件、ナース制約条件 が制約条件で、可能であれば の部分がコスト関数に該当します。

サンプルとして表示されていた勤務表は、以下の通りです。0が月曜日、6が日曜日です。

012345678910111213休みDN週末連休
0NNNNDND7251
1NNDNNDD7341
2NNNDDDD7431
3NNDDNNN7251
4NNDDDDN7431
5DDNNNDD7431
6DDDDNNN7431
7DDDDDNN7521
D22222222222222
N22222222222222

では、上記の流れに従って問題を解いていきます。

問題を解いていく！

環境は、Google Colaboratory を使用しました。 はじめに、amplify sdk をインストールし、Google Drive をマウントします。 Google Drive に鍵を置いておくと、何かと便利です。 画面共有するときも安全だし、そのままShare しちゃっても大丈夫だし！！！

!pip install amplify
from google.colab import drive
drive.mount('/content/drive')

from pathlib import Path
from amplify import decode_solution
from amplify import Solver
from amplify.client import FixstarsClient
from amplify import BinaryQuadraticModel
from amplify import BinaryPoly

from amplify import (
    decode_solution,
    gen_symbols,
    pair_sum,
    sum_poly,
    Solver,
)
from amplify.client import FixstarsClient
from amplify.constraint import (
    equal_to,
    less_equal,
    greater_equal,
    penalty,
)

量子コンピュータに入れる量子ビット(的なやつ？)を作成します。

nurses = 8
days = 28 # 問題は14日だが、後述の理由により28 としている
table = gen_symbols('Binary', 0, (nurses, days))

これで、準備は完了です。

gen_symbols で作成される配列について

table[看護師ID][日付ID] という感じで、変数にアクセスできます。 ここで、一点事項注意があります。 与えられた問題では、看護師ID n, 日付 d が null, D, N の3つの値を取りますが、量子コンピュータは、True or False の2値しか取れません。 そこで、今回は、

1日 昼1日 夜
看護師1ox
看護師2xx
看護師3ox

みたいな感じで取り扱っています。 以下では、量子コンピュータの出力した結果が1 のとき出勤、 0 のときおやすみとして取り扱います。

これで準備が整いました。が、一点注意事項です。現時点で 週末の連休は1回以上 の条件を入れると問題が解けないので、その部分だけはチートして、予め休みの希望をもらっているという設定にしています。

以下のように BinaryPoly を使用して、値を代入すると、その値は固定されるみたいです。(参考: https://amplify.fixstars.com/docs/sudoku.html)

for i in range(people):
    if i < 4:
        table[i][10] = BinaryPoly(0)
        table[i][11] = BinaryPoly(0)
        table[i][12] = BinaryPoly(0)
        table[i][13] = BinaryPoly(0)
    else:
        table[i][24] = BinaryPoly(0)
        table[i][25] = BinaryPoly(0)
        table[i][26] = BinaryPoly(0)
        table[i][27] = BinaryPoly(0)

定式化

シフト制約

# シフト制約: 各勤務日・勤務時刻には、2人勤務する
shift_constraints = []
for d in range(days):
    tmp = []
    for i in range(people):
        tmp.append(table[i][d])
    shift_constraints.append(equal_to(sum(tmp), 2))

ナース制約

週末の連休は1回以上

この条件については、上述の通り、 BinaryPolyで設定済み。

昼勤と夜勤に連続では入れない

これは、制約条件としては明示されていませんが、問題設定上暗黙のルールが存在します。

# ナース制約: 昼と夜の連続勤務はできない
day_and_night_in_same_day = []
for d in range(0, days, 2):
    tmp = []
    for p in range(people):
        #                   昼          * 夜 = 0
        tmp.append(equal_to(table[p][d] * table[p][d+1], 0))
    day_and_night_in_same_day.append(sum(tmp))

夜勤(N)の翌日の昼(D)は休みにする

night_next_morning_is_off = []
for d in range(0, days, 2):
    tmp = []
    if d + 2 >= days:
        continue
    for p in range(people):
        # 夜勤と 次の日の昼勤は、一緒に1 にはならない => 掛け算すると0 になる
        tmp.append(equal_to(table[p][d+1] * table[p][d+2], 0))
    night_next_morning_is_off.append(sum(tmp))

休みは7回以上

more_than_7_days_off = []
for p in range(people):
    tmp = []
    for d in range(days):
        tmp.append(table[p][d])
    # 休みが7日 => 出勤が7日以下 => 出勤日の合計が7以下という制約
    more_than_7_days_off.append(less_equal(sum(tmp), 7))

連続勤務は4日まで

# 連続勤務は4日まで
continue_service = []
for p in range(people):
    for d in range(days - 10):
        tmp = []
        # 5日分のbit を取得
        # 5日で 1 となるbit が 4 つ以下になるように制約をかける
        for i in range(10):
            tmp.append(table[p][d+i])
        continue_service.append(less_equal(sum(tmp), 4))

夜勤は3連続まで

# 夜勤は連続3日まで
continue_service_nights = []
for p in range(people):
    # 夜勤の日だけ抽出したい
    for d in range(days//2):
        if d+2 * 4 >= len(table[p]):
            continue
        tmp = []
        # 4日後までの夜勤を抽出
        for i in range(4):
            tmp.append(table[p][d+2 * i])
		# 足すと3 以下になるという制約をかける
        continue_service_nights.append(less_equal(sum(tmp), 3))

以上が制約条件です。より詳細に問題を解くためには、 可能であれば の部分をコスト関数として実装してあげることができます。今回は、コスト関数を入れて問題を解く方法が見つかっていないので、割愛いたします。

ここまで来ると、それぞれの制約条件を足し合わせます。

constraints = sum(shift_constraints) + \
  sum(day_and_night_in_same_day) + \
  sum(night_next_morning_is_off) + \
  sum(more_than_7_days_off) + \
  0.1 * sum(continue_service) + \
  0.1 * sum(continue_service_nights)

continue_service やcontinue_service_nights にかけられている 0.1 は、ハイパーパラメータです。 この値を調整することにより、制約の強さを調整できるようです。これ、探すのがけっこう大変ですｗ 今回は、これらの値を設定することにより、10 秒以内で結果が返ってくるようになりました。

ここで、以下のように便利関数を定義しておきます。 こうすることで、結果が見やすくなります(本当は、table とかで書くとよいのだけど、ちょっとめんどくさくて)。

import numpy as np
def reconstruct_and_print_schedule(sol):
    """
    decode_solution した値をこれに食わせると、
    markdown 的な何かを出力してくれる！
    """
    day_length = len(sol[0]) // 2
    print("|" + "|".join([str(i) for i in range(1, day_length + 1)]) + "|sum|")
    print("|:-"*(day_length+1) + "|")
    d = []
    n = []
    for person in range(people):
        d_tmp = []
        n_tmp = []
        s = "|"
        for day in range(0, days, 2):
            dn = False
            d_tmp.append(0)
            n_tmp.append(0)
            if sol[person][day] == 1:
                d_tmp[-1] = 1
                s += 'D'
            if sol[person][day+1] == 1:
                n_tmp[-1] = 1
                s += 'N'
            s += '|'
        d.append(d_tmp)
        n.append(n_tmp)
        s += f"{sum(d_tmp) + sum(n_tmp)}|"
        print(s)
    npd, npn = np.array(d), np.array(n)
    print("|",  '|'.join(map(str, npd.sum(axis=0).tolist())),"|")
    print("|",  '|'.join(map(str, npn.sum(axis=0).tolist())),"|")
    return np.array(d), np.array(n)

さて、ここまでできたら、あとは Fixstars Amplify に投げて、結果を見てみます。

def get_token(solver_type = "Fixstars"):
    # Google Drive の、 quantum_tokens の中に、 fixstars.txt というファイルを置き、その中にToken を入れている。
    base_path = Path("/content/drive/MyDrive/quantum_tokens/")
    if solver_type == 'Fixstars':
        filename = base_path / 'fixstars.txt'
    else:
        raise ValueError("SOLVER TYPE IS NOT DEFINED")

    with open(filename, 'r')  as f:
        content = f.read()
    return content
def get_solver(solver_type = "Fixstars", timeout=1):
    if solver_type == 'Fixstars':
        client = FixstarsClient()
        client.token = get_token(solver_type)
        client.parameters.timeout = timeout * 1000  # タイムアウト1秒

        solver = Solver(client)
    else:
        raise ValueError("SOLVER TYPE IS NOT DEFINED")
    return solve

solver = get_solver('Fixstars', 10)
solver.filter_solution = False

model = BinaryQuadraticModel(constraints)
result = solver.solve(model)

if not result[0].is_feasible:
    print("no solutions")

# decode_solution は、便利関数。めっちゃ便利。
# table (bit の集合) に、値を当てはめてくれます。
decoded = decode_solution(table, result[0].values)

# 結果の表示
reconstruct_and_print_schedule(decoded)

出力は、

|1|2|3|4|5|6|7|8|9|10|11|12|13|14|sum|
|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|
|||D|N||||D||D||D|N|N|7|
|N||D||N|||D|D||||D|D|7|
|D||N||D||||D|N|||D|D|7|
||N||D||||N|N||N||N|N|7|
|D|D|||N|N|N||||D|N|||7|
||N||D||D|D|N|||D|D|||7|
|N|||N||D|D||N|N|N||||7|
||D|N||D|N|N|||D||N|||7|
| 2|2|2|2|2|2|2|2|2|2|2|2|2|2 |
| 2|2|2|2|2|2|2|2|2|2|2|2|2|2 |

のようになっています。

これを、Colabのテキストセルに貼り付けると、、、

1234567891011121314sum
DNDDDNN7
NDNDDDD7
DNDDNDD7
NDNNNNN7
DDNNNDN7
NDDDNDD7
NNDDNNN7
DNDNNDN7
22222222222222
22222222222222

という感じの表が出てきます。

ここで、制約条件をちゃんと満たしているかをおさらいしてみましょう。

シフト制約条件

  • 各日のシフト(昼・夜)で、2人のナースが出勤する必要がある

    • 最後の2行が、それぞれ昼勤の人の数、夜勤の人の数 になっています。
    • 全部2 なので、ちゃんと制約を満たせていることがわかります。

ナース制約条件

  • 休みは7回以上

    • 最後の列が、各ナースの出勤数を表しています。
    • 14日あって全員出勤数が7 なので、きちんと制約を満たせています。

  • 週末の連休は1回以上

    • BinaryPoly で設定した値です。
    • 6, 7, 13, 14 の列がそれぞれ土日なので、きちんと制約を満たせています。

  • 連続勤務は4日まで

    • 目視で確認しました。きちんと制約を満たせています。

  • 夜勤(N)の翌日の昼(D) は休みにする

    • 目視で確認しました。きちんと制約を満たせています。

  • 夜勤は3連続まで

    • 目視で確認しました。きちんと制約を満たせています。

ということで、無事制約を満たせていることが確認できました。本当は、チェックする処理までちゃんとコード書けばよかったんですけど、サボっちゃいました。。。

Yasuaki Hamano

Yasuaki Hamano

I'm a software engineer in Fukuoka, Japan. Recently, I am developing machine learning models using TensorFlow, and also developing Web services by using PHP.