期刊
COMPUTERS & OPERATIONS RESEARCH
卷 36, 期 4, 页码 1026-1049出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2007.12.004
关键词
Cutting and packing; Two-dimensional knapsack problems; Three-dimensional knapsack problem; Heuristics; Simulated annealing; Sequence pair; Sequence-tripple
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 anew 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(n log log n) 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. (C) 2007 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据