メタ戦略に基づく3次元物体の最適配置を求めるフレームワークの構築

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

2次元と3次元の任意の形状の物体を容器の中に物体同士の重複がないように配置する問題に対する汎用的なフレームワークとして、Multi-sphere schemeを平成19年度に提案していた。Multi-sphere schemeは、与えられた図形をまず球の集合で近似した後に、球集合の配置を求めるものである。平成20年度の研究では、まずこのフレームワークの高速化に関する研究を行った。ボトルネックとなる部分は、球同士の衝突を判定する部分であった。これに対してスラブ分割や平面走査法を組合せたアルゴリズムを提案し、次元と球の半径比が定数となる条件の下で、理論的に最適な時間量と領域量を達成することを示した。そして計算実験を通じて実際にそのアルゴリズムがMulti-sphere schemeを高速化するのに有効であることを示しか。これによりMulti-sphere schemeがより大規模な問題に適用できるようなった点て意義がある。また、この高速化された手法を用いて、平成19年度で行っていたラベル配置問題への応用について詳細な計算実験を行い、200程度ラベルのある問題に対して数秒で解くことができることを示した。また関連問題の研究として、長方形を幅固定の容器に配置する際に、必要となる高さを最小化するというストリップパッキング問題の厳密解法の研究も行った。新しい下界値を考案するとともに、実行可能解の標準型を定めて標準型を満たす解のみを探索するような分枝規則と限定規則を構築した。これにより探索木のサイズを効果的に縮小することに成功した。