Heuristic approaches for the two- and three-dimensional knapsack packing problem

Publication: Research - peer-reviewJournal article – Annual report year: 2009

Without internal affiliation

  • Author: Egeblad, Jens

    University of Copenhagen

  • Author: Pisinger, David

    University of Copenhagen

View graph of relations

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.
Original languageEnglish
JournalComputers & Operations Research
Issue number4
Pages (from-to)1026-1049
StatePublished - 2009
Externally publishedYes
CitationsWeb of Science® Times Cited: 47
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 4399321