An efficient constructive heuristic for the rectangular packing problem with rotations

Xusheng Zhao, Yunqing Rao, Peng Qi, Qianhang Lyu, Piaoruo Yang and Shoubo Yu

PLOS ONE, 2023, vol. 18, issue 12, 1-17

Abstract: The rectangular packing problem has been extensively studied over the years due to its wide application in industry. However, most of the research efforts are devoted to positioning techniques of the rectangles for various problem variants, the efficient implementation of the packing procedure is relatively less studied. In this paper, we propose an efficient constructive algorithm for the rectangular packing problem with rotations. We design a preprocess procedure with four data structures to store the information used for item selection. The gaps on the skyline are categorized into three types according to their associated edges for the placement procedure, during which the item is searched and packed in a descending order of the fitness value. The entire constructive phase takes a time complexity of O(nlogn). For the packing improvement phase, we optimize the packing through random perturbation on the sequence and orientation of the item. Three classes of stochastic problems are generated ranging from small-scale to extra-large-scale, the recorded running time confirms the efficiency of the proposed algorithm. We also test the proposed algorithm on the benchmark problem C21, N13, NT, Babu and CX, the computational results show that it delivers a good performance.

Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0295206 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 95206&type=printable (application/pdf)

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:plo:pone00:0295206

DOI: 10.1371/journal.pone.0295206

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().