背景
私が所属しているAI戦略室では、社内で"AIお悩み相談会"を開催し「こんなことってできない?」というニーズに対して既存のツールやライブラリを組み合わせて解決策を探る、という業務も行っています。
例えば、 LIFULL HOME'S 住まいの窓口 というサービスがあります。これは、家づくりや住まい探しを、専属の住まい探しアドバイザーに無料で相談できるというサービスです。
この住まい探しアドバイザーのシフトを組む仕組みを自動化・最適化できないか?という問い合わせがあり、そこで見つけたGoogle ORtools の使い方の一つを今日はご紹介します。
例題
- あなたは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枠のシフトを組んだとすると、例えば以下のようなシフト表ができますね。
上の表を計算結果として出力するために、以下のように分解して、n, d, s
の「3次元配列状」にすれば、
- その要素に1が入っていれば出勤する
- 0が入っていれば出勤しない
とみなすことができます。
つまり、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の値でいいので素直に多次元配列として用意します。
- その要素に1が入っていれば出勤希望
- その要素に0が入っていれば出勤希望ではない
ことにすると、以下のような3次元配列として5人分のシフト希望が数値化できます。
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
アドバイザーのシフト希望をもっとも満たした解が出力できました。
Enjoy!