Heuristic approaches for the two- and three-dimensional knapsack packing problem
Heuristic approaches for the two- and three-dimensional knapsack packing problem
复制标题
DOI：
10.1016/j.cor.2007.12.004
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
J. Egeblad;David Pisinger
中科院分区：
文献类型：
--
作者：
J. Egeblad;David Pisinger
最大利润二维或三维背包装箱问题是将给定矩形或盒子的最大利润子集打包成一个更大的固定尺寸的矩形或盒子。项目必须正交包装，但没有其他限制强加给这个问题。基于Murata等人提出的序列对表示，我们提出了一种新的求解二维背包问题的迭代启发式算法。IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems 1996;15：1518-24]使用Pisinger的半正规化包装算法[在O（nloglogn）时间内获得的Denser包装。INFORMS Journal on Computing 2007;19：395-405]。解表示为一对序列。在每一次迭代中，序列对被修改并转换为一个包装，以评估目标值。采用模拟退火算法对启发式算法进行控制。一种新的抽象表示框的位置，称为序列三元组，使用类似的技术的三维背包问题。启发式算法能够处理允许旋转的问题实例。全面的计算实验，比较发达的ecologistics与以前的方法表明非常有前途的结果为二维和三维的问题。
The maximum profit two- or three-dimensional knapsack packing problem packs a maximum profit subset of some given rectangles or boxes into a larger rectangle or box of fixed dimensions. Items must be orthogonally packed, but no other restriction is imposed to the problem. We present a new iterative heuristic for the two-dimensional knapsack problem based on the sequence pair representation proposed by Murata et al. [VLSI module packing based on rectangle-packing by the sequence pair. IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems 1996;15:1518–24] using a semi-normalized packing algorithm by Pisinger [Denser packings obtained in O(nloglogn) time. INFORMS Journal on Computing 2007;19:395–405]. Solutions are represented as a pair of sequences. In each iteration, the sequence pair is modified and transformed to a packing in order to evaluate the objective value. Simulated annealing is used to control the heuristic. A novel abstract representation of box placements, called sequence triple, is used with a similar technique for the three-dimensional knapsack problem. The heuristic is able to handle problem instances where rotation is allowed. Comprehensive computational experiments which compare the developed heuristics with previous approaches indicate very promising results for both two- and three-dimensional problems.