Keywords

1 Introduction

The problem of packing small objects inside one or more large objects appears in many real-world applications. In the logistics area, for example, we have pallets and boxes to be loaded into containers, trucks, trains, ships, or airplanes. This problem is computationally hard in many of its variants and so mathematical programming models and heuristics have been proposed in the literature. It is important to mention that, from a theoretical point of view, it is equivalent to cutting problems, which in turn requires the cutting of large objects to produce small ones. In the textile and metal-mechanic industry, for example, fabric rolls and metal plates are cut to produce pieces of products. For an overview of packing and cutting problems, we refer to the book in [20].

In this paper, we are interested in problems where small objects can have irregular shapes. We look for the packing (cutting) of all small objects (hereafter called items) in a single large object (hereafter called a strip). This problem is known as the two-dimensional irregular strip packing problem [18]. As the strip is assumed to have a fixed width, the objective is to minimize its opened length by obtaining a feasible packing. Concerning irregularly shaped items, the guarantee of a feasible packing can be obtained with geometric tools, such as the raster method, the phi-functions, the direct trigonometry, and the no-fit polygons. For these tools, we refer to the tutorial in [3]. We use the no-fit raster, a combination of the raster method and the no-fit polygons [23].

In the literature on the two-dimensional irregular strip packing problem, we may find different contributions, from simple mathematical programming models to sophisticated heuristics. As this problem is NP-hard, most of the contributions are related to heuristics. In [1], sequences of items are packed with the bottom-left rule. In this rule, an item is translated to the bottom and then to the left in the strip. This rule is also used in [15], where a genetic algorithm generates the sequence of items; in [10], where a 2-exchange heuristic generates the sequence of items; in [11], where simulated annealing is used for generating the sequence of items; in [17], where a biased random key genetic algorithm generates the sequence of items.

Other contributions are related to a constraint programming model in [4], the integration of the cuckoo search with a guided local search in [7], and a tailored branch-and-cut algorithm, where a variable neighborhood search heuristic generates feasible solutions, in [22]. Integer linear programming models are proposed in  [5, 8, 16, 19, 23]. The model in [19] uses clique constraints to detect infeasible packings. They improved most of the previous solutions presented in the literature.

We propose a Variable Neighborhood Search (VNS) for the two-dimensional irregular strip packing problem. The VNS’s neighborhood structures are based on swap and insertion movements. The shaking phase consists of a single structure based on swap movements, while the local search consists of the variable neighborhood descent (VND). The VNS generates the sequence of items, while a function is used to transform the given sequence into a feasible packing. For that, items are positioned in the strip by combining the bottom-left and top-left placement rules. Results obtained with the VNS are compared with those in [19, 22], with better solutions for 27.27% of the instances and equal solutions for 63.63% of the instances.

The remainder of this paper is organized as follows. In Sect. 2, we define the problem and the geometric tools used to guarantee feasible packings. In Sect. 3, we present the variable neighborhood search and how a sequence of items is transformed into a problem solution. In Sect. 4, we perform computational experiments on literature instances and compare the performance of the VNS with the literature. In Sect. 5, we give some conclusions and directions for future works.

2 Problem Definition

This paper is about the Two-Dimensional Irregular Strip Packing Problem (2ISP). We assume the strip is rectangular, while items are defined as (irregular) polygons without holes. Each item j has a set of vertices \(V_j\), an area \(a_j\), and a reference vertex \(p_j\). We assume an item is positioned in the strip by its reference vertex, which in turn is defined as the vertex with the lowest y-coordinate and, in the case of ties, with the lowest x-coordinate. A solution is built on the Cartesian plane. The strip’s lower-left coordinates are at (0, 0) and its top-right coordinates are at \((\infty , W)\). We associate the opened length (\(\infty \)) to the x-axis and the width W to the y-axis. The problem’s objective is to minimize the opened length while packing all items in the strip.

We assume the strip is discrete and then defined by a grid of points [2]. The reference vertex of items is positioned on points of this grid. A feasible solution (packing) is obtained when all items are packed inside the strip (i.e., there is no part/area of any item extrapolating the strip’s dimensions) and items do not overlap each other (i.e., there is no intersection between any two items when positioned on the grid). To guarantee these two conditions to obtain a feasible solution, we calculate the inner-fit raster of each item with the strip and the no-fit raster between any two items. Figure 1 shows an example of irregularly shaped items, a rectangular strip, and the no-fit raster between two items.

Fig. 1.
figure 1

Illustrative example for the 2ISP.

Full size image

The inner-fit and no-fit rasters are calculated in a pre-processing step [23]. For the inner-fit raster, each item j is positioned by its reference vertex at the lowest-left position on the grid, touching the strip’s borders where possible but not extrapolating the strip’s dimensions. Then, this item is translated around the strip always touching the strip’s borders. The inner-fit polygon that is generated is next discretized according to the strip’s grid. Positions having value “1” mean that such an item cannot be positioned there since it does not respect the strip’s dimensions. For the no-fit raster, we consider each pair of items i and j. Item i is fixed on the plane, while j is positioned in such a way that it touches i. Then, item j is translated (by its reference vertex) around and touching i. The no-fit polygon that is generated is next discretized according to the strip’s grid. Positions having value “1” mean that item j cannot be positioned there since such items will overlap each other.

3 Proposed Heuristic

We develop a VNS heuristic to the 2ISP. This heuristic has been applied to solve many continuous and discrete optimization problems, obtaining very competitive results compared to other literature methods [6, 13]. Differently from other literature contributions that applied VNSs to irregular cutting problems, we consider the shaking phase defined on only one neighborhood structure, while the local search phase is composed of three neighborhood structures. The idea is to prioritize the local search phase to obtain high-quality solutions. As this phase could require a large computational time, the VNS has the advantage of carrying the optimization over a single solution and thus helping on reducing the computational effort. Algorithm 1 presents the proposed VNS.

In Algorithm 1, we code the solution x as a vector of integers. This is commonly adopted in the literature on irregular cutting problems [21, 22]. Each integer represents the index of an item in the input instance. This means that x contains the sequence in which items are packed in the strip’s grid. In the shaking phase, we consider that only the neighborhood structure \(N_1\) is applied, where positions i and j are randomly chosen. On the other hand, the local-search phase considers three neighborhood structures, which are \(N_1\), \(N_2\), and \(N_3\). In detail, the neighborhood structures are:

  • \(N_1\) (one-element swap): The elements of two given positions i and j are swapped, i.e., \(i \leftrightarrow j\);

  • \(N_2\) (one-element insertion): Given two positions i and j, position i is inserted immediately after position j;

  • \(N_3\) (three-elements change): The elements of three given positions i, j, and u are changed, i.e., \(i \rightarrow j\), \(j \rightarrow u\), and \(u \rightarrow i\). Notice that auxiliary variables are used to avoid losing information.

figure a

The local-search phase in Algorithm 1 consists of the variable neighborhood descent heuristic [12]. It starts by looking for the first solution in the neighborhood structure \(N_k(x^\prime )\), initially for \(k=1\), that is better than \(x^\prime \), the solution of the shaking phase. If this is true, solution \(x^\prime \) is updated and the search continues on the same neighborhood structure; otherwise, the search continues on the next neighborhood structure. It is worth mentioning that all possibilities of positions in \(N_1\), \(N_2\), and \(N_3\) are tested until finding the first improved solution if one exists. After the local search, solution \(x^{\prime }\) is compared with the current solution x. The latter is updated if \(x^{\prime }\) is better; otherwise, the while loop is broken.

The value of a solution x is determined by the function F() in Algorithm 2. This function is based on the decoder proposed by [22]. The difference is that we are using only one placement rule, which is a combination of the bottom-left and top-left rules. The proposed placement rule divides the solution vector x into two parts. The left half of vector x assumes that items are positioned by the bottom-left rule, while the right half part has its items positioned by the top-left rules.

figure b

Figure 2 has an example of Algorithm 2 applied to a solution with four items in the sequence \(\{1, 4, 3, 2\}\). Items 1 and 4 are in the left half of x and then are packed by the bottom-left rule. Items 3 and 2 are in the right half part and then are packed by the top-left rule. The resulting packing has length L, which is the cost of the solution returned by the function F().

4 Computational Experiments

We coded all algorithms in the C++ programming language and performed computational experiments on literature instances. The experiments are executed in a computer with an Apple M2 processor, 8 GB of RAM, and macOS 13 as the operating system. The proposed VNS has a single parameter to define, which is the maximum number of iterations. We define it as a maximum time limit, set to 120 s, to solve each instance. The VNS runs 5 times and the best solution found among these is reported.

Fig. 2.
figure 2

Example of packing obtained with the function F() for a solution x.

Full size image
Table 1. Data of the 22 instances.
Full size table
Table 2. Comparing the VNS with two other literature algorithms.
Full size table

We consider 22 instances from the literature, which may be found on the website of the EURO Special Interest Group on Cutting and PackingFootnote 1. Table 1 has the instance name, the authors who proposed the instance, the total number of items, and the strip width. Concerning the grid of points, we discretize the strip, the inner-fit rasters, and no-fit polygons by one unit of distance according to [19].

Table 2 has the results obtained with the proposed VNS and two other literature methods, i.e., the branch-and-cut algorithms in [19, 22]. The algorithm in  [19] is not able to obtain the solution of two instances, namely shapes15 and shirts5-10. On the other hand, the VNS and the algorithm in [22] report a solution to all instances. The proposed VNS obtains equal solutions for 14 out of 22 instances. For the others, the VNS improves the solution of 6 instances, namely poly1a, poly1b, shapes5, shapes7, shapes9, and shapes15. On the other hand, the VNS is worse for instances shirts2-4 and shirts3-6, differing from one unit in terms of length. The computing time of the VNS is not reported in the table because it is used as the stopping criterion and is equal to 120 s for each instance. In Fig. 4, we show the improved solutions obtained with the proposed VNS.

Fig. 3.
figure 3

Solutions improved by the proposed VNS - part 1.

Full size image
Fig. 4.
figure 4

Solutions improved by the proposed VNS - part 2.

Full size image

5 Concluding Remarks

This paper is related to the two-dimensional irregular strip packing, an open-dimension problem, for which the strip’s length is minimized while packing all items. Besides being an NP-hard problem, it is found in many real-world applications. As the items to pack may have an irregular shape, we use geometric tools such as the inner-fit raster and no-fit raster to guarantee feasible solutions. The proposed VNS has the shaking phase defined over a single neighborhood structure, while the local search as the VND has three neighborhoods based on swap and insertion movements. Due to the solution representation, we define a function to obtain the packing and so its length. In this function, items in the given sequence are packed by a combination of the bottom-left and top-left placement rules (Fig. 2).

The computational experiments on literature instances show the proposed VNS is competitive, obtaining equal or better solutions for 90.90% of the instances. For the other instances, the difference is one unit in the strip’s length, which is relatively small. We notice that there is room for improvement in many directions. One could be in the proposal of new ways to code and decode a solution, as in the case of defining new placement rules. Further exploration of the scale adopted to the grid could also be worthwhile to identify the trade-off between solution quality and computing time. Another interesting direction is the combination of heuristics and mathematical programming models. It could be important to have a comparison between different paradigms, e.g., single trajectory heuristics versus population-based ones. In terms of instances, one direction could be to have items with holes and allow the rotation of items.