トップ > 数理計画用語集 > 積み付けアルゴリズム

数理計画用語集

積み付けアルゴリズム

読み:つみつけあるごりずむ
関連ビンパッキング問題Bottom-Left 法スケジューリング

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

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

ビンのサイズequation

アイテム集合 equation

各アイテムequation のサイズequation

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

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

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

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

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

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

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

[参考]
[1] G. Washer, H. Haussner, H. Schumann, An Improved Typology of Cutting and Packing Problems,Eur. J. of Oper. Res. 183, 2007, pp.1109-1130
[2] S. Martello, D. Pisinger, D. Vigo,The three-dimensional bin packing problem, Operations Research. 48, 2000, pp.256-267
[3] R. Morabito, M. Arenalis,An AND/OR-graph Approach to the Container Loading Problem, Internat. Trans. in Oper. Res. 1, 1994, pp.59-73
[4] M. Eley, Solving Container Loading Problem by Block Arrangement, Eur. J. of Oper. Res. 141, 2002, pp.393-409
[5] M. Hifi, Approximate Algorithm for the Container Loading Problem, Internat. Trans. in Oper. Res. 9, 2002, pp.747-774