Presentation Information
[2J5-OS-36a-05]ASP-based Implementation of Adaptive Large Neighborhood Prioritized Search and its Application to the Nurse Scheduling Problem
〇Maki Miyashita1, Irumi Sugimori1, Hidetomo Nabeshima2, Takehide Soh1, Mutsunori Banbara1 (1. Nagoya University, 2. University of Yamanashi)
Keywords:
Combinatorial Optimization Problem,Nurse Scheduling,Answer Set Programming
本発表では，解集合プログラミング（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 の有効性を確認することができた．