TY - GEN

T1 - A Fitness Functions Based Algorithm for the Two-Dimensional Irregular Strip Packing Problem

AU - Shperling, Sofia

AU - Kochetov, Yury

N1 - Публикация для корректировки.

PY - 2023

Y1 - 2023

N2 - We are given a finite set of items (irregular polygons) and a strip with known width and infinite length. The goal is to pack all items without overlapping so to minimize the used length of the strip. Rotation of items by discrete set of angles are allowed. We apply the well-known semi-discrete representation of the items in the strip. Each item and a strip are represents as a series of equidistant horizontal line segments. To receive the strip packing we apply the following iterative procedure. The number of iterations is equals to the number of items. The algorithm try to pack every unpacked item on every available place on the strip. For every item and for every place we calculate the fitness function. Our fitness function evaluate both the polygon to be packed and its packing place. At every iteration of the algorithm we evaluate unpacked polygons and a places to pack using the fitness functions. After that we construct the set of the combinations of the items and places with the biggest value of the fitness function. We randomly select one of this combinations to pack. This procedure is repeated while all objects is not packed. Because of the randomisation of this algorithm we need to repeat this algorithm for a several times to find a better result. Computational results for available test instances are discussed.

AB - We are given a finite set of items (irregular polygons) and a strip with known width and infinite length. The goal is to pack all items without overlapping so to minimize the used length of the strip. Rotation of items by discrete set of angles are allowed. We apply the well-known semi-discrete representation of the items in the strip. Each item and a strip are represents as a series of equidistant horizontal line segments. To receive the strip packing we apply the following iterative procedure. The number of iterations is equals to the number of items. The algorithm try to pack every unpacked item on every available place on the strip. For every item and for every place we calculate the fitness function. Our fitness function evaluate both the polygon to be packed and its packing place. At every iteration of the algorithm we evaluate unpacked polygons and a places to pack using the fitness functions. After that we construct the set of the combinations of the items and places with the biggest value of the fitness function. We randomly select one of this combinations to pack. This procedure is repeated while all objects is not packed. Because of the randomisation of this algorithm we need to repeat this algorithm for a several times to find a better result. Computational results for available test instances are discussed.

KW - fitness function

KW - local search

KW - nesting problem

KW - semi-discrete representation

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85175480764&origin=inward&txGid=214ea85138aa9096feade5587266d142

UR - https://www.mendeley.com/catalogue/418bc60f-adc0-3b8b-9b9f-cd159c1d75e8/

U2 - 10.1109/OPCS59592.2023.10275760

DO - 10.1109/OPCS59592.2023.10275760

M3 - Conference contribution

SN - 9798350331134

T3 - Proceedings - 2023 19th International Asian School-Seminar on Optimization Problems of Complex Systems, OPCS 2023

SP - 104

EP - 109

BT - Proceedings - 2023 19th International Asian School-Seminar on Optimization Problems of Complex Systems, OPCS 2023

PB - Institute of Electrical and Electronics Engineers Inc.

ER -