Optimization of one-dimensional bin packing problem using a hybrid flower pollination algorithm

Abstract

Keywords: Bin Packing; Flower Pollination Algorithm; Genetic Algorithm; Hybridization

Introduction

The one-dimensional bin packing problem (1BPP) is defined as the optimal placement of boxes in certain sizes inside of containers in certain sizes. The depth (a) and

width (b) dimensions of the boxes are considered to be the same (a1 = a2 =…. = an and b1 = b2 =…= bn) and their height (h) are different (h1 ≠ h2 ≠… ≠ hn) (Figure 1). The depth (D) and width (W) dimensions of the containers are whole numbers which are exact times of the box dimensions

*Corresponding author. *E-mail address: harun.gezici@klu.edu.tr This paper was recommended for publication in revised form by Regional Editor Oscar Castillo Published by Yıldız Technical University Press, İstanbul, Turkey Copyright 2021, Yıldız Technical University. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

(D = k.a and W = l.b, k and l ∈ Z+). The container height (H) dimension does not have to be exact times of the box height dimension. The total height of the boxes placed in the containers should not exceed the height of the container. The aim is to maximize the container occupancy rate and use a minimum number of containers. The process of placing boxes in containers is done by humans or robots. According to the availability of the working area, a loading direction is determined for loading the boxes into the containers. The number and dimensions of the boxes to be loaded are already known. Based on these parameters, the optimum box order is tried to be determined. Some of the containers may remain empty after loading. The constraints and decision structure of 1BPP are defined as follows [1,2].

BPP is in the Np-hard problem class [3]. It can be adapted to real-world problems in areas such as logistics and manufacturing [4,5]. 1DBPP is used in memory management in the computer industry. In the literature, exact, heuristic, and meta-heuristic methods are suggested for the solution of BPP [6,7]. Although the exact methods give favorable results in the solution of small-scale problems, they need a long calculation time in large-scale problems [8]. Calculation time with meta-heuristic methods is short, but it does not always guarantee the correct result. Studies on meta-heuristic methods are ongoing due to short calculation times and successful results [9,10]. Meta-heuristic algorithms such as ant colony algorithm [11], particle swarm optimization algorithm [12], GA [13,14], tabu search [15], ILWOA [6] have been used in the solution of BPP. It is known that there is no single algorithm that can solve all optimization problems [16,17]. Applying meta-heuristic algorithms in pure form to BPP may not yield optimum results. For this reason, in some studies, it is preferred to transform the meta-heuristic algorithms into a hybrid structure while they are applied to BPP [18–20]. In recent years, Levy-based meta-heuristic optimization algorithms have been used for the solution of the BPP, and obtained results were successful. Studies on ILWOA and Adaptive Cuckoo Search based on levy distribution, which provide excellent results in the solution of the BPP, have been published previously [6,20]. In these studies, it is seen that the Levy distribution improves the solution quality of the algorithm. Levy distribution transforms the algorithms into the continuous form while bin packing is a problem in discrete form. Algorithms in continuous form can be converted into discrete forms with proven methods [20–23]. In this study, the problem of placing different-sized boxes into containers of the same size will be emphasized [24]. For the solution of the 1D-BPP, a hybrid algorithm was created by reinforcing the Meta-heuristic algorithm by combining the flower pollination algorithm (FPA) with GA. The proposed algorithm is called Improved Hybrid Flower Pollination Genetic Algorithm (IHFPGA). Global searching ability is increased by making changes in the mathematical model of FPA. Mutation operators and the elimination process have been added to the IHFPGA to increase the efficiency of the algorithm. The existence of mutation operators increases the local searching ability of the proposed algorithm. With these changes, the proposed algorithm is aimed to have the ability to search for a better solution space compared to other algorithms in the literature. The proposed algorithm has been compared with other meta-heuristic algorithms with the best results from the literature. The obtained results have confirmed the validity of the proposed algorithm. In Section 2, the literature on 1BPP is summarized. In Section 3, İnformation about the developed algorithm is given. In Section 4, the test parameters are explained and comparative results are given. These results are discussed in Section 5.

(7) where n shows the number of boxes, H indicates the container capacity, hj shows the height of the jth box, m is the number of containers, and B is the set of containers.

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

Related Work on the Bin Packing Problem For the solution of 1DBPP, researchers have proposed various heuristic and meta-heuristic methods. The first suggested heuristics are Next-Fit (NF), First-Fit (FF), BestFit (BF) methods, and their derivatives [4,22]. In the NF method, the incoming box is placed in the last opened container, if the container is not available, a new bin is opened. In the FF method, the next box is placed in the first available space for it. In BF, the next box is placed in the smallest space it can fit. Among the meta-heuristic algorithms, GA is the most known and has been used many times to solve 1DBPP [25,26]. In [3], a new island-parallel grouping GA was developed by modifying the GA for the solution of grouping problems. In [15], the Greedy Randomized Adaptive Search (GRASP) method has been proposed. This method consists of 2 steps. The first stage was created by hybridizing the FF and BF heuristic methods. In the second stage, the taboo search procedure was applied to improve the results obtained in the first stage. A modified GRASP method is presented in [27]. In [28], an iterative local search algorithm based on gradually reducing the number of divisions has been proposed. In [29] First-Fit Decreasing (FFD) algorithm has been modified to shorten the resolution time of 1DBPP. In [30], a heuristic weight annealing algorithm is presented to increase the quality of the results obtained. In [31]’, a multi-step tabu search algorithm based on dynamic programming of object sets has been proposed for the solution of 1DBPP. In [32], a new algorithm is presented, which is a modified version of the Grouping Genetic Algorithm (GGA-CGT). In this study, a new grouping genetic operator is proposed to increase the probability of finding the best genes on chromosomes. In addition, a new gene derivation technique that enables the identification of the search area and the FF procedure to produce a quality starting population are also presented. In [6]’, Whale Optimization Algorithm (WOA) is presented for the solution of 1DBPP. WOA is a meta-heuristic algorithm that mimics whales’ unique hunting strategy. In this study, Lévy flight was adapted to the algorithm to improve the original algorithm. In addition, the algorithm includes an additional mutation stage and a logistic map. In [33], the AFDO method, which is a modified version of the Fitness-Dependent Optimizer (FDO) procedure, is presented. This algorithm is inspired by the characteristics of the breeding process of bee swarms and collective decision-making behavior. This algorithm also includes the FF procedure for optimization of the starting population. In [34], the adaptive African Buffalo Optimization algorithm (ABO) is presented for the solution of 1DBPP. The proposed algorithm is combined with the ranked order value method used for discretization. In [4]’, a modified version of the Squirrel Search Algorithm, inspired by the behavior of squirrels during foraging, is proposed. The proposed algorithm has a procedure that controls the random generation of the starting population. It also has various strategies to improve the quality of the

solution in each iteration. In [35], firefly algorithm, GA, adaptive cuckoo search algorithm, and artificial bee colony algorithm are presented for the solution of 1DBPP. In addition, these algorithms include best fit and better fit heuristics. While solving optimization problems like 1D-BPP, some meta-heuristic algorithms might not result successfully. The reason for it is, as it is explained in the free-lunch theorem, that an optimization algorithm cannot solve all optimization problems [16]. Moreover, definite solutions to some optimization problems like 1D-BPP are not known. Therefore, researchers keep developing more useful optimization algorithms. In this paper, a hybrid meta-heuristic algorithm is proposed for the solution of 1D-BPP. The basis of the algorithm is FPA based on the Levy distribution. To increase the performance of FPA, its mathematical model has been changed. Three different mutation operators of the GA have been added to increase the 1D-BPP solution performance of the algorithm. There is also an elimination operator in the algorithm. This operator removes the boxes that maximize the occupancy rate of the containers in each iteration. This elimination reduces the size of the solution space. Thus, the efficiency of the algorithm is increased in terms of the iteration number, iteration time, and occupancy rate. This study contributes to the literature in 3 ways. First, FPA’s mathematical model has been modified. Second, FPA is hybridized with GA’s mutation operators. Third, the hybrid FPA is applied to 1D-BPP and a competitive algorithm is developed. Implementation of IHFPGA to Bin Packing Problem The proposed algorithm has five main stages. These stages are FPA, discretization, fitness function, mutation, and elimination. A flow chart of the proposed algorithm is given in Figure 2. Flower pollination algorithm The flower pollination algorithm is an optimization algorithm inspired by the pollen transfer in nature. Pollination takes place in two different forms, biotic and abiotic. Biotic pollination is often caused by insects, birds, bees, etc. supplied with pollinators. These pollinators can carry pollen over long distances and show Levy flight behavior. Water and wind are exemplary pollinators for abiotic pollination. Pollination is divided into two as self-pollination and cross-pollination. Self-pollination occurs in the same flower or between different flowers of the same plant. Therefore, self-pollination can be considered as local pollination. Cross-pollination occurs between the flowers of two different plants. Biotic, cross-pollination can occur over long distances. Therefore, cross-pollination can be regarded as global pollination. Due to other factors such as physical proximity and wind, local pollination has an essential share in general pollination activities.

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

FPA is designed based on the features characterized above. There are two critical steps in this algorithm, and these are global pollination and local pollination. Global pollination is modeled by the following equation [36,37]. (8)

(9) In the formula, t is the number of iterations, i is the pollen bundle or solution vector index, Xi is the solution vector, and g is the best of all solution vectors in the current generation. L is the Levy flight, the mathematical model of pollinators’ flight routes. Local pollination can be formulated as follows. (10) In the equation, and represent pollen bunches of different flowers of the same plant or different solutions of the solution set. ε represents a random local pollination distance and has a normal distribution between 0-1 [38]. The switching probability of local pollination or global pollination is controlled by p ∈ [0, 1].

Improved flower pollination algorithm Global pollination and local pollination procedures have been modified to improve the performance of the flower pollination algorithm. New mathematical expressions of the IHFPGA are given in equation 11 (global pollination) and equation 12 (local pollination). (11) (12) fw in the equations is the fit weight and is an array of n elements (where n is the number of elements in the solution set). fw is calculated using equation 13 [6]. (13) where fwn is the initial fitness weight (Equation 14). (14) where fbest is the fitness value of the best solution. f( ) is the fitness value of the ith solution in the tth iteration. Objective Function Using the container number as an objective function causes algorithm stagnation in the solution of BPP because

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

multiple sequences can give the same container number. For this reason, instead of container number using the container occupancy rate as the objective function increases the efficiency of the algorithm (Equation 15).

Mutation phase The mutation process in IHFPGA is performed when FPA cannot improve the result. The mutation process can be achieved with three different methods. These are swap, displacement, and reversion methods. In the swap process, two randomly determined bins are moved [38]. In displacement, a random subarray is selected and transferred randomly to another location [39]. In reversion, a randomly selected subarray is reversed [6]. It is decided by a random number in which method to use. Examples of mutation methods are given in Table 3.

Where m is the number of containers that are used, H is the container capacity, n is the box number of the ith container, h is the height of the box and k is the equation constant and is usually taken as 2. Discretization FPA is an optimization algorithm in continuous form. The solution vector must be converted into a discrete form to apply the FPA method to the BPP. In BPP, four different ways are used to transform the solution set into a discrete form. These are “the largest ranked value, (LRV)” [23], “the smallest position value, (SPV)” [22], “the largest order value, (LOV)” [21], and “the rank order value, (ROV) ” [20]. In Table 2, an example of converting a 6-element continuous form array into a discrete form is given. In the ROV method, the smallest element of the array is assigned 1, while the highest one is assigned 6. The ROV method converts the continuous form set into the nearest numbers when converting it into discrete form, which does not disrupt the numerical sequence of the set. For this reason, the ROV method was preferred as the method of converting into discrete form.

Elimination phase The elimination phase is added to the proposed algorithm to increase efficiency. Each iteration of the algorithm determines the best individual of the population, which is the solution set. This solution set is placed in containers using the FF placement strategy. If the number of iterations is less than half of the total number of iterations, the boxes that fill up the containers are removed from the population. If the iteration number is more than half of the total number of iterations, containers that are as full as the theoretical minimum container occupancy rate (TMCOR) or more are removed from the population. TMCOR is calculated using the theoretical minimum container number (TMCN) (Equation 16 and 17). After this elimination process, the best sequence continues to be searched among the remaining boxes (Figure 3). (16)

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

Figure 3. Elimination strategy. Table 3. Scholl easy class container numbers Ins_no

Ihfpga

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

samples of the Scholl dataset are not available in these studies. Unavailable samples are shown with ‘-’ in the tables. The container number, minimum fitness value, average fitness value, minimum percentage performance, and average percentage performance metrics are used for comparison. The proposed algorithm is run 10 times to be compared with competing algorithms and the results are recorded. The proposed algorithm has a population of 50 and an iteration number of 50. Besides, TMCN is determined as the stop limit of the algorithm (Equation 16). In Table 3, Table 4, and Table 5, the number of containers obtained in previous studies using the Scholl dataset and in this study are given. In the tables, the first column shows

Experimental Results

The proposed algorithm is coded in Python. Simulations (experiments) are performed on a 64-bit operating system with a 2.4 GHz CPU and 6 GB RAM. The proposed algorithm has been tested using the publicly available Scholl dataset [1] (http://or.dei.unibo.it/library/bpplib). The Scholl data set consists of 3 classes that include easy, medium, and difficult examples. The optimum container numbers of the Scholl dataset are known and these values are shown in the tables with m *. The proposed algorithm is compared with AFDO [33], ILWOA [6], and MSBPP [4] algorithms. The studies selected for comparison use different samples from each other and the results of some

Ihfpga

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

Ihfpga

the sample number, the second column shows the name of the sample, the third column shows the number of boxes in the sample, the third column shows the container capacity, the fifth column shows the best-known container numbers, the sixth, seventh and eighth columns show the container numbers of the rival algorithms and the last column shows the container numbers obtained by the proposed algorithm. Table 3 shows the easy class of the Scholl dataset. In this table, it is seen that the proposed algorithm in all examples achieves the best container numbers similar to other algorithms. Table 4 examines the medium class of the Scholl dataset. The proposed algorithm has achieved equal or better results than competing algorithms in all samples. The proposed algorithm has achieved better results than the ILWOA algorithm in examples 7, 16, 17, 27, 28, 31, and 32. Also, the proposed algorithm gave a better result than the MSBPP algorithm in example 24. The proposed algorithm achieved the best-known results in 31 of 33 samples. In 2

samples (27, 28) it approached the best-known results with a difference of 1 box. Table 5 shows the hard class of the Scholl dataset. The proposed algorithm gave equal or better results than competing algorithms in all examples. The best-known results are obtained in samples 1, 2, 5, 6, 7, 9, and 10. In examples 3 and 4, the best-known results are approached with a difference of 1 box, and in example number 8, it is approached with 2 boxes. Table 6 shows the minimum fitness values (Equation 15) and average fitness values (Equation 18) obtained from previous studies and this study for three classes of the Scholl dataset. Since minimum fitness values and average fitness values are not given in the study using the ILWOA algorithm, they are not included in table 6. The sample number is given in the first column of Table 6 and the sample name is given in the second column. In the third, fifth, and seventh columns, the minimum fitness values obtained from the studies are given, average fitness values are given in the fourth, sixth, and eighth columns.

Table 6. Scholl dataset fitness value Scholl Easy Class ins_no

Ihfpga

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

Ihfpga

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

its competitors. Competitive studies obtained better results in 4 samples (32, 34, 35, 41). The fact that the studies selected for comparison use different samples of the dataset makes it difficult to compare the information given in Table 6. Therefore, the proposed algorithm has been compared separately with each competing algorithm in Figure 4, Figure 5, Figure 6, Figure 7, Figure 8, Figure 9. Minimum and average fitness values are given in Figure 4 and Figure 5 for the easy class of the Scholl dataset, in Figure 6 and Figure 7 for the middle class, and in Figure 8 and Figure 9 for the hard class.

(18) where fi is the minimum fitness value obtained in the ith run of the proposed algorithm. When Table 6 is examined, the proposed algorithm achieved better results than its competitors in 44 of 50 samples in terms of minimum fitness value metric. In 6 samples (5, 18, 27, 32, 35, 41), competing algorithms achieved better results. In the average fitness value metric, the proposed algorithm achieved better results in 46 of 50 samples than

b) Figure 4. Scholl easy class minimum fitness value a) AFDO - IHFPGA b) MSBPP - IHFPGA.

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

b) Figure 5. Scholl easy class average fitness value a) AFDO - IHFPGA b) MSBPP - IHFPGA.

Other metrics used to compare the proposed algorithm with previous studies are minimum percentage performance (Equation 19) and average percentage performance (Equation 20). The minimum fitness value and the average fitness value are used in the calculation of these metrics. (19)

(20) where, Min.fAFDO,MSBPP,IHFPGA is the minimum fitness value and Avg.fAFDO,MSBPP,IHFPGA is the average fitness value of algorithms. This comparison shows the performance of the proposed algorithm against its competitors as a percentage. Percentage performance values are given in Figure

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

b) Figure 6. Scholl medium-class minimum fitness value a) AFDO - IHFPGA b) MSBPP - IHFPGA.

10 for the easy class of the Scholl dataset, in Figure 11 for the medium class, and in Figure 12 for the hard class. In Figure 10a, the proposed algorithm is compared with the AFDO algorithm. The proposed algorithm performed better than the AFDO algorithm in all examples in the minimum percentage performance and average percentage performance metric. In Figure 10b, the proposed algorithm is compared with the MSBPP algorithm. The proposed algorithm performed better in 10 out of 12 samples in the

minimum percentage performance metric, while MSBPP achieved better results in 2 samples (instance 5, 18). In the average percentage performance metric, the proposed algorithm performed better than the MSBPP algorithm in all samples. In Figure 11a, the proposed algorithm is compared with the AFDO algorithm for medium-class samples. While the proposed algorithm performed better in 8 out of 10 samples in the minimum percentage performance

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

b) Figure 7. Scholl medium-class average fitness value a) AFDO - IHFPGA b) MSBPP - IHFPGA

metric, the AFDO algorithm achieved better results in 2 samples (instance 35,41). In the average percentage performance metric, the proposed algorithm performed better in 7 out of 10 samples, while the AFDO algorithm achieved better results in 3 samples (instance 34, 35, 41). In Figure 11b, the proposed algorithm is compared with the MSBPP algorithm. While the proposed algorithm performed better in 9 out of 11 samples in the minimum percentage performance metric, the MSBPP algorithm achieved better results in 2 samples (instance 27, 32). In

the average performance metric, the proposed algorithm performed better in 10 of 11 samples, while the MSBPP algorithm achieved better results in 1 sample (instance 32). In Figure 12a, the proposed algorithm is compared with the AFDO algorithm for hard class examples. The proposed algorithm gave better results than the AFDO algorithm in all samples in the minimum percentage performance and average percentage performance metric. In Figure 12b, the proposed algorithm is compared with the

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

b) Figure 8. Scholl hard-class minimum fitness value a) AFDO - IHFPGA b) MSBPP - IHFPGA.

MSBPP algorithm. The proposed algorithm gave better results than the MSBPP algorithm in all samples in the minimum percent performance and average percent performance metric.

Conclusion

In this paper, the proposed IHFPGA algorithm is compared with the AFDO, MSBPP, and ILWOA algorithms for

the 1DBPP problem. For comparison, metrics including container number, minimum fitness value, average fitness value, minimum percentage performance, and average percentage performance values are used. In terms of the container number metric, the proposed algorithm has achieved equal or better results than competing algorithms in all tests. The proposed algorithm obtained the best-known results in 72 of 77 samples (93.5%) used for comparison. In the minimum fitness metric, the proposed

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

b) Figure 9. Scholl hard-class average fitness value a) AFDO - IHFPGA b) MSBPP - IHFPGA.

algorithm achieved more successful results than its competitors in 44 of the 50 samples (88%). In the average fitness metric, it achieved better results than its competitors in 46 of the 50 samples (92%). In the minimum percentage performance metric, it is compared with the AFDO algorithm in 30 samples, and it is more successful in 93.3% of the samples. In general, the proposed algorithm showed an average of 37.6% better performance than the AFDO algorithm. In the comparison made with the MSBPP

algorithm, 26 samples are used and the proposed algorithm is more successful in 84.6% of them. In general, the proposed algorithm outperformed the MSBPP algorithm by an average of 32.7%. In the average percentage performance metric, the proposed algorithm is compared with the AFDO algorithm in 30 samples and is more successful in 90% of the samples. In general, the proposed algorithm outperformed the AFDO algorithm by an average of 38.6%. In the comparison made with the MSBPP

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

b) Figure 10. Performance percentage of IHFPGA in terms of the fitness value (Scholl easy class) a) AFDO/IHFPGA b) MSBPP/IHFPGA.

algorithm, 26 samples are used and the proposed algorithm is more successful in 96.1% of the samples. In general, the proposed algorithm outperformed the MSBPP algorithm on average 42.3%. These data reveal the superiority of the proposed algorithm over the competing ones. Thanks to the elimination phase, the proposed algorithm achieves better results

on average fitness and average percentage performance parameters. This strategy ensures that candidate solutions are close to each other. Besides, the results of the algorithm are reproducible. The proposed algorithm will be compared with more algorithms in the future. It will also be applied to two-dimensional and three-dimensional BBP.

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

b) Figure 11. Performance percentage of IHFPGA in terms of the fitness value (Scholl medium class) a) AFDO/IHFPGA b) MSBPP/IHFPGA.

Data Availability Statement

The authors confirm that the data that supports the findings of this study are available within the article. Raw

data that support the finding of this study are available from the corresponding author, upon reasonable request.

Conflict Of Interest

The author declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Sigma J Eng Nat Sci, Vol. 41, No. 3, pp. 545−564, June, 2023

b) Figure 12. Performance percentage of IHFPGA in terms of the fitness value (Scholl hard class) a) AFDO/IHFPGA b) MSBPP/IHFPGA.

Ethics

There are no ethical issues with the publication of this manuscript.

Delorme M, Iori M, Martello S. Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur J Oper Res 2016;255:1−20. [CrossRef]

Share and Cite