文献

J-GLOBAL ID：201802283243311828   整理番号：18A0184626

ビットマップ形状パッキング問題における効率的オーバーラップ検出と構成アルゴリズム

EFFICIENT OVERLAP DETECTION AND CONSTRUCTION ALGORITHMS FOR THE BITMAP SHAPE PACKING PROBLEM

著者 (5件)： Hu Yannan (Nagoya University) ,  Fukatsu Sho (Nagoya University) ,  Hashimoto Hideki (Tokyo University of Marine Science and Technology) ,  Imahori Shinji (Chuo University) ,  Yagiura Mutsunori (Nagoya University)
資料名： Journal of the Operations Research Society of Japan  (Journal of the Operations Research Society of Japan)
巻： 61  号： 1  ページ： 132-150(J-STAGE)  発行年： 2018年 
JST資料番号： G0402A  ISSN： 0453-4514  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 二次元ストリップ包装問題は多種多様の産業アプリケーションに生起する。本論文では,ビットマップ形式で表現される一連の任意形状オブジェクトがオーバーラップ無くより大きな長方形コンテナにパッキングされる,ビットマップ形状パッキング問題に焦点を当てた。ビットマップ形状の複雑な幾何形状と処理されるべき大量データはオーバーラップ検査を困難にする。本論文では,オーバーラップ検査の効率的方式を提案し,ボトムレフト戦略に基づく,2構成アルゴリズムの効率的実装を設計した。この戦略では,空レイアウトから始めて,商品を1つずつコンテナにパッキングする。各商品を現レイアウトに対してオーバーラップの無い最低位置に配置する。この戦略を採用する2つのアルゴリズム,ボトムレフト及び最善適合アルゴリズムについて考察した。周知ベンチマークインスタンスから生成される一連のインスタンスに関して,計算結果は,提案アルゴリズムが顕しく短時間で良好な解を得,大規模インスタンスに特に有効であることを示した。(翻訳著者抄録)

シソーラス用語： *組合せ最適化問題 ,  *発見的方法 ,  *パッキング問題 ,  行動 ,  効率 ,  画像 ,  形式 ,  包装 ,  形態 ,  多角形 ,  位置 ,  アルゴリズム ,  長方形 ,  *計算量 ,  多重化 ,  コンテナ ,  ベンチマーク ,  ストリップ包装 ,  効率的実用化
準シソーラス用語： 効率的実行 ,  ビットマップ形状 ,  ボトムレフト位置 ,  オーバラップ

著者キーワード (5件)： Combinatorial optimization ,  construction heuristics ,  strip packing ,  bitmap shapes ,  efficient implementation

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  計算理論  (JB02000A)

引用文献 (27件)：

• [1] R.C. Art: An approach to the two dimensional irregular cutting stock problem. PhD thesis, Massachusetts Institute of Technology, IBM Cambridge Science Center, 1966.
• [2] B.S. Baker, E.G. Coffman Jr., and R.L. Rivest: Orthogonal packings in two dimensions. SIAM Journal on Computing, 9 (1980), 846-855.
• [3] J.A. Bennell and J.F. Oliveira: A tutorial in irregular shape packing problems. Journal of the Operational Research Society, 60(S1) (2009), S93-S105.
• [4] E.K. Burke, G. Kendall, and G. Whitwell: A new placement heuristic for the orthogonal stock-cutting problem. Operations Research, 52 (2004), 655-671.
• [5] L.H. Cherri, L.R. Mundim, M. Andretta, F.M.B. Toledo, J.F. Oliveira, and M.A. Carravilla: Robust mixed-integer linear programming models for the irregular strip packing problem. European Journal of Operational Research, 253 (2016), 570-583.

タイトルに関連する用語 (4件)： ビットマップ ,  パッキング問題 ,  オーバーラップ ,  アルゴリズム