トップ > データ分析 > 数理最適化によって訪問介護のシフトスケジューリングモデルを作ってみた話

数理最適化によって訪問介護のシフトスケジューリングモデルを作ってみた話

データ分析 カイポケ

はじめに

医療・介護・ヘルスケア・シニアライフの4つの事業領域で高齢社会の情報インフラを構築している、株式会社エス・エム・エスのAnalytics&Innovation推進部（以下、A&I推進部）の新卒3年目の小貝です。現在は主に介護職向け求人情報サービスである「カイゴジョブ」のデータ分析・アルゴリズム開発を担当しています。

A&I推進部はエス・エム・エス社内のデータを横断的に収集し、データの分析や加工から、データに基づく施策展開までを行う部門です。部門の役割としては以下の3つが挙げられます。

  • 事業課題解決：事業会社のデータ活用組織として、PL貢献をする
  • 技術開発：データ活用組織としての専門性をもつ
  • 事業開発：専門性をお金に換える

そのなかで最も優先度が高いのは1つ目の事業課題解決なのですが、組織としての専門性を維持するために技術開発や事業開発にも取り組んでいます。 今回は私が技術開発の一環で行っていた、介護事業者向け経営支援サービスである「カイポケ」のデータを使った「数理最適化による訪問介護のシフトスケジューリングモデル開発」について紹介します。

数理最適化とは

数理最適化とは、「ある条件を満たしつつ、利益やコストなどの関数が最大or最小になる変数の値を求める手法」です。扱える問題の例として、

  • 300円以内で最も効用が高いおやつの組み合わせを求める（ナップザック問題）
  • 商品の配送先がいくつかあったとき、移動距離が最も短くなるような巡回の仕方を求める（巡回セールスマン問題）
  • ある駅からある駅への最安経路を求める（最短路問題）

などが挙げられます。身近なところだと、乗り換えや経路検索のアプリは内部で数理最適化アルゴリズムが動いています。 最近では、「機械学習によって予測した応募率をもとに、数理最適化によって期待応募数が最大になるように求人をレコメンドする」「機械学習によって商品の需要を予測し、数理最適化によって最も経済的な在庫数を決める」といったように、機械学習との相性が良いこともあり、企業での活用が進みつつある技術です。

医療・介護業界における「勤務シフト作成」の難しさ

数理最適化という分野の中で有名な問題の1つに「ナース・スケジューリング問題」があります。名前の通り、病院などで働く看護師の勤務シフトを作成する問題です。「そんなの簡単じゃないの？」と思う人もいるかもしれませんが、看護師のシフトには以下のように考慮しなければならないことがたくさんあります。

  • 各時間帯に◯人以上配備する必要があり、そのうち△人はベテラン看護師でなければならない
  • AさんはBさんのメンターなので同じ時間帯に入れる必要がある
  • 1人の看護師が2連続で夜勤をするのはNG
  • AさんとCさんは不仲なので同じ時間帯に入れてはいけない
  • すべての看護師さんで希望休の反映度合いを同じくらいにする必要がある（公平性）

…

これらすべての条件を満たしたシフトを、人間が作るのはかなり大変だと思われます。 実際、この問題の研究者が病院に行ったアンケートでは「勤務シフト作成にかかる時間は最大で30時間」「多くの人は勤務時間内ではなくプライベートの時間で作成している」「やりたくないと答えた人が90%」といった結果も出ています。 https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.41_08_436.pdf

ここまで複雑なのは看護師特有かもしれませんが、介護業界における介護ヘルパーでも同様に、勤務シフト作成の業務は発生しています。特に、ヘルパーが利用者の自宅を訪問する訪問介護では、介護士の勤務可能日時だけでなく、地理的な要素も考慮する必要がある（あまりにも遠くて非効率的な移動はさせたくない、など）ため、人間が手でシフトを作るのはなかなか大変だと思われます。 そこで今回は、数理最適化によって「訪問介護のシフトスケジューリング問題」を解いてみました（A&I推進部内に訪問介護のカイポケデータにとても詳しい人がいた、ということも訪問介護を扱うことにした大きな理由です）。

問題の整理・定式化

問題を解くために、「どういうデータが使えるのか」「どういう問題を解きたいのか」の整理をします。 カイポケには介護事業者の経営を支援する機能がいくつもありますが、その中に

  • 利用者のサービス提供予定を登録する
  • ヘルパーの勤務可能日時を登録する

という機能があります。今回はその2つを使って、利用者のサービス提供予定が与えられたとき、ヘルパーの勤務可能日時を守りながら自動で各サービスにヘルパーを割り当てる数理最適化モデルを作ってみました。また、カイポケ内には「実際にどのような割当がされていたか」というデータもあるので、モデルによる出力と比較もしてみます。

データとモデルによる出力の比較

先ほども書いたように、数理最適化は「ある条件を満たしつつ、利益やコストなどの関数が最大or最小になる変数の値を求める手法」なので、

  • どういう条件で（＝制約条件）
  • 何を最大化 or 最小化するか（＝目的関数）

の2つを決める必要があります。思考の過程は省略しますが、今回は以下のような問題を解くことにします。

  • 制約条件
    • 可能な限りすべてのサービスにヘルパーを割り当てる
    • 各ヘルパーの月間勤務時間の合計を一定の範囲内で収める（働かせすぎず、休ませすぎない）
      • これに関するデータはないので「各ヘルパーは1日8時間まで勤務できる」としました
    • 1人のヘルパーが同時にできないサービスには同時に割り当てない
      • ヘルパーを分身・瞬間移動させない
      • 遠すぎる移動もさせたくないので、移動距離が一定以上になるサービス（利用者宅）のペアも同時割当NGにしました
  • 目的関数
    • 未割当のサービスができたり、ヘルパーの勤務時間の合計が過不足した場合にペナルティを与え、それを最小化する

問題を数式に落とし込むことを分野特有(？)の言葉で「定式化」というのですが、今回の問題を定式化すると以下のようになります。なお、定式化にはこちらの書籍を参考*1にしました。https://www.kindaikagaku.co.jp/book_list/detail/9784764905580/ www.kindaikagaku.co.jp

データ
決定変数
minimize, subject to
※補足

  • データ：問題を解く前にわかっている入力データ
  • 決定変数：問題を解かないとわからない（求めたい）変数
  • 「minimize ～～～」：～～～（目的関数）を最小化する
  • 「subject to ～～～」：～～～を制約条件とする

Pythonによる数値実験

さて、問題の定式化ができたので、実際のカイポケデータを使って解いてみます。 数理最適化問題の解き方には大きく分けて「解を求めるアルゴリズムを自分で書く」「数理最適化ソルバーで解く」という2種類があります。とてもざっくり言うと、前者は解の探索手法や効率的な計算方法など競技プログラミング的なスキルが強く求められ、後者はソルバーで解ける形に数式を落とし込むという学術的な知識やスキルが求められるといった違いがあります。今回は個人的になじみのある、後者のソルバーを使ったやり方で解いてみます。 数理最適化ソルバーには有償・無償のものを含めいくつか種類があり、当然有償のほうが高性能ですが、今回はそこまで問題の規模が大きくないので、無償かつ商用フリーのCBCというソルバーを使います。また、ソルバーに問題を入力するラッパー（モデリング言語）としてPython-MIPを使います。先ほど定式化したものをPythonで実装すると以下のようになります。

https://github.com/coin-or/Cbc

https://www.python-mip.com

def model():
    '''
    ヘルパーごとの勤務時間量の上下限をなるべく守って各サービスに担当可能なヘルパーを割り当てる
    ヘルパーごとの移動範囲をコンパクトにするために、移動距離が大きい利用者のペアは1人のヘルパーに同時に割り当てない
    '''
    
    model = Model("model")
    model.emphasis = 1  # 最適性よりも実行可能であることを優先する
    model.verbose = 1  # ログを表示する
    model.preprocess = 1  # 定式化を解きやすくする
    
    # 変数の定義
    x, alpha, beta_m, beta_p = {}, {}, {}, {}
    
    for h in target_helper_id_list:


        # ヘルパーごとの勤務時間量の上下限を下回る/上回る量
        beta_m[h] = model.add_var(lb=0, name=f"beta_m_{h}")
        beta_p[h] = model.add_var(lb=0, name=f"beta_p_{h}")
        
        for s in target_shift_id_list:
            
            # ヘルパーhにシフトsを割り当てるとき1、それ以外は0になる変数
            x[h, s] = model.add_var(var_type=BINARY, name=f"x_{h}_{s}")
    
    for s in target_shift_id_list:
        
        # シフトsがどのヘルパーにも割り当てられなかったとき1、それ以外は0になる変数
        alpha[s] = model.add_var(var_type=BINARY, name=f"alpha_{h}_{s}")


    # 目的関数
    ## シフトにヘルパーが割り当てられなかったり、ヘルパーの勤務時間の過不足に関するペナルティを最小化する
    p1 = 10000  # シフトにヘルパーが割り当てられなかったときのペナルティ
    p2 = 10  # ヘルパーの勤務時間の過不足のペナルティ（1時間ごと）
    model.objective = minimize(xsum(p1 * alpha[s] for s in target_shift_id_list) + xsum(p2 * (beta_m[h] + beta_p[h]) for h in target_helper_ids))


    # 制約式
    for s in target_shift_id_list:
        
        ## すべてのシフトにヘルパーを割り当てる（アルファで緩和）
        model += (xsum(x[h, s] for h in target_helper_id_list) + alpha[s] == 1)


    for h in target_helper_id_list:
        
        ## ヘルパーごとに勤務時間量の上下限を守る
        model += (xsum(shifts_time_amounts[s] * x[h, s] for s in target_shift_id_list) >= low_time_amounts[h] - beta_m[h])
        model += (xsum(shifts_time_amounts[s] * x[h, s] for s in target_shift_id_list) <= upp_time_amounts[h] + beta_p[h])


        
        ## 勤務時間量の緩和制約
        model += (beta_m[h] <= low_time_amounts_ease[h] - low_time_amounts[h])
        model += (beta_p[h] <= upp_time_amounts[h] - upp_time_amounts_ease[h])
    
    # 同時に担当不可能なサービスには割り当てない
    for s1, s2 in overlapped_shifts:
        for h in target_helper_id_list:
            model += (x[h, s1] + x[h, s2] <= 1)


    model.__data = x, alpha, beta_m, beta_p
    return model

得られた結果と考察、課題

カイポケ内のデータにある10事業所に対して、今回の問題を解いてみたところ、以下のような結果が得られました。

得られた結果

「ヘルパー数」「利用者数」「サービス数」が入力データに関する情報、「実行時間」がソルバーによる計算にかかった時間を表しています。「ヘルパー1人あたりの移動時間」は、カイポケ内に記録されている実際のシフトでの移動時間と、今回作ったモデルの出力での移動時間、その差分を表しています。差分がマイナスなほど、モデルによって移動時間が大きく削減されていることを意味します。なお、地図上の直線距離から移動時間を計算していて、移動速度は簡単のため東京都では自転車移動を仮定して分速250m、東京都以外では車移動を仮定して分速500m（時速30km）としています。

これを見ると、まずおおむね実際よりも移動時間が短くなるシフトが得られていることがわかります。最大だとヘルパー1人あたり月間279分（＝4.6時間）もの移動時間の削減ができています。一方で、差分がプラスで削減されなかったケースもありますが、そこそこ効率的なシフトが「人の手を借りず自動で」得られたことにも価値はあると考えています。

また実行時間をみると、月間のサービス数が多いと実行時間が長くなることがわかります。特に、サービス数が1000を超えたあたりから急激に実行時間が伸びていそうです。今回はあくまでも技術開発として進めましたが、もしこのモデルによる「シフト自動作成機能」を実際にカイポケに組み込むとすると、月間サービス数が1000を超える大きい事業所には何らかの工夫をする必要がありそうです。

モデルの挙動をもう少し細かく見てみます。こちらの図は、とある事業所の一日のシフトを地図上に可視化したものです。

シフトの可視化A

色はヘルパーに対応し、①などの数字はヘルパーごとの訪問順を表します。左がカイポケ内に登録されている実際のシフト、右が今回のモデルによって得られたシフトです。 これらを比較すると、実際よりもモデルによるシフトのほうが遠距離の移動が減り、全体的にコンパクトに利用者宅を巡回していることがわかります。合計の移動時間も25分→15分に削減されており、「遠すぎる移動はさせない」という制約条件をモデルに組み込んだ効果が得られています。

一方で、望ましい結果が得られていないケースもあります。こちらの図は、先ほどと同じ事業所の別日のシフトを可視化したものです。

シフトの可視化B

これを見ると、たしかにモデルによるシフトのほうが移動時間は大きく削減されているものの、1シフトのためだけに出勤するヘルパーが増えてしまっていることがわかります。「ヘルパーを増やしたら移動時間も短くなる」というある意味当然の結果になってしまっており、これを改善するためには移動時間以外の効率性も考慮する必要がありそうです。

さいごに

今回はカイポケ内のデータと数理最適化の技術を使って、訪問介護のシフトスケジューリング問題を解いてみました。 簡単なモデルを作成して結果を見てみると、おおむね実際のシフトよりも効率的に移動するシフトが得られました。一方で、今回のモデルだと月間のサービス数が一定を超えると計算時間が急増したり、「移動時間が減るかわりに稼働するヘルパーが増える」といった微妙な結果になることもありましたが、改善のための示唆が得られたという点ではプラスだと思います。 そして何よりも、社内データを使って数理最適化の技術検証ができたというのは、A&I推進部にとって大きな意義があると考えています。数理最適化にかぎらず、今後もさまざまな技術を検証して、ゆくゆくは事業課題解決に役立てることができたら嬉しいです。

エス・エム・エスには数多くのサービスがあり、介護、医療に特化したデータを数多く保有しています。データサイエンスを活用したサービス向上ニーズも高く、今回のような技術開発にも力を入れています。今回の記事で少しでも興味を持って頂ける方がいらっしゃいましたら、ぜひお話を聞きに来ていただけたらと思います。

*1:シリーズ：最適化モデリング 第3巻 ナース・スケジューリング 問題把握とモデリング p.157