量子アニーリングを活用した
個別指導塾向けの導入負担の少ない
コマ組自動化サービスの開発

取り組んだ内容

2023年度の未踏ターゲット事業で、個別指導塾におけるコマ組作業を量子アニーリング・イジングマシンを活用して自動化するサービス「塾コマ」の初期バージョンを開発しました。本サービスでは、講師・生徒・授業科目・時間帯の最適な割り当てを自動化することで、従来人手に頼っていた煩雑な作業の効率化を目指しています。2024年度の未踏ターゲット事業では、トライアルユーザーからのフィードバック等を踏まえて、追加機能の開発や使い勝手の改善などに取り組みました。

※ 2023年度のインタビュー記事はこちら

2024年度に取り組んだ中で最適化という観点で最も力を入れたのは、大規模なコマ組問題になった場合に、高精度かつ高速に解を導けるように問題分割の手法を工夫することです。 一般的に、夏期講習などがある長期休暇の際にコマ組は最も難しくなります。長期休暇において、通常の授業と長期休暇の授業をどのような考え方に基づいてコマ組を行うかなどの運用は塾によって大きく異なります。塾ごとに解くべき最適化問題の内容や規模も変わってきますが、それぞれの運用に合わせて、時間方向に問題を分割をしながらコマ組を行ったり、生徒ごとや教師ごとに問題を分割しながらコマ組を行ったり、といった形で内部的に適切な問題分割を行いながらコマ組ができるよう工夫しました。

※ コマ組とは：講師1人が生徒3人を教えるなどの個別指導形式において、どの時間帯にどの講師がどの生徒にどの科目を担当するかを決定する作業

組合せ最適化問題の概要

個別指導塾でのコマ組を自動化するため、講師・生徒・教科・出席可能日程などに対する多数の条件を考慮した多目的最適化問題として定式化しました。「1日あたりの最大のコマ数」や「教室の定員数」などの制約条件を満たしながら、「講師のコストの最小化」「講師・生徒の相性」「連続授業による運営効率の最大化」などの複数の目的を同時に最適化する問題です。

決定変数

ある時間帯において、講師と生徒の授業を実施するか否かを示すバイナリ変数。長期休暇の際は、最大で10万決定変数を超える大規模な問題になります。

講師 ×科目 × 生徒 × 日にち × 時間の5次元（授業を実施する場合は1、しない場合は0）

目的関数

• 講師の人件費の最小化
• 生徒と講師の相性
• 連続授業回数の最大化　など

制約条件

• 教室の定員制限
• 講師1人あたりの生徒上限（例：1対3）
• 生徒・講師の出席可能日程　など

苦労した点

塾へのヒアリングを通して、コマ割りの現場では、生徒に日程を入力してもらう際、「出席可能日」ではなく「出席不可能日」を入力してもらうことの方が多いことが分かりました。人間の心理的に出席可能日だと安全を見越して候補日が絞られるのに対して、出席不可能日とすると実際に不可能な日だけを入力する傾向があり、「出席可能な時間帯」が増えてコマ組を行いやすくなることが背景にあるようです。実験でもそのような傾向は確認できたのですが、出席可能な時間帯が増えたため、最適化問題としては大規模化することとなり求解が困難になりました。
この課題を解決するため、様々な問題分割の手法を試行錯誤することになりましたが、非常に地道な作業の繰り返しで苦労しました。ですがその過程で、大きな問題を一度で解くよりも適切に問題を分割して解いた方が、より高速で解の精度も上がることがあることが分かりました。内部的な問題分割の工夫を含めて、最終的に出席不可能日ベースの予定提出機能をリリースできたときは大きな達成感がありました。

嬉しかった点

量子アニーリング・イジングマシンを用いた多目的最適化では、目的関数間の重みを調整することで、その時々の好みに応じた計画を短時間で作成できるため、とても柔軟性が高いアプリを作ることができました。特に、ユーザーインターフェイスを通じたユーザーによるインプットと、実際の最適化計算に適用する重みをどう連携させるかは、腕の見せ所という感じで検討するのが楽しかったです。例えば、ユーザーインターフェイス上では「この講師にもう少しコマを割り振りたい」や「1コマ授業の先生の数をもう少し減らしたい」といった質問に対する回答を入力してもらい、裏では、その回答に基づいて各目的関数間の重みの調整を動的に行ったうえで再計算をするような形に工夫しています。また、一度計画を作った後に「やっぱりこの部分をもう少しこうしたいな」と思うことも多いのですが、すぐに再計算して計画を返してくれるので、あれもこれもといった感じで複数のパターンを気が済むまで試せるようなアプリにできたときは手ごたえを感じました。

今後の展望

すでにアプリの有償提供を開始していますが、今後は有償ユーザーの数を増やしていきたいと思っています。また、個別指導塾以外にもシフト作成が求められる業種は多く存在します。「塾コマ」で培った技術を活かし、他業種への展開も検討していきたいです。

見ている方に一言

量子最適化の分野は、大きな可能性を秘めていると感じています。組合せ最適化の現場適用に興味のある方、量子技術に可能性を感じている方と、ぜひ一緒にこの業界を盛り上げていけたら嬉しいです！

＊本記事の掲載内容は全て取材時の情報に基づいています