LoginSignup
TrendQuestionOfficial EventOfficial ColumnOpportunitiesOrganization
11
5

More than 3 years have passed since last update.

lifull

LIFULL Advent Calendar 2019 Day 5

@wakuteka(株式会社LIFULL)

posted at

updated at

Organization

５等分のシフト埋め

Python,ortools

背景

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

例えば、 LIFULL HOME'S 住まいの窓口 というサービスがあります。これは、家づくりや住まい探しを、専属の住まい探しアドバイザーに無料で相談できるというサービスです。

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

image.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 をごらんください。

from ortools.sat.python import cp_model

model = cp_model.CpModel()

変数を用意する

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

n人のアドバイザーに対し、d日間、s枠のシフトを組んだとすると、例えば以下のようなシフト表ができますね。
image.png

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

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

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

image.png

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

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

    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を使って擬似的に多次元配列っぽく使えるものを用意します。

    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つしかフラグが立っていないようにします。

    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つしかフラグが立っていないようにします。

    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次元配列」の図で、アドバイザーごとの平面の表のフラグの数を全部足して、その結果が下限の制約値以上、上限の制約値以下になるようにします。

    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

  • その要素に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という関数に渡してあげることで、最適化条件をソルバに指示することができます。

    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))

プログラム全体

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

Enjoy!

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
Sign upLogin
11
5