[1F3-GS-1] 基礎・理論：

[1F3-GS-1-03] 制約と変数の貢献度に基づく説明可能な計画最適化のための分枝限定法の高速化

〇土屋 祐太¹、濱本 真生¹ (1. 株式会社日立製作所)

キーワード：シャープレイ値、数理最適化、スケジューリング、説明可能なAI、分枝限定法

労働人口の減少に伴う業務のデジタル化が求められる中、属人化されやすい制約条件や評価指標を明示的にモデリングできることから、数理最適化を用いた計画立案の自動化が発展している。ただし、様々な条件が複雑に影響し合うために、得られた計画の要素が現場の知識や直感と矛盾し、意志決定者が計画を信頼できない場合がある。そこで、直感に反する計画の要素成立への影響度を、シャープレイ値として制約や変数へ分解する説明手法がある。しかし、候補となる各要因が存在する場合としない場合の全ての組み合わせに対して最適化問題を解き直すため、膨大な計算時間が課題となっていた。そこで、シャープレイ値算出のための繰り返し計算を高速化する分枝限定法を提案する。具体的に、計算対象である要因候補の組み合わせよりも厳しい制約条件のもとで既に得られた最適解を再利用する。さらに、最適解自体を探索するのではなく、直感に反する条件内に最適解が存在するかどうかを探索する問題へと条件を緩和することで、計算の収束を早める。様々なパラメータ設定における人員配置問題の数値実験を通じて、提案手法により平均79.7%の計算時間が削減できることを確認した。