Ctrl+K

積み付けアルゴリズム

積み付けアルゴリズム#

  • 読み: つみつけあるごりずむ

  • 英名:

コンテナローディング問題（Container Loading Problem. 以下，CLP）または 3 次元ビンパッキング問題を解くためのアルゴリズム． これらの問題ではアイテム（製品，品物等）をビン（コンテナ，ボックス等）に入れることを考える．

以下 CLP の文脈のなかで話を進める．CLP の基本形は以下の通りである．

  • ビンのサイズ \((L,W,H)\)

  • アイテム集合 \(I\)

  • 各アイテム \(i \in I\) のサイズ \((l_i,w_i,h_i)\)

これらからなる入力データに対して，充填率を最大とする積載方法を求める． なお，ビンの種類が複数の問題を考えることも可能だが，問題のタイプが異なる [1] ため，以下では扱わないものとする．

CLP はパッキング問題の一種と捉えられ， 分枝限定法を用いた厳密解法を Martello らは [2] で紹介しているが， 実際には大別して以下の 3 つを用いた近似解法が専ら研究されている．

  1. 貪欲法や局所探索法などのヒューリスティクス

  2. GA, 焼きなまし法，タブーサーチなどのメタヒューリスティクス

  3. グラフサーチ法 [3] や不完全分枝限定法などの樹探索法 [4, 5]

近似解法における探索の基礎となる詰め方の構成には Bottom-Left 法，壁作り法，ブロック生成法，柱生成法，部分空間生成法，層生成法などの方法がよく知られている．

積み付けアルゴリズムで扱われる問題は空間に対するインスタンスの割り当てだが，一方で時間に対する割り当てと解釈した問題はスケジューリング問題となる．

関連

参考文献

[1]

Gerhard Wäscher, Heike Haußner, and Holger Schumann. An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3):1109–1130, dec 2007. URL: https://linkinghub.elsevier.com/retrieve/pii/S037722170600292X, doi:10.1016/j.ejor.2005.12.047.

[2]

Silvano Martello, David Pisinger, and Daniele Vigo. The Three-Dimensional Bin Packing Problem. Operations Research, 48(2):256–267, mar 2000. URL: http://www.jstor.org/stable/223143.

[3]

Reinaldo N. Morabito and Marcos Arenales. An AND/OR-graph approach to the container loading problem. International Transactions in Operational Research, 1(1):59–73, jan 1994. URL: http://doi.wiley.com/10.1016/0969-6016(94)90046-9, doi:10.1016/0969-6016(94)90046-9.

[4]

Michael Eley. Solving container loading problems by block arrangement. European Journal of Operational Research, 141(2):393–409, sep 2002. URL: https://linkinghub.elsevier.com/retrieve/pii/S0377221702001339, doi:10.1016/S0377-2217(02)00133-9.

[5]

M. Hifi. Approximate algorithms for the container loading problem. International Transactions in Operational Research, 9(6):747–774, nov 2002. URL: https://onlinelibrary.wiley.com/doi/10.1111/1475-3995.00386, doi:10.1111/1475-3995.00386.