Combining Local Search and Genetic Algorithm for Two-Dimensional Guillotine Bin Packing Problems with partial sequence constraint Filipe Souza and Diarmuid Grimes Department of computer science Cork Institute of Technology Cork, Ireland {filipe.luca-desouza@mycit.ie,diarmuid.grimes@cit.ie} Abstract. In this work we consider a variant of the standard bin packing problem, known as the the two-dimensional guillotine cutting problem. This is a widely occurring problem in industry, for example for reducing the economic and environmental costs of glass production. This vari- ant can also incorporate an additional partial sequencing constraint on batches of sub-items in comparison with the traditional bin packing prob- lem. We propose a hybrid metaheuristic approach combining a dedicated genetic algorithm with a local search for solution refinement. The genetic algorithm has a number of dedicated aspects for the problem at hand, such as a complex phenotype representation with multi gene-types, a par- tial fitness function and different mutation operators for different parts of the chromosome tuple. Empirical results on public instances demon- strate the effectiveness of the hybrid algorithm and provide insight into interleaving local search with population-based approaches. Keywords: Bin Packing Problem · Genetic Algorithm · Local Search · Phenotype · Genotype · Fitness Function 1 Introduction The Two-Dimensional Bin Packing Problem (2BP) aims to allocate several rect- angular items to a set of rectangular bins, in a way that the number of re- quired 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 20181 , where the items from the same order (stack) have to be cut in a specific sequence. 1 https://www.roadef.org/challenge/2018/en/index.php Copyright 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 2 Filipe Souza and Diarmuid Grimes To address this issue a novel technique combining a dedicated genetic algo- rithm 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 Algo- rithm 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 meth- ods 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 Algo- rithms such as a complex phenotype representation of a chromosome with mul- tiple gene-types, a partial fitness function, and the application of different mu- tation operators for different parts of a chromosome. Additional aspects inves- tigated 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 Prob- lem, 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 sim- plistic bounds and pseudo-dominance properties. The evaluation also provided opportunity to develop a number of insights into the behavior of a hybrid ap- proach such as GALS-2BP. 2 Problem definition 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 (wi , hi ) representing its width w and its height h. Definition 2 (Stack). A stack S = {i1 , i2 , ..., ij } is an ordered sequence of items such that i1 < cut i2 < cut ... < cut ij , basically meaning that item i1 must be cut before item i2 , which is one of the constrains related to deliveries and item processing. For example in an instance with three stacks s1 = {i1 , i2 }, s2 = {i3 , i4 , i5 }, and s3 = {i6 , i7 }, two feasible sequence of cutting can be define as below: – The sequence s1 , s2 , s3 , s3 , s2 , s1 , s2 means i1 , i3 , i6 , i7 , i4 , i2 , i5 . – The sequence s2 , s3 , s2 , s1 , s3 , s1 , s2 means i3 , i6 , i4 , i1 , i7 , i2 , i5 . 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. [n I= sk k=1 Combining Local Search and Genetic Algorithm for 2BP 3 Definition 4 (Bin). A bin b is characterized by a pair (Wb , Hb ) representing its width W and its height H. The set of bins B = {b1 , b2 , ..., bq }, where b1 < cut b2 means that bin b1 has to be used before the bin b2 . In addition the bin size is standardised. ∀a, b ∈ B : Wa = Wb ∀a, b ∈ B : Ha = Hb Definition 5 (Guillotine cut). A guillotine cut is the cut that divides a nonempty subset p into two disjoint rectangular subsets p01 and p02 such that no item i ∈ I is intersected by the cut between p01 and p02 . Definition 6 (Cutting pattern). A set cutting pattern P = {p1 , p2 , ..., pt } is a feasible solution, where ∀p ∈ P , p is a guillotine cutting pattern that divides a rectangular glass piece pt in two new rectangular piece pt+1 and pt+2 . Figure 1 depicts an example of guillotine pattern for a bin and the order of the cuts. Fig. 1. Example of feasible cutting pattern diagram Definition 7 (Waste). A waste ω is a p, where ∀i ∈ I : i ∩ p = 0. In Figure 1, p7 and p8 are examples of waste. ω = p ⇒ ∀i ∈ I : i ∩ p = 0 Definition 8 (Residual). A residual R is the last element of P . R = p|P | 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 4 Filipe Souza and Diarmuid Grimes 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: xib ∈ {0, 1} should be 1 iff item i is packed into bin b. yb ∈ {0, 1} should be 1 iff bin b is used. X X minimize Hb Wb yb − (HR WR ) − wi hi (1) b∈B i∈I X X subject to: wi hi <= Hb W b (2) i∈I b∈B X xib = 1 ∀i ∈ I (3) b∈B X wi hi xij ≤ Wb Hb ∀b ∈ B (4) i∈I s∩q =0 ∀s, q ∈ S, s 6= q (5) yBj ≥ yBj+1 ∀j ∈ {1, 2, ..., |B| − 1} (6) j∈ /p3i ∀i, j ∈ I, i 6= j, ∃p ∈ P (7) xib ∈ {0, 1} ∀i ∈ I, ∀b ∈ B (8) yb ∈ {0, 1} ∀b ∈ B (9) 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 de- fects at given locations and that must not be included in our cut items, is not considered in this work. 3 Related 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 Combining Local Search and Genetic Algorithm for 2BP 5 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. 4 Proposed Hybrid Algorithm 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 solu- tion 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 solu- tion, 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). 6 Filipe Souza and Diarmuid Grimes Fig. 2. Hybrid Algorithm diagram Fitness Function The fitness function presented in equation 1 was imple- mented 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. There- fore 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. P i∈I wi hi xib (10) Wb Hb 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. Selection Method In order to achieve a balance between biasing towards fit- ter individuals (i.e. better solutions) and the necessity of being computationally efficient, the chosen selection method was Tournament Selection[1]. In particu- lar, binary tournament selection was used, where two individuals are randomly chosen and the fitter of the two is selected. Combining Local Search and Genetic Algorithm for 2BP 7 Crossover Operator Due to the specificity of this problem, the chromo- some is divided into three parts as previously stated. Hence, different crossover operators were developed for each part. For the permutation part two differ- ent 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. Mutation Operator The mutation operator works in the following way: First, a subset of offspring population is selected based on the mutation rate prob- ability. 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 posi- tions 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 with- out modifications. Then, the rest of the new population is generated by the processes of crossover and mutation of the individuals from the previous popu- lation (including the elite chromosomes). Local Search 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 5.1 Experimental design The configuration presented in Table 1 below was used to assess the perfor- mance 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. 8 Filipe Souza and Diarmuid Grimes Table 1. Configurations parameters for the benchmark experiment. Parameter value Iterations 10,000 Population Size 100 Selection Tournament Crossover PMX Mutation Reciprocal Exchange Mutation Rate 30% Elitism Rate 10% Local Search 100% 5.2 Preliminary Experiments 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 homo- geneous due to the strong specificity of the Local Search Process. To overcome this issue, a Replacement Strategy component was developed. Fig. 3. Graph of occupation rate improvement over generations for instance X2 per different Local Search rates The proposed Replacement Strategy was implemented based on that pro- posed 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 chro- mosome was of N genes, where each gene was composed by the three parameters. Combining Local Search and Genetic Algorithm for 2BP 9 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 moti- vation and inspiration behind the mutation operator described in the previous section. 5.3 Evaluation 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-of- the-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. Fig. 4. Graphic shows the comparison of the GALS-2BP Algorithm and the MBA*, in different sizes of instances. 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. 10 Filipe Souza and Diarmuid Grimes Fig. 5. Graphic shows the comparison of the GALS-2BP Algorithm and the MBA* per average Stack size. 6 Discussion 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 popu- lation evolves with less noise in the crossover and mutation operator. The local search also has a larger neighbourhood to improve the solution when fewer se- quencing constraints and therefore more possibilities for improvement. Fig. 6. Graph of the average occupation rate improvements along 10 executions over generations for instance X6 for best solution and average population at different Local Search rates 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 Combining Local Search and Genetic Algorithm for 2BP 11 the PMX crossover is has a higher capacity to preserve the parents characteris- tics. 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. 7 Conclusion In this paper we introduced a novel hybrid algorithm, combining Genetic Algo- rithms and Local Search, to solve the Two-Dimensional Guillotine Bin-Packing problem. Empirical analysis demonstrated the worth of the method, in partic- ular 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. References 1. Abdulal, W., Ramachandram, S.: Reliability-Aware Genetic Scheduling Algorithm in Grid Environment. International Conference on Communication Systems and Network Technologies pp. 673–677 (2011) 2. Baker, B., Coffman, E., Rivest, R.: Orthogonal Packings in Two Dimensions. SIAM J. Comput. 9, 846–855 (1980). https://doi.org/10.1137/0209064 3. Baldi, M.M., Crainic, T.G., Perboli, G., Tadei, R.: Branch-and-price and beam search algorithms for the Variable Cost and Size Bin Packing Problem with optional items. Annals of Operations Research 222, 125–141 (2014) 4. Bennell, J.A., Soon Lee, L., Potts, C.N.: A genetic algorithm for two-dimensional bin packing with due dates. International Journal of Production Economics 145, 547–560 (2013) 5. Fernández, A., Gil, C., Márquez, A.L., Baños, R., Montoya, M.G., Parra, M.: A memetic algorithm for two-dimensional multi-objective bin-packing with con- straints. Proceedings of the 13th annual conference companion on Genetic and evolutionary computation - GECCO p. 341 (2011) 12 Filipe Souza and Diarmuid Grimes 6. Gilmore, P.C., Gomory, R.E.: Multistage cutting stock problems of two and more dimensions. Operations research 13, 94–120 (1965) 7. Gonçalves, J.F., Resende, M.G.: A biased random key genetic algorithm for 2D and 3D bin packing problems. International Journal of Production Economics 145, 500–510 (2013) 8. Huang, W., Ye, T., Chen, D.: Bottom-Left Placement Theorem for Rectangle Pack- ing. arXiv:1107.4463 [cs] (2011) 9. Hwang, H., Choi, B., Lee, G.: A genetic algorithm approach to an integrated prob- lem of shelf space design and item allocation. Computers & Industrial Engineering 56, 809–820 (2009) 10. Jakobs, S.: On genetic algorithms for the packing of polygons. European Journal of Operational Research 88, 165–181 (1996) 11. Kierkosz, I., Luczak, M.: A hybrid evolutionary algorithm for the two-dimensional packing problem. Central European Journal of Operations Research 22, 729–753 (2014) 12. Libralesso, L., Fontan, F.: An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem. arXiv:2004.00963 [cs] (2020) 13. Liu, D., Teng, H.: An improved BL-algorithm for genetic algorithm of the orthog- onal packing of rectangles. European Journal of Operational Research pp. 413–420 (1999) 14. Lodi, A., Monaci, M., Pietrobuoni, E.: Partial enumeration algorithms for Two- Dimensional Bin Packing Problem with guillotine constraints. Discrete Applied Mathematics pp. 40–47 (2017) 15. Merz, P., Freisleben, B.: Memetic Algorithms for the Traveling Salesman Problem. Complex Systems p. 50 (2001) 16. Moscato, P.: On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts - Towards Memetic Algorithms. Caltech Concurrent Computation Program (1989) 17. Moscato, P., Cotta, C.: A Gentle Introduction to Memetic Algorithms. Operations Research & Management Science 57, 105–144 (2003) 18. Pisinger, D., Sigurd, M.: Using Decomposition Techniques and Constraint Pro- gramming for Solving the Two-Dimensional Bin-Packing Problem. INFORMS Journal on Computing 19, 36–51 (2007) 19. Puchinger, J., Raidl, G.R.: Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research 183, 1304–1327 (2007) 20. Ronald, S.: Duplicate genotypes in a genetic algorithm. IEEE International Con- ference on Evolutionary Computation Proceedings. IEEE World Congress on Com- putational Intelligence (Cat. No.98TH8360) pp. 793–798 (1998)