Study on efficient algorithms for the dynamic block relocation problem

点击翻译按钮获取中文摘要

本研究は，ブロック積み替え問題に対する結果を，並列スタック積み込み問題，動的ブロック積み替え問題と段階的に拡張することで，動的ブロック積み替え問題に対する効率的な厳密解法を構成することを目的とする．２０２２年度の主成果は以下の２点である．（１）並列スタック積み替え問題の計算複雑さに関する結果．他のアイテムの取り出しをブロックしているアイテム（ブロッキングアイテム）の総数を最小化する並列スタック積み替え問題は，NP困難な組合せ最適化問題であることが知られている．しかし，スタックの容量制約がない問題の計算複雑さはこれまで知られていなかった．そこで本研究では，この問題が多項式時間で求解可能であることを，順序グラフの最大独立分割問題との等価性を示すことにより証明した．（２）動的ブロック積み替え問題に対する厳密解法に関する結果．ブロックの到着時刻から実際の積み込み時刻までの遅れ時間，および出発時刻から実際の取り出し時刻までの遅れ時間を考え，これら遅れ時間の重み和を最小化する動的ブロック積み替え問題を対象とした．また，本問題において，次に取り出すブロックの上に積まれたブロックのみ積み替え可能な制限問題と，積み替えに制限を設けない無制限問題の２通りの問題設定を考えた．そして，これらに対して分枝限定法に基づく基本的な厳密解法を構成した．そして数値実験によりその有効性を検討した．（１）の成果については２０２２年に国内学会で発表を行った．また，（２）の成果については，２０２３年に国内学会で発表予定である．