氏名 : 岩澤 宏紀 (281367078)
所属 : 張研
題目 : 長方形配置問題に対する配置改善の高速化
概要 :
本発表では，長方形配置問題に対する配置改善の高速アルゴリズムについて述べる．
・対象とする問題
長方形配置問題とは，様々な大きさの長方形を二次元平面上に重ならないように配置
する問題である．この問題は長方形を荷物や部品，タスクに見立てることで，荷物の
詰め込み，工業製品の部品配置，スケジューリングなど，日常の様々な場面に応用を
持ち，実用上重要な問題である．
・研究背景
本研究の難しさは，配置方法が無数に存在し，最適な配置の決定が現実的な時間では
不可能な点である．そこで実用上はコンピュータを用いて，限られた時間で出来るだ
け効率の良い配置を求める手法が用いられている．既存解法の一つに長方形名を並べ
た二つの順列により配置を表現し，順列を操作することで配置を改善していく手法が
ある．この手法は実現可能なあらゆる配置を表現できるが，計算時間の面で改善すべ
き点がある．配置の計算方法や改善方法に関しては様々な効率的手法が提案されてお
り，実用上十分精度の高い手法として認知されてきた．
・提案法
本研究では，順列を用いて改善する手法に対して短時間でより高精度な解を得ること
を目標とし，新たに二つ長方形の位置を交換して得られる配置を高速に計算する手法
を二つ提案する．交換操作の前後で配置が似た構造を持っていることに着目し，予め
似た構造の情報を計算しておき，それを用いて高速な計算を可能とする．数値実験の
結果，交換して得られる配置を高速に計算できたことで，従来と同じ時間でより高精
度な解が得られたことを確認した．
目次に戻る