研究内容 / Research

これまで組合せ最適化問題に対して実用的な近似解法の開発を目指して研究を行ってきました.組合せ最適化問題は,問題の解が定義される空間や制約などが離散的である問題で,社会で現れる様々な問題は組合せ最適化問題として表現できます.しかし,それらは多くの場合,
NP困難な問題で,現実的な計算時間で最適解を得ることは非常に困難です.その一方で,現実の問題では厳密な最適解が必要とされることはまれで,適度な精度の近似解を現実的な計算時間で求める解法で十分に実用的であると考えられています.このような状況では,効率よく近似最適解を求める解法が有用となります. 
  
私がこれまでに主な研究テーマとして行った研究は,2次元と3次元の配置問題に対する近似解法の研究です.
配置問題:
 配置問題とは,配置すべきもの(製品と呼ぶ)の集合と配置される空間が与えられたとき,製品を空間内に,様々な制約の下で効率よく配置する問題です.この問題は,古典的な組合せ最適化問題の1つです.
 2次元配置問題について,私の研究では一般の図形配置問題の中でも特に大規模な問題に焦点を絞り,性能の高い近似解法の構築を目的としました.一般の図形配置問題では,図形の配置に対して重なりがあるか否かを判定する際,計算コストの高い計算幾何的な処理が必要となり,さらに,それに起因する数値誤差が問題となります.本研究では一般の図形をビットマップ形式で表現された図形で近似したビットマップ図形配置問題を考えます(右図参照).ビットマップ図形は垂直もしくは水平線分で描かれるレクトリニア図形として捉えることができ,図形の重なりを容易に判定することができます.さらに,レクトリニア図形は長方形と似た構造を持っており,長方形配置問題に対する知見・成果を利用して,高速・高性能なアルゴリズムを設計できます.    
構築型解法とは空の状態からひとつずつ多角形を配置しに行きます.以下の配置の例はレクトリニア多角形を長方形の領域に詰め込む問題に対して,三つの構築型解法により得られたものです.  
レクトリニア図形の数:204, 充填率は:79.51%, 90.59%,92.45%です.