TY - GEN

T1 - Randomized Greedy Strategy with Corner Filling for the Irregular 2D Bin Packing Problem

AU - Shperling, Sofia

AU - Kochetov, Yury

N1 - Conference code: 23

PY - 2024/12/20

Y1 - 2024/12/20

N2 - We are given a finite set of irregular items and an unlimited number of identical rectangular bins. Items presented as two-dimensional, possibly non-convex polygons. The length and width of bins are given. We need to pack all items without overlapping and minimize the number of used bins. The rotations of items by 90, 180, and 270 angles are allowed. In the packing algorithm, we apply a fitness function based on the gravity center of the packing area and idea of the well-known sky-line approach for regular packing problem. To improve the result, we apply a special rule to fill the corners of bins. This rule is based on a function to evaluate how good a corner of each item fits in the corner of the bin. We select a subset of items with the best values of this function and randomly choose one of them to pack in the corner. We present computational results with filling of one, two, three, and four corners of some bins before packing. The comparison with well-known algorithms is presented on the real test instances from Novosibirsk car mats manufacturer company with up to 50 items.

AB - We are given a finite set of irregular items and an unlimited number of identical rectangular bins. Items presented as two-dimensional, possibly non-convex polygons. The length and width of bins are given. We need to pack all items without overlapping and minimize the number of used bins. The rotations of items by 90, 180, and 270 angles are allowed. In the packing algorithm, we apply a fitness function based on the gravity center of the packing area and idea of the well-known sky-line approach for regular packing problem. To improve the result, we apply a special rule to fill the corners of bins. This rule is based on a function to evaluate how good a corner of each item fits in the corner of the bin. We select a subset of items with the best values of this function and randomly choose one of them to pack in the corner. We present computational results with filling of one, two, three, and four corners of some bins before packing. The comparison with well-known algorithms is presented on the real test instances from Novosibirsk car mats manufacturer company with up to 50 items.

KW - 2D bin packing problem

KW - Fitness function based algorithm

KW - Irregular item

KW - Local search

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85214255308&origin=inward&txGid=84d9c8b87856d28602cd36c9aa6a30fb

UR - https://www.mendeley.com/catalogue/55e5bd9b-51ba-3b40-a0a4-d24480174fa3/

U2 - 10.1007/978-3-031-73365-9_17

DO - 10.1007/978-3-031-73365-9_17

M3 - Conference contribution

SN - 978-303173364-2

T3 - Communications in Computer and Information Science

SP - 250

EP - 263

BT - Communications in Computer and Information Science

PB - Springer Science and Business Media Deutschland GmbH

T2 - 23rd International Conference on Mathematical Optimization Theory and Operations Research

Y2 - 30 June 2024 through 6 July 2024

ER -