数理科学による業務支援：シフトの自動生成
はじめに
こんにちは。データ・サイエンティストの大澤です。普段はHOTLEADに搭載されているAIエンジン開発の他、統計分析、機械学習、数理最適化などを活用した業務改善に従事しています。
ビジネスの現場では、利益の最大化や業務効率化のために多様な意思決定を下す必要があります。産業界を見渡すと、商品の発注計画、物流拠点の配置、金融資産の運用、交通機関のダイヤ作成など、意思決定の質が事業に大きな影響を与える例をいくつも見つけることができます。homieにおける日々の意思決定も例外ではありません。意思決定の質を高く保つにはどうすればよいでしょうか。事業で直面する、一見関連がないように見える問題に共通した構造があるでしょうか。あるとすれば、その構造を利用して、たくさんの問題を統一された方法で解決することができるでしょうか。
こうした疑問に答えるには、数理科学的な方法が非常に効果的です。この記事では、勤務スケジュール（いわゆるシフト）の自動生成という問題を通じて、数理科学の成果をhomieでの業務改善に応用した事例を紹介します。
課題：シフトが作れない
homieが提供するサービスHOTLEADでは、弊社コンシェルジュが住宅・不動産事業者様に代わって反響の一次対応を行います。反響は時間帯や平日・休日を問わずに寄せられますので、それに対応できる体制を整える必要があります。一般的なホワイトカラーのように、全員が平日の日中に働いて、週末や祝日は休むわけにはいきません。毎日誰かしら出勤していなければなりませんし、寄せられる反響の規模に応じた人数が割当てられていないと、サービスの質が低下してしまいます。同時に、労働時間や勤務間インターバル、有給休暇の日程、希望休の充足などにも注意しなければなりません。事業上の需要を満たしながら、関連法規を守り、従業員への負荷を可能な限り抑えたシフトを作成する必要があります。
私がこの問題に着手するまでは、シフト作成の経験があるコンシェルジュが毎月手動でシフトを作成していました。もともと複雑な制約条件を扱わなければならなかったことに加えて、事業の成長に伴ってコンシェルジュの人数が増えたことで、シフト作成業務の負荷が高まっていました。シフトの作成は熟練が必要な業務で、それを担当できる人材は多くありません。組織の規模が大きくなったうえに、作成業務に従事する人材を採用できないことで、シフトを安定的に供給することができなくなりつつありました。
人手による運用が限界を迎えつつあったので、シフト作成の問題を最適化問題に帰着して、それを計算機に解かせることができないか検討することにしました。以下ではシフト作成を例に、最適化による問題解決の一般的な流れを説明します。
アプローチ
最適化による問題解決は大きく3つの段階にわけられます（図1）。決まった順番で1回だけ実行するものではなく、各段階で得られた結論を元に、他の段階での結論を再検討することがよくあります。
課題の整理
まず、求めたいことは何で、どんな条件を守らなければならないのか、計算機で扱えるように明確にする必要があります。今回のケースでは、誰がいつどのシフトに割当てられるのかを、指定した期間、全員分求めることが目的です。守らなければならない条件には、
1日に複数のシフトに割当てられない
法定労働時間の上限を超えない
各シフトに指定した人数以上の人員が配置される
などが含まれますが、これに限りません。人間は、計算機で扱えるほどの明瞭さで条件を把握していないこともあるので、数理科学の知識がある者が業務担当者に入念に取材しなければなりません。
モデリング
課題を整理できたら、その問題を数学的に表現します。この過程をモデリングと言います。幸い、シフトを作成する問題は勤務スケジューリング問題として定式化されており、よく研究されていて、モデリングや解法の例をたくさん見つけることができます。
勤務スケジューリング問題は、組合せ最適化問題（あるいは整数計画問題）の一種です。一般に、最適化問題は以下の3つの要素で構成されます。
決定変数
求めたい値を表現する変数。勤務スケジューリング問題では、どの人がいつどのシフトに勤務するかを表現する変数。
制約条件
決定変数が取りうる値の範囲を定める等式や不等式。勤務スケジューリング問題では、各シフトに必要な人員や月間の最低休日数など。
目的関数
最小化あるいは最大化したい指標の表現。勤務スケジューリング問題では、希望休の充足数（最大化）や負担の大きい勤務パターンの数（最小化）など。
最適化問題のうち、決定変数に離散値しか取れないものが含まれている問題を組合せ最適化問題と言います。組合せ最適化問題は、厳密解を得ることが難しいNP困難問題であることが多く、計算が現実的な時間で終わらないときの対処を考えておく必要があります。
解法とソルバの検討
最適化問題は、決定変数や制約条件、目的関数の性質によって、適用できる解法が異なります。組合せ最適化問題の場合、問題規模が小さく、目的関数と制約条件が線形であるときには、分岐限定法や切除平面法といった厳密解法の適用を検討します。そうでないときは、メタヒューリスティクスなどの近似解法の適用を検討します。
組合せ最適化問題を解くアルゴリズムを自力で実装するのは、厳密解法であれ近似解法であれ骨が折れる仕事です。幸い、一般的な組合せ最適化問題の解法を実装したソフトウェア（ソルバと呼ばれる）が商用・非商用を問わず多く存在します。どのソルバがどの解法を実装していて、その解法は自分の問題に適用できるのかどうかを把握する必要があります。
解の評価と問題定義の見直し
ソルバにモデルを入力して実行し、シフトを得ることができたら、そのシフトを業務担当者と共に評価します。仮に厳密解法が最適解を出力した場合でも、無条件にそれを受け入れるべきだとは限りません。
人間の頭脳は計算機とは違う考え方をします。自分が考えている条件を、計算機でも把握できるように明確にして全て列挙しろと言われても、完璧にはできないものです。計算機が出力したシフトを見ると、ここは何かがおかしいとか、言い忘れていたけどこの点も考慮してもらいたいとか、何かしら要望が出てきます。そういった新たな要望を明瞭に表現することができれば、それをモデルに取り込み、シフトの品質を改善することができます。
この際、計算時間に関する評価も行います。計算に非常に時間がかかっているなら、どの制約条件が足を引っ張っているのか、それを考慮することにはそれほどの価値があるのか、モデリング上の工夫はできないかなど、様々な観点から改善ができないかを探ります。計算時間に余裕がある場合、以前諦めた条件や、単純化しすぎた条件などを再考慮してもよいかもしれません。
実例
ここまで、数理モデリングによる問題解決の流れをある程度一般化して述べてきました。ここからは、homieにおいてシフト生成がどのように自動化されたかを、私の視点からお話しします。私自身、数理モデリングに挑戦するのは（統計分析や機械学習を除けば）初めてだったのですが、先人の偉大な業績と周囲の協力に助けられて、何とか成功させることができました。
課題の整理とソルバの調査
まずは教科書どおりに、シフト作成の際に考慮している制約条件をシフト作成者に列挙してもらうところから始めました。シフト作成者はもちろん数理科学にあまり明るくありませんから、最初に列挙してもらった条件にはかなり曖昧な表現が含まれていました。この条件はこういう意味ですか、それともこうですかと会議で執拗に尋ねたり、それを数理的に表現するのに苦労したりした記憶があります。
それと同時並行して、ソルバの調査も行いました。CPLEXやGurobi Optimizer、SCIPなどは、学術論文で引用されることが多いソルバですが、商用利用となるとライセンス料を支払わなければなりません。無料のソルバにはPuLPやOR-Toolsがあります。正確には、PuLPもOR-Toolsもソルバラッパーとも呼ぶべきもので、多数のソルバを統一されたインターフェースから呼び出すことができます。また、それぞれ独自のソルバを実装しています。問題形式が定まらないことにはソルバを決めづらいのですが、MiniZinc Challenge 2021という最適化問題のコンペティションで4つの金メダルを獲得した実績があるので、OR-Toolsの独自ソルバの利用を検討しました。
OR-Toolsの独自ソルバはCP-SATソルバと呼ばれます（参考リンク）。CP-SATソルバは、線形の純整数計画問題のソルバです。つまり決定変数が全て整数で、制約条件と目的関数は線形でなくてはなりません。列挙された制約条件を検討したところ、両方の条件を満たす形でモデリングできそうだったので、CP-SATソルバを採用する方向で検証を進めました。
モデリング上の問題と対策
検証を進める中で、問題が実行不能になるというトラブルに見舞われました。制約条件を満たす解が存在しない問題を実行不能であると言います。つまり矛盾した要求を課していたのです。そこで、比較的重要でない制約条件の違反を許して、その度合いを最小化することにしました。このような制約条件のことを考慮制約と言います。問題を組合せ最適化問題として定式化していると、考慮制約を自然にモデリングできます。違反度合いを表す決定変数を導入して、その線形和を目的関数に足せばよいのです。
制約条件をいくつか緩和したにもかかわらず、問題設定（チームの人数や月間休日数などの具体的な値）を変更すると、問題が実行可能になったり実行不能になったりする現象が見られました。運用上、最も懸念されたのは、問題がある日突然実行不能になり、どの制約条件がネックになっているのかを特定するのに時間がかかり、シフトの安定供給に支障が出ることでした。
そこで、本当に優先順位が高い条件（関連法規など）のみを制約条件として、他の条件は全て考慮制約とすることにしました。考慮制約の数が増えたことで、問題規模（≒決定変数の数）が増え、計算が現実的な時間で終わらなくなってしまいました。64コアの仮想マシンで100時間計算させても終わりませんでした。
教科書通りに行くならば、メタヒューリスティクスの導入を検討するところですが、他にも良い方法があります。OR-Toolsには、計算時間の上限を設定して、上限に達した場合にはその時点での暫定解を出力するというオプションがあるので、そちらを利用することにしました。メタヒューリスティクスを使ったとしても、近似解で我慢してもらうことになりますから、これでも良いでしょう。
最終的には、コンシェルジュをいくつかのチームに分割して、チームごとのシフトを出力する問題設定に切り替えました。この変更によって計算速度が飛躍的に速くなり、手元の開発マシンでも最適解が1分足らずで求められるようになりました。いくらCP-SATソルバが高速だとはいえ、指数時間のアルゴリズムですから、人数が1人増えれば計算時間は $${a}$$ 倍になります。 元のチームの人数を $${n}$$ 人とすると、計算時間は $${\mathcal{O}(a^n)}$$ です。このチームを2分割すると、各チームの計算時間が $${\mathcal{O}(a^{n/2})}$$ 、合計の計算時間が $${\mathcal{O}(2 a^{n/2})}$$ となり、 大幅な高速化になります。その分、シフトの柔軟性がやや失われますが、出力されたシフトを評価した結果、分割後のシフトでも問題ないと判断されました。
おわりに
理論的な側面の詳細をかなり省きましたが、数理最適化に基づく業務改善の事例を紹介しました。数理問題として扱う関係上、細やかな点まで配慮しづらかったり、計算機の都合に人間が合わせなければならない事態に直面することもありますが、数理科学にはそうした労力を吹き飛ばしてしまうくらいの威力があると思います。既によく研究されている問題に限らず、今後も多様な問題を数理科学に基づいて解決していきたいです。
またhomieでは一緒に働く仲間を絶賛募集中です。
数理最適化に限らず、エンジニアリングで課題解決をすることに興味をお持ちの方はぜひお問い合わせください。
参考文献
穴井宏和, 斉藤努 (著) 『今日から使える！組合せ最適化 離散問題ガイドブック』 講談社, 2015.
組合せ最適化問題の概論を述べた書籍です。組合せ最適化問題の全体像から問題の分類や解法まで解説されています。参考文献も充実していて、さらなる学習への起点にもなります。組合せ最適化問題に取り組む際のとっかかりとして非常に優秀です。
池上敦子 (著) 『ナース・スケジューリング』 近代科学社, 2018.
勤務スケジューリング問題の研究者が自身の業績について解説した書籍です。具体的なモデリングの技法や解法が載っています。
