Problem Formulation

Two-dimensional irregular bin packing problem. We are given a finite set of N items P = {P₁ , P₂ , . . . , P_N } and an infinite set of bins B = {B₁, B₂ , . . . }. Items presented as a two-dimensional, possibly non-convex polygons. Each polygon is presented as a set of vertices p ∈ P_i with coordinates (x^p , y^p). The length and width of bins are given and equal to L and W, respectively. We need to pack all items without overlapping while minimizing the number of used bins. The rotations of items by 0^◦ , 90^◦ , 180^◦ and 270^◦ angles are allowed. To distinguish solutions with the same number of bins, but with the different percent of the residuals at the last bin, we apply the following objective function.

where U_i  is the utilisation ratio of bin i, N is a number of the used bins. The U_i is defined as

  ,

where  S_qr (P_i ) is the area of the item P_i if it is packed in the bin i, 0 otherwise. Irregular strip packing problem is in a group of problems which are called as nesting problems. They deal with a lot of applications in textile, sheet metal, leather, glass and other industries. In these cases, we want to cut all pieces and to spend less material.

Information about the data sets

Presented data sets consists of a polygons which are the templates for a car mates production. In this data sets the templates of car mates for trunks and for different parts of the cabin is presented. For example, data set car_mats_5 consist of the trunks mates only, car_mats_9 consist of templates of mats which is located in the middle of back row of the car. The source data is contained in text files car_mats1.txt – car_mats10.txt. Each file contains information about all the polygons of the data set one by one. For each polygon we have the following information. In the line after word PIECE indicates the id of the item. At the next line after word QUANTITY we point out the number of this polygons in data set. At the next line we record the NUMBER OF VERTICES of this polygon. This value will equal the number of lines with the coordinates. Next line VERTICES (X,Y) indicates that next lines will present the coordinates of each point by axis X and by axis Y. After the coordinates of the one item will be the same information about the next item.

Data set	Illustrations	Types of items	Best found values	Result illustrations
car_mats_1	car_mats_data_set_1	10 types × 5	0.421	result_set_1
car_mats_2	car_mats_data_set_2	10 types × 5	0.417	result_set_2
car_mats_3	car_mats_data_set_3	10 types × 5	0.414	result_set_3
car_mats_4	car_mats_data_set_4	10 types × 5	0.416	result_set_4
car_mats_5	car_mats_data_set_5	25 types × 2	0.419	result_set_5
car_mats_6	car_mats_data_set_6	25 types × 2	0.427	result_set_6
car_mats_7	car_mats_data_set_7	25 types × 2	0.412	result_set_7
car_mats_8	car_mats_data_set_8	25 types × 2	0.410	result_set_8
car_mats_9	car_mats_data_set_9	10 types × 5	0.415	result_set_9
car_mats_10	car_mats_data_set_10	50 types × 1	0.425	result_set_10

All  data sets and illustrations data sets car mats.zip

All result illustrations  result_illustrations.zip

References
S. Shperling and Yu. Kochetov. Randomized greedy strategy with corner filling for the irregular 2D bin packing problem // MOTOR 2024, Revised Selected Papers. Communications in Computer and Information Science. 2024 Vol. 2239 P. 243-256