3次元配置問題に対する近似解法の研究とその応用

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

3次元(3D)物体配置問題は，直方体の容器に3D物体を詰め込む問題である．既存研究では直方体の配置問題に対して様々な方法が提案されているが，一般的な3D物体の配置問題に対する研究は，申請者の知る限りこれまで行われていない．一般的な3D物体の配置問題は，医療機器，ロボット，人工衛星などの設計において限られたスペースにより多くの機能を搭載するために必要となる製品をより小さく作る技術をはじめ，工学的な応用が非常に多い．本研究は，2D図形と直方体配置問題で得られた知見を利用して，2次元(2D)図形配置問題の解法を3次元物体配置問題に拡張することを検討し，3D物体配置問題に対する高速・高性能な解法を開発することを目的とした.曲線を含む図形垂直もしくは水平線分で描かれるレクトリニア図形として捉えることができ，図形の重なりを容易に判定することができる．これまでの研究では一般の2D図形をレクトリニア図形に近似し，レクトリニア図形配置問題に対して性能の高い構築型解法の開発した．今年度は，2D図形配置問題に対する解法を3D物体配置問題へ拡張した．次元が高くなることで問題の難しさが急激に増すため，既存研究の長方形配置問題に対する解法の3D直方体配置問題への拡張を検討しており，その中で現在の配置に対して新しく直方体を配置できる場所の探索が現在の配置のある断面に対する2D図形の配置可能性と等価な問題となる．この研究を応用して，レクトリニア図形配置問題に対して提案した解法を3Dレクトリニア多面体に拡張した．そして，一般の3D物体を3Dレクトリニア多面体に近似して解く方法を設計した．