多角形パッキング問題は，一定の大きさの生地から洋服の部品を切り取る問題や，長 方形の鋼板から船舶の部品を切り取る問題として，様々な分野で応用をもつ組合せ最 適化問題である．この問題は全ての多角形の配置に必要な母材の面積の最小化を目的 とし，応用面では母材の面積減少によるコストの低下が期待される．
この問題は，多項式時間で計算が不可能であると考えられるＮＰ困難な問題であると 知られているが，良い配置を見つけ出すための実用的なアルゴリズムとして反復局所 探索法やアニーリング法などを適用した方法が多数提案されて，成果を上げている．
本発表では，探索の効率化を目指し既存の方法とは異なるアプローチを用いた，多角 形パッキング問題における新手法の提案について述べる． この方法は，探索により得られた図形の配置と目的関数値を評価値行列に記憶させ， 次に行う図形の配置を評価値行列から算出して行うことにより，探索の過程の情報を それ以降の配置に影響させるという方法である． 数値実験では，今回提案した手法と反復局所探索法を用いてベンチマーク問題に対し て実験を行い，結果を比較し，提案した手法の有効性についての検証を行う．