講演情報
[2J5-OS-36a-05]ASPに基づく適応型優先度付き巨大近傍探索の実装とナーススケジューリング問題への適用
〇宮下 眞樹1、杉森 唯瑠未1、鍋島 英知2、宋 剛秀1、番原 睦則1 (1. 名古屋大学、2. 山梨大学)
キーワード：
組合せ最適化問題、ナーススケジューリング、解集合プログラミング
本発表では，解集合プログラミング（Answer Set Programming; ASP）を用いた適応型優先度付き巨大近傍探索（Adaptive Large Neighborhood Prioritized Search; ALNPS）の実装について述べる．
ALNPS は，組合せ最適化問題に対して，初期解から開始し，現在解に対して破壊と再構築を繰り返すことによって，より良い解を見つけるメタヒューリスティクスである．従来の適応型巨大近傍探索（ALNS）との大きな違いは，再構築に優先度付き系統的探索を用いることにより破壊されなかった部分の可変性を許す点，得られた解の最適性を保証できる点，破壊演算子の振る舞いを自律的に制御できる点があげられる．
山梨大学医学部附属病院のナーススケジューリング問題を用いて性能評価を行った結果，提案ソルバーは，高速 ASP ソルバー clingo および ALNS の実装である ALASPO と比較して，実データに基づく人工インスタンス（全50問）すべてに対してより良い解を生成することに成功し，ALNPS の有効性を確認することができた．
ALNPS は，組合せ最適化問題に対して，初期解から開始し，現在解に対して破壊と再構築を繰り返すことによって，より良い解を見つけるメタヒューリスティクスである．従来の適応型巨大近傍探索（ALNS）との大きな違いは，再構築に優先度付き系統的探索を用いることにより破壊されなかった部分の可変性を許す点，得られた解の最適性を保証できる点，破壊演算子の振る舞いを自律的に制御できる点があげられる．
山梨大学医学部附属病院のナーススケジューリング問題を用いて性能評価を行った結果，提案ソルバーは，高速 ASP ソルバー clingo および ALNS の実装である ALASPO と比較して，実データに基づく人工インスタンス（全50問）すべてに対してより良い解を生成することに成功し，ALNPS の有効性を確認することができた．