Hybrid flower pollination algorithm approach for the two-dimensional bin packing problem


Gezici H., Livatyali H.

JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY, vol.37, no.3, pp.1523-1534, 2022 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Volume: 37 Issue: 3
  • Publication Date: 2022
  • Doi Number: 10.17341/gazimmfd.764853
  • Journal Name: JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY
  • Journal Indexes: Science Citation Index Expanded, Scopus, Academic Search Premier, Art Source, Compendex, TR DİZİN (ULAKBİM)
  • Page Numbers: pp.1523-1534
  • Keywords: Bin packing problem, Flower pollination algorithm, Genetic algorithm, Combinatorial optimization, Hybridization, HEURISTIC ALGORITHMS, DIFFERENTIAL EVOLUTION, OPTIMIZATION, ROTATIONS, TYPOLOGY, GA

Abstract

Graphical/Tabular Abstract Meta-heuristic algorithms are frequently used in the solution of the two-dimensional bin packaging problem (2DBPP). This is because meta heuristic algorithms reach acceptable solutions in reasonable time in cases where there are many examples. In this study, a new hybrid meta heuristic algorithm is proposed for the solution of 2DBPP (2DHFPGA). The proposed algorithm was created by hybridizing the flower pollination algorithm (FPA) and genetic algorithm (GA). In 2DBPP, n small rectangular objects are placed inside larger rectangles (containers). The aim is to minimize the number of containers required for packaging all small objects. There are two rules for classifying 2DBPP. The first one is orientation and the second one is the cut type. This study focuses on the 2DBPPRF problem where there is no guillotine cut and objects can be rotated. Table A. Comparison of the results. Purpose: Minimum container numbers have not been reached in 2DBPP with meta heuristic optimization algorithms yet. The aim of this study is to get better results than the previous studies. Theory and Methods: The global search procedure of the proposed algorithm is carried out with FPA. The local search operator in the structure of FPA has been modified. The variable in this operator representing the local pollination distance was removed from the equation and the Levy distribution was added instead. With this change, FPA's global search capability has been increased. The local search procedure of the proposed algorithm is carried out with 4 different mutation operators of GA. These are swap, scramble, reversion and displacement. Results: The proposed algorithm has been tested with a data set with 10 classes and 50 subgroups. The obtained results were compared with 6 meta-heuristic algorithms which have previously published. Average container numbers of each class and subgroup were used as comparison parameters. In addition, Friedman test was performed to compare the performances of the algorithms. In the first column of Table A, shows the names of the algorithms. the number of classes and subgroups that they have successfully solved can be seen in the second and third columns and the average rank values obtained from the Friedman test are given in the last column. Conclusion: 2DFPGA has been the most successful algorithm by achieving the best results in the 6 classes of the data set. According to these data, the proposed algorithm achieved the best results in 60% of the data set classes and achieved 3 times more success than its closest competitor. In addition, the proposed algorithm was the most successful algorithm in 33 of the 50 subgroups by achieving the best results. Considering these data, the proposed algorithm successfully resolved 66% of the subgroups and achieved 12% more successful results than its closest competitor. According to the average rank values obtained from the Friedman test, the proposed algorithm was the most successful algorithm with 2.6 scores.