The Two-Dimensional Bin Packing Problem (2BP) aims to allocate several rectangular items to a set of rectangular bins, in a way that the number of required bins is minimized. Most of the literature related to Cutting and Packing problems are based on heuristic [2,8,13,14] or Branch-and-Bound [3,12,18,19] approaches.
Cutting glass optimization is an important industrial specialization of the 2BP. The initial constraint in this problem is that the glass jumbo (bin) must be cut in guillotine cuts, i.e. orthogonal cuts going from one side of the sheet component to the other. In this work we consider the variant where the items can be rotated by 90 degrees and with partial sequencing constraints introduced by the ROADEF/EURO challenge 2018 1 , where the items from the same order (stack) have to be cut in a specific sequence.
To address this issue a novel technique combining a dedicated genetic algorithm interleaved with a local search operator is proposed, denoted as GALS-2BP. To the best of our knowledge, the use of such a hybrid algorithm to solve the 2BP, is still insufficiently explored. The method proposed is investigated not only to generate good performance for the variant studied but also to provide further insight into the behavior of such hybridized techniques.
Investigating the potential of combining Local Search and Genetic Algorithm can produce impressive results, due to the complementary nature of the approaches. Genetic algorithms look at combining good solutions, but without looking at why a solution is good or bad. On the other hand, local search methods only consider one solution, but they specifically look for where the solution can be improved and make changes based on this.
Furthermore, this work digs deep into many components of Genetic Algorithms such as a complex phenotype representation of a chromosome with multiple gene-types, a partial fitness function, and the application of different mutation operators for different parts of a chromosome. Additional aspects investigated include crossover operators, elite survival, and periodic rediversification of the population to avoid stagnation.
The performance of the GALS-2BP approach was evaluated on the instances proposed in the ROADEF/EURO challenge 2018: Cutting Optimisation Problem, and shown to be competitive with the winner of that challenge: the MBA* algorithm [12]. The latter is an anytime tree search algorithm with some simplistic bounds and pseudo-dominance properties. The evaluation also provided opportunity to develop a number of insights into the behavior of a hybrid approach such as GALS-2BP.
The guillotine cutting problem considered here can be defined as follows:
Definition 1 (Item). An item i is a glass piece to cut, characterized by a pair (w i , h i ) representing its width w and its height h.
A stack S = {i 1 , i 2 , ..., i j } is an ordered sequence of items such that i 1 < cut i 2 < cut ... < cut i j , basically meaning that item i 1 must be cut before item i 2 , which is one of the constrains related to deliveries and item processing. For example in an instance with three stacks s 1 = {i 1 , i 2 }, s 2 = {i 3 , i 4 , i 5 }, and s 3 = {i 6 , i 7 }, two feasible sequence of cutting can be define as below:
Definition 3 (Batch). The set of items to cut is called batch I. It corresponds to a customer order using the stack notation, the item set I can be partitioned into n stacks. A guillotine cut is the cut that divides a nonempty subset p into two disjoint rectangular subsets p 1 and p 2 such that no item i ∈ I is intersected by the cut between p 1 and p 2 .
Definition 6 (Cutting pattern). A set cutting pattern P = {p 1 , p 2 , ..., p t } is a feasible solution, where ∀p ∈ P , p is a guillotine cutting pattern that divides a rectangular glass piece p t in two new rectangular piece p t+1 and p t+2 . Figure 1 depicts an example of guillotine pattern for a bin and the order of the cuts. The objective function is to minimize the geometrical loss of the cutting patterns applied to bins. In order to compute the loss area, glass leftover must not be taken into account, since they can be reused after cutting. Only the residual in the last cutting pattern will be considered in order to simplify the residual management. This residual is represented by the waste at right of the last 1-cut performed in the last cutting pattern in a solution as described in definition 8. So that, the problem can thus be modeled as:
subject to:
s ∩ q = 0 ∀s, q ∈ S, s = q (5)
Note that in our work, we consider a slight simplification of two-dimensional cutting glass problem proposed in the ROADEF/EURO challenge 2018. Namely the defects constraint of the challenge problem, where a bin may contain defects at given locations and that must not be included in our cut items, is not considered in this work.
The 2BP has been a problem of interest for decades [6]. One of the most popular heuristic approaches to tackle the two-dimensional bin packing problem was proposed by Baker et al. [2], the well-known bottom-left (BL) heuristic. It tries to minimize the height of each piece in a rectangular bin, focusing on orthogonal and oriented packing.
Numerous variants of the bottom-left heuristic have been proposed since then (e.g. [8,13]). Even though the recent literature have recommended block-based placement [14] for guillotine problems, due to the additional ordered sequence constraint in our problem, we chose item-based placement based on BL, similar to [10].
In terms of relevant GA approaches to the 2BP, Goncalves and Resende in [7] proposed a biased random-key genetic algorithm (BRKGA) approach. In their work a novel fitness function was also proposed which we have incorporated for our evolutionary process fitness function. While, Hwang et al.in [9] used Genetic Algorithms as an approach to solving a variant of 2BP with guillotine constraint for retail shelf space design, in this variant the size of the items can be mutated in order to maximize the demand rate of the items, which is a function of the quantity displayed and the location in the shelf space.
To the best of our knowledge, the idea of combining Genetic Algorithm with local search approach to solve a specific problem was introduced in the late 80s with the term of Memetic Algorithms [16], and since then it has been the focus of many research works (See [17,15,5]). While in the matter of 2BP, Kierkosz and Luczak in [11] proposed an interesting approach that combines an evolutionary algorithm and a tree search, where the GA solution is used as an input for the tree search step. The same idea is implemented in this paper's approach, where the LS uses the GA solution to generate the final solution.
Finally, the current State of the art algorithm to solve the variation of 2BP presented in this work comes from [12], where they proposed the algorithm MBA*. The approach involves a tree search algorithm with aggressive pruning which diminishes over time.
Figure 2 shows the macro process of the GALS-2BP algorithm developed in this work. As can be observed, the macro-structure is almost the same as the general GA, with only the addition of two new steps. The first one is the Replacement strategy that aims to avoid homogeneous population and the second one is a Local Search step that refines the GA solutions in order to improve the final solution. Thus, every GA step is guided by the cost of the solutions refined by the Local Search.
Chromosome Representation Using the standard GA terminology, a solution to a problem is given by a set of genes encoded in a chromosome. This solution can be represented directly or indirectly by the chromosome. When it is a direct representation, the chromosome will be the solution of the problem, referred to as a Genotype [20]. An indirect representation on the other hand, has the chromosome as the input to a particular procedure to generate the solution, that representation is known as a Phenotype [7]. In this work, the indirect representation was used given that the problem solution is too computationally expensive.
For this reason, the chromosome consists of three subgroups of genes that are combined to compute the fitness of the chromosome. Each chromosome is composed of 3N genes, where N is the number of items in the instance problem. The first N genes represents the sequence in which the items will be cut (this part of the chromosome works the same as a permutation problem encoding). The next N genes represent whether the item will be rotated or not. The final N genes represent the orientation of the cutting for the item (horizontal or vertical). Fitness Function The fitness function presented in equation 1 was implemented for the Genetic Algorithm. That function gives the final cost for the solution. However, it is necessary to place each item in its bin to calculate or update this fitness function, and this requires a high computational effort. Therefore this is impracticable for the Local Search step in computing the cost of each neighborhood move. Instead, the occupation rate of the bin is used to guide search. Equation 10 formally describes how the occupation rate is calculated for a given bin.
Initial Population A high level of diversity in the initial population is essential to avoid early stagnation in GAs. Thus, the initial population was created with a random set of item sequences and also randomly assigning the rotation position and the cutting orientation. Hence, the diversity of the population is ensured, while the Local Search step aids in the intensification.
In order to achieve a balance between biasing towards fitter individuals (i.e. better solutions) and the necessity of being computationally efficient, the chosen selection method was Tournament Selection [1]. In particular, binary tournament selection was used, where two individuals are randomly chosen and the fitter of the two is selected.
Crossover Operator Due to the specificity of this problem, the chromosome is divided into three parts as previously stated. Hence, different crossover operators were developed for each part. For the permutation part two different permutation-based crossover operators were tested -uniform order-based crossover and PMX. While the two parts with Boolean valued genes followed the permutation operator chosen. In other words, when the PMX is used for permutation, two-point crossover is used for the Boolean parts, and uniform crossover was used for the uniform order-based operator case.
The mutation operator works in the following way: First, a subset of offspring population is selected based on the mutation rate probability. Then, for each offspring, it is decided randomly which part (sequence, rotation, cut orientation) of the chromosome will be mutated. If the sequence part is chosen, the algorithm will apply a Reciprocal Exchange Mutation on that part of the chromosome, where two random genes are selected and their positions are swapped. Otherwise, Boolean genes are selected based on the mutation rate and their values are flipped.
Elite survival Elite survival was included such that the top x percent of the best solutions of the previous population are copied to the new population without modifications. Then, the rest of the new population is generated by the processes of crossover and mutation of the individuals from the previous population (including the elite chromosomes).
The Local Search is the last step to generate a new population. That step tries to optimize the wasted space left by the Genetic Algorithm solution. In order to do that, for each wasted space in the bins the Local Search algorithm searches in the whole neighbourhood composed by the next item of each stack. If there is more than one neighbour suitable for the waste space, it is randomly selected between the three best fit items and the selected item will be moved to fill the wasted space. The quality of the neighbor move is defined by the size of the smallest new wasted space that it creates after placing the item.
5 Experimental results
The configuration presented in Table 1 below was used to assess the performance of the GALS-2BP algorithm comparing it to the MBA* algorithm. Both algorithms were run under the same conditions and on the same machine (Mac-Book Pro 2.4 GHz Intel Core i5 machine with 8GB 1600 MHz DDR3 on macOS High Sierra), with a runtime cutoff of 10 minutes per instance. Furthermore, as the proposed approach has stochastic components, the presented results are the average of 10 runs with different seeds.
Replacement Strategy During initial experimentation, it was observed that the approach was not able to improve the solutions after the initial population for some instances. This is illustrated in Fig. 3, where for the instance X2 the algorithm was not able to improve the solution after the initial population even when Local Search was applied for more than 40% of the population. Analysing the problem, it was discovered that the population was rapidly becoming homogeneous due to the strong specificity of the Local Search Process. To overcome this issue, a Replacement Strategy component was developed. The proposed Replacement Strategy was implemented based on that proposed by Bennell et al. [4]. At every fifty generations, any duplicated solution is overwritten by a new solution that is a copy of the best solution with some genes mutated. In this way it is possible to avoid premature convergence and also create diversity on the population without loss of specificity.
Chromosome Representation Initially a solution was represented by a chromosome was of N genes, where each gene was composed by the three parameters.
However, this was found to be ineffective as the sequencing constraint resulted in swapping of information between genes. In this way the children were losing a lot of genetic information from their parents. This problem was particularly prominent in instances where there were many items per stack. This motivated the representation with 3N genes given in the previous section.
Mutation Operator In the initial implementation, the mutation operator was divided into two parts. The first one dealt with the Boolean genes, where each gene swapped its value based on the mutation rate probability. The second part involved a permutation mutation operator. However, when analysed empirically it was observed that the operator behaviour was extremely sensitive to the size of the instance. In other words, the same mutation rate could generate a high number of mutations in a big instance, which made the search highly stochastic, while in a small instance it rarely generated any mutation. This was the motivation and inspiration behind the mutation operator described in the previous section.
Figure 4 shows the results obtained with the GALS-2BP algorithm compared to the MBA* solution in the set of instances with size ranging from 5 to 656 items. As depicted in the graph, the GALS-2BP achieves results near to the state-ofthe-art in instances with up to 300 items. However, the gap tends to increase in larger instances. Nevertheless, the GALS-2BP still found solutions with around 90% of occupation rate, even in instances greater than 400 items. Figure 5 depicts the benchmark between the GALS-2BP algorithm and the MBA* algorithm per different average of stack size. The GALS-2BP managed to outperform the benchmark algorithm in instances with less than 5 items per stack, and also managed to catch results very near to the MBA* in instances with up to 15 items per stack on average. Unfortunately, when the number of items per stack starts to increase more than this, the difference tends to increase as well.
Even though the GALS-2BP did not outperform the overall results of the MBA* algorithm [12], it still found very good solutions, particularly for instances with fewer sequencing constraints. It is also important to highlight the consistency of the proposed hybrid algorithm, where in the total of fifty different executions for each instance the best result found throughout these executions always remained at most 2% above the average best solution for each instance.
The reason for the better performance on instances with fewer sequencing constraints is that the GA has more freedom to combine solutions. The population evolves with less noise in the crossover and mutation operator. The local search also has a larger neighbourhood to improve the solution when fewer sequencing constraints and therefore more possibilities for improvement. With regard to the crossover operators it was found that the PMX crossover performed better. This is due to the problem's high sensitivity to changes, since the PMX crossover is has a higher capacity to preserve the parents characteristics.
It should also be noted that, since the Local Search is executed before the calculation of the fitness function, the goal of the GA is effectively to generate the best inputs for the Local Search step instead of looking for the best final solution. In order to demonstrate the impact of this, the Local Search was run for different proportions of the population (from 0% to 100% in steps of 10%).
The results of this are shown in Figure 6. One can clearly see, in the average occupation rate for the population along iterations, the unstable behaviour of the algorithm when the Local Search is used in only a part of the population. This instability happens because part of the population is trying to evolve to the best final solution while the other part is trying to evolve to the best input for the Local Search process. Thus, a worse solution from the GA can in some cases be a better input to the Local Search than a good solution would be. For example a worse solution can result in avoiding a local minimum in the Local Search.
In this paper we introduced a novel hybrid algorithm, combining Genetic Algorithms and Local Search, to solve the Two-Dimensional Guillotine Bin-Packing problem. Empirical analysis demonstrated the worth of the method, in particular finding an average occupation rate of 91% across a range of challenging instances. In future work, one are for improvement would be the development of placement strategies to help the process of decoding the phenotype chromosome into a better final solution. This would be extremely beneficial, particularly for instances with many sequencing constraints.