大会名称
2010年 情報科学技術フォーラム(FIT)
大会コ-ド
F
開催年
2010
発行日
2010/8/20
セッション番号
7A
セッション名
アルゴリズム・コンピュテーション(3)
講演日
2010/09/09
講演場所(会議室等)
A会場(総合学習プラザ1F 第5講義室)
講演番号
RA-006
タイトル
3次元箱詰め問題に対する構築型解法の効率的実現法
著者名
川島 大貴田中 勇真今堀 慎治柳浦 睦憲
キーワード
切り出し・詰め込み問題, 3次元箱詰問題, 3次元ストリップパッキング問題, bottom-left法, no-fit polygon
抄録
3次元箱詰め問題は, 複数の直方体を容器に詰め込む問題の総称であり, 様々な種類の問題を含んでいる. 3次元箱詰め問題の応用として, コンテナへの荷物の積み付け等がある. 本研究では3次元箱詰め問題に対して, 2次元箱詰め問題の解法に用いられるbottom-left (BL)法を3次元に拡張した解法の効率的実現法を提案する. なお, 本研究で提案する手法は, 他の3次元箱詰め問題にも容易に適用できるが, 本研究では回転を許さない3次元ストリップパッキング問題を対象とする.
ランダムに生成した直方体数最大10000の問題例に対して計算実験を行った.その結果, 大規模な問題例に対しても数百秒程度と実用的な時間で解を構築できることが確認できた.
本文pdf
PDF download (230.9KB)