Abstract: 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 f itness 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.

Cite: Shperling S. , Kochetov Y.
A Fitness Functions Based Algorithm for the Two-Dimensional Irregular Strip Packing Problem
In compilation 2023 19th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS). – IEEE., 2023. – C.104-109. – ISBN 9798350331134. DOI: 10.1109/opcs59592.2023.10275760 Scopus OpenAlex

Dates:

Published print:	Oct 13, 2023
Published online:	Oct 13, 2023

Identifiers:

Scopus:	2-s2.0-85175480764
OpenAlex:	W4387620824

Citing:

DB	Citing
OpenAlex	1
Scopus	1

Altmetrics: