A strip packing solving method using an incremental move based on maximal holes

Bertrand Neveu, Gilles Trombettoni, IGNACIO DANIEL ARAYA ZAMORANO, Maria Cristina Riff

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

When handling 2D packing problems, numerous incomplete and complete algorithms maintain a so-called bottom-left (BL) property: no rectangle placed in a container can be moved more left or bottom. While it is easy to make a rectangle BL when it is added in a container, it is more expensive to maintain all the placed pieces BL when a rectangle is removed. This prevents researchers from designing incremental moves for metaheuristics or efficient complete optimization algorithms. This paper investigates the possibility of violating the BL property. Instead, we propose to maintain the set of maximal holes, which allows incremental additions and removals of rectangles. To validate our alternative approach, we have designed an incremental move, maintaining maximal holes, for the strip packing problem, a variant of the famous 2D bin-packing. We have also implemented a metaheuristic, with no user-defined parameter, using this move and standard greedy heuristics. We have finally designed two variants of this incomplete method. In the first variant, a better first layout is provided by a hyperheuristic proposed by some of the authors. In the second variant, a fast repacking procedure recovering the BL property is occasionally called during the local search. Experimental results show that the approach is competitive with the best known incomplete algorithms.

Original languageEnglish
Pages (from-to)881-901
Number of pages21
JournalInternational Journal on Artificial Intelligence Tools
Volume17
Issue number5
DOIs
StatePublished - 1 Oct 2008

Keywords

  • 2D packing
  • Bin packing
  • Local search
  • Strip packing

Fingerprint Dive into the research topics of 'A strip packing solving method using an incremental move based on maximal holes'. Together they form a unique fingerprint.

Cite this