An adaptive selection approach for the 2D rectangle packing area minimization problem

Lijun Wei, Wenbin Zhu, Andrew Lim, Qiang Liu and Xin Chen

Omega, 2018, vol. 80, issue C, 22-30

Abstract: This paper investigates the 2D rectangle packing area minimization problem (RPAMP), in which the objective is to pack a set of rectangles into a container with variable sizes and minimize the area of the container. The RPAMP is transformed into a series of 2D strip packing problems (2DSPs). Instead of selecting the set of most promising widths initially, a novel adaptive selection approach is proposed to choose a candidate width at each iteration. An iterative doubling search strategy is introduced to avoid spending too much effort on the same width. A skyline based best-fit heuristic is adapted to solve the 2DSP. Compared to previous approaches, the proposed one is much simpler as it does not need any control parameter. Computational experiments on the benchmark test sets show that the proposed method outperforms all existing approaches and improves the best-known solutions for most of the instances (28 out of 39 instances). Especially for the well-studied instances Ami33 and Ami49, the approach finds better solutions.

Keywords: Packing; Area minimization; Strip packing; Heuristic (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048316310313
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:80:y:2018:i:c:p:22-30

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2017.09.002

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().