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


Gezici H., Livatyali H.

SIGMA JOURNAL OF ENGINEERING AND NATURAL SCIENCES, vol.41, no.3, pp.545-564, 2023 (ESCI) identifier

  • Publication Type: Article / Article
  • Volume: 41 Issue: 3
  • Publication Date: 2023
  • Doi Number: 10.14744/sigma.2023.00061
  • Journal Name: SIGMA JOURNAL OF ENGINEERING AND NATURAL SCIENCES
  • Journal Indexes: Emerging Sources Citation Index (ESCI), Scopus, Academic Search Premier, Directory of Open Access Journals
  • Page Numbers: pp.545-564
  • Yıldız Technical University Affiliated: No

Abstract

The bin packing problem (BPP) is one of the most elaborated combinatorial optimization problems, yet there is still a need and room for improvement. An improved flower pollination algorithm (FPA) is proposed for the solution of one-dimensional BPP (1DBPP). To increase efficiency, global and local pollination procedures are modified and hybridized with the genetic algorithm (GA). An elimination strategy that increases the quality of the solution set in each iteration is also included and the proposed algorithm is tested on the Scholl dataset. It is compared with the adaptive fitness-dependent optimizer (AFDO), the improved Lévy-based whale optimization (ILWOA), and the modified squirrel search BPP (MSBPP) algorithms. The comparison is made in terms of metrics including the container number, minimum and average fitness values, and minimum and average percentage performances. In terms of the container number, the proposed algorithm yielded results equal to or better than competing algorithms. In terms of minimum fitness value, the proposed algorithm achieved 88% more successful results than its competitors. It achieved 92% more successful results in terms of average fitness value. Regarding minimum percentage performance, the proposed algorithm is more successful in 93.3% of the samples compared to AFDO. Compared to MSBPP, the proposed algorithm is 84.6% more successful. In terms of average percentage performance metric, the proposed algorithm has better results in 90% of the samples than AFDO; and compared to MSBPP, it is more successful in 96.1% of the samples. These results show the effectiveness of the proposed algorithm in solving the 1DBPP problem.