Details

Autor(en) / Beteiligte

• Zhao, Xusheng
• Rao, Yunqing
• Qi, Peng
• Lyu, Qianhang
• Yang, Piaoruo
• Yu, Shoubo
• Saikia, Lalit Chandra

Titel

An efficient constructive heuristic for the rectangular packing problem with rotations

Ist Teil von

• PloS one, 2023-12, Vol.18 (12), p.e0295206-e0295206

Ort / Verlag

United States: Public Library of Science

Erscheinungsjahr

2023

Quelle

Free E-Journal (出版社公開部分のみ）

Beschreibungen/Notizen

• 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.