２Ｄと３Ｄ配置問題に対する解法の研究とその応用

配置問題とは，配置すべきもの（製品と呼ぶ）の集合と配置される空間が与えられたとき，製品を空間内に，様々な制約の下で効率よく配置する問題である．計算の複雑度という観点から見ると，ほぼ全ての配置問題はNP困難に分類され，多項式時間で厳密な解を求める手法はおそらく存在しない．このような状況にあるため，性能の良い近似解法の開発が非常に重要であると考えられている．このような状況のもと、本年度は以下のテーマについて研究を進めた．(1)ギロチンカット制約および配置コストを考慮する長方形詰込み問題に対する近似解法を開発した．ギロチンカット制約とは，容器を端から端まで切り取る操作を繰り返すことで全ての長方形を切り出す制約で，生産工程における手順や機械の構造などにより現実の問題においてしばしば要求される．また，各長方形の配置に対して配置コストを導入した．具体的には，各長方形にx軸方向，y軸方向それぞれに関するコスト関数が与えられる時に，得られた配置における各長方形のコストのうち最も大きいコストを最大配置コストとし，その最小化を目的とする．この問題に対して効率的な反復局所探索法を提案した．(2)レクトリニア図形配置問題に対する局所探索法を開発した．先行研究で提案した高速なbottom-left法の配置順序に変化を加えることで局所探索を行い，初期解から解を改善する手法を提案した．さらに, 効率的な局所探索の方法について検証した．(3) レクトリニア図形配置問題に対する厳密解法を開発した．レクトリニア図形を幅１の長方形に分解し，分解されたそれらの長方形の相対的位置を緩和した配置問題を考え，整数計画問題として定式化した．この緩和問題を解くことで，元問題の下界を計算できる．さらに，緩和問題の解を利用し，元問題の上界を求める手法を提案した．そして，これらの手法を用いた厳密解法を提案した．

配置問題とは，配置すべきもの（製品と呼ぶ）の集合と配置される空間が与えられたとき，製品を空間内に，様々な制約の下で効率よく配置する問題である．計算の複雑度という観点から見ると，ほぼ全ての配置問題はNP困難に分類され，多項式時間で厳密な解を求める手法はおそらく存在しない．このような状況にあるため，性能の良い近似解法の開発が非常に重要であると考えられている．このような状況のもと、本年度は以下のテーマについて研究を進めた．(1)ギロチンカット制約および配置コストを考慮する長方形詰込み問題に対する近似解法を開発した．ギロチンカット制約とは，容器を端から端まで切り取る操作を繰り返すことで全ての長方形を切り出す制約で，生産工程における手順や機械の構造などにより現実の問題においてしばしば要求される．また，各長方形の配置に対して配置コストを導入した．具体的には，各長方形にx軸方向，y軸方向それぞれに関するコスト関数が与えられる時に，得られた配置における各長方形のコストのうち最も大きいコストを最大配置コストとし，その最小化を目的とする．この問題に対して効率的な反復局所探索法を提案した．(2)レクトリニア図形配置問題に対する局所探索法を開発した．先行研究で提案した高速なbottom-left法の配置順序に変化を加えることで局所探索を行い，初期解から解を改善する手法を提案した．さらに, 効率的な局所探索の方法について検証した．(3) レクトリニア図形配置問題に対する厳密解法を開発した．レクトリニア図形を幅１の長方形に分解し，分解されたそれらの長方形の相対的位置を緩和した配置問題を考え，整数計画問題として定式化した．この緩和問題を解くことで，元問題の下界を計算できる．さらに，緩和問題の解を利用し，元問題の上界を求める手法を提案した．そして，これらの手法を用いた厳密解法を提案した．