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 variant can also incorporate an additional partial sequencing constraint on batches of sub-items in comparison with the traditional bin packing problem. We propose a hybrid metaheuristic approach combining a dedicated genetic algorithm with a local search for solution re nement. 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 partial tness function and di erent mutation operators for di erent parts of the chromosome tuple. Empirical results on public instances demonstrate the e ectiveness of the hybrid algorithm and provide insight into interleaving local search with population-based approaches.
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 [
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 speci c sequence. 1 https://www.roadef.org/challenge/2018/en/index.php
To address this issue a novel technique combining a dedicated genetic algorithm interleaved with a local search operator is proposed, denoted as GALS2BP. To the best of our knowledge, the use of such a hybrid algorithm to solve the 2BP, is still insu ciently 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 speci cally 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 tness function, and the application of di erent mutation operators for di erent parts of a chromosome. Additional aspects investigated include crossover operators, elite survival, and periodic rediversi cation 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 [
The guillotine cutting problem considered here can be de ned as follows: De nition 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.
De nition 2 (Stack). A stack S = fi1; i2; :::; ij g 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 = fi1; i2g, s2 = fi3; i4; i5g, and s3 = fi6; i7g, two feasible sequence of cutting can be de ne 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.
De nition 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.
I = n [ sk De nition 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 = fb1; b2; :::; bqg, where b1 < cut b2 means that bin b1 has to be used before the bin b2. In addition the bin size is standardised.
8a; b 2 B : Wa = Wb 8a; b 2 B : Ha = Hb De nition 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 2 I is intersected by the cut between p01 and p02.
De nition 6 (Cutting pattern). A set cutting pattern P = fp1; p2; :::; ptg is a feasible solution, where 8p 2 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. De nition 7 (Waste). A waste ! is a p, where 8i 2 I : i \ p = 0. In Figure 1, p7 and p8 are examples of waste.
! = p ) 8i 2 I : i \ p = 0 De nition 8 (Residual). A residual R is the last element of P .
R = pjP j
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 b2B i2I X xib = 1 b2B X wihixij i2I s \ q = 0 yBj
yBj+1 j 2= p 3 i xib 2 f0; 1g yb 2 f0; 1g b2B WbHb 8i 2 I 8b 2 B 8s; q 2 S; s 6= q 8j 2 f1; 2; :::; jBj 1g 8i; j 2 I; i 6= j; 9p 2 P 8i 2 I; 8b 2 B 8b 2 B (1) (2) (3) (4) (5) (6) (7) (8) (9) 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 de nition 8. So that, the problem can thus be modeled as: xib 2 f0; 1g should be 1 i item i is packed into bin b. yb 2 f0; 1g should be 1 i bin b is used. minimize X HbWbyb
(HRWR) subject to:
X wihi <= X HbWb
X wihi i2I
Note that in our work, we consider a slight simpli cation 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. 3
The 2BP has been a problem of interest for decades [
Numerous variants of the bottom-left heuristic have been proposed since then
(e.g. [
In terms of relevant GA approaches to the 2BP, Goncalves and Resende in [
To the best of our knowledge, the idea of combining Genetic Algorithm with
local search approach to solve a speci c problem was introduced in the late 80s
with the term of Memetic Algorithms [
Finally, the current State of the art algorithm to solve the variation of 2BP
presented in this work comes from [
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 [
For this reason, the chromosome consists of three subgroups of genes that are combined to compute the tness of the chromosome. Each chromosome is composed of 3N genes, where N is the number of items in the instance problem. The rst 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 nal N genes represent the orientation of the cutting for the item (horizontal or vertical). Fitness Function The tness function presented in equation 1 was implemented for the Genetic Algorithm. That function gives the nal cost for the solution. However, it is necessary to place each item in its bin to calculate or update this tness function, and this requires a high computational e ort. 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.
Pi2I wihixib
WbHb (10) 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 intensi cation.
Selection Method In order to achieve a balance between biasing towards
tter individuals (i.e. better solutions) and the necessity of being computationally
e cient, the chosen selection method was Tournament Selection[
Mutation Operator The mutation operator works in the following way: First, a subset of o spring population is selected based on the mutation rate probability. Then, for each o spring, 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 ipped.
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 modi cations. 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).
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 t items and the selected item will be moved to ll the wasted space. The quality of the neighbor move is de ned by the size of the smallest new wasted space that it creates after placing the item. 5 5.1
Experimental design The con guration 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 (MacBook Pro 2.4 GHz Intel Core i5 machine with 8GB 1600 MHz DDR3 on macOS High Sierra), with a runtime cuto of 10 minutes per instance. Furthermore, as the proposed approach has stochastic components, the presented results are the average of 10 runs with di erent 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 speci city 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.[
Mutation Operator In the initial implementation, the mutation operator was divided into two parts. The rst 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. 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-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 di erent 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 di erence tends to increase
as well.
Even though the GALS-2BP did not outperform the overall results of the MBA*
algorithm [
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 tness function, the goal of the GA is e ectively to generate the best inputs for the Local Search step instead of looking for the best nal solution. In order to demonstrate the impact of this, the Local Search was run for di erent 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 nal 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
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 nding 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 nal solution. This would be extremely bene cial, particularly for instances with many sequencing constraints.