The 1-D bin packing problem optimisation using bees algorithm

Natalia Hartono, Asrul Harun Ismail, Sultan Zeybek, Mario Caterino, Kaiwen Jiang, Murat Sahin, Christine Natalia

Abstract


The bin packing problem is a classic combinatorial optimisation problem that is widely used in various applications such as assembly line balancing, scheduling, and time-tabling. Metaheuristic algorithms can provide solutions to these problems faster than exact methods. Bees Algorithm, a metaheuristic algorithm inspired by the foraging activity of bees, is known for its performance in solving optimisation problems. To our best knowledge, this is the first use of the Bees Algorithm to solve a bin packing problem. In this paper, we use the basic Bees Algorithm to demonstrate near-optimal solutions and measure the accuracy of solutions to the one-dimensional bin packing problem. The algorithm procedure and parameter settings are set following the previous research. Benchmark datasets are used in the experiment, and accuracy is measured. The results indicate that the basic Bees Algorithm for bin packing problems and previous research on travelling salesman problems produce similar accuracy results.

Keywords


Bees Algorithm; Bin Packing; Optimisation

Full Text:

PDF

References


A. Ekici, “Bin packing problem with conflicts and item fragmentation,” Computers & Operations Research, vol. 126, p. 105113, 2021, doi:10.1016/j.cor.2020.105113.

J. Pereira, “Procedures for the bin packing problem with precedence constraints,” European Journal of Operational Research, vol. 250, no. 3, pp. 794–806, 2016, doi:10.1016/j.ejor.2015.10.048.

M. Abdel-Basset, G. Manogaran, L. Abdel-Fatah, and S. Mirjalili, “An improved nature inspired meta-heuristic algorithm for 1-D bin packing problems,” Personal and Ubiquitous Computing, vol. 22, no. 5, pp. 1117–1132, 2018, doi:10.1007/s00779-018-1132-7.

X. Schepler, A. Rossi, E. Gurevsky, and A. Dolgui, “Solving robust bin-packing problems with a branch-and-price approach,” European Journal of Operational Research, vol. 297, no. 3, pp. 831–843, 2022, doi:10.1016/j.ejor.2021.05.041.

P. Shaw, “A constraint for bin packing,” in International conference on principles and practice of constraint programming, 2004, pp. 648–662, doi:10.1007/978-3-540-30201-8_47.

R. Kramer, M. Dell’Amico, and M. Iori, “A batching-move iterated local search algorithm for the bin packing problem with generalised precedence constraints,” International Journal of Production Research, vol. 55, no. 21, pp. 6288–6304, 2017, doi:10.1080/00207543.2017.1341065.

E. G. Coffman, J. Csirik, G. Galambos, S. Martello, and D. Vigo, “Bin packing approximation algorithms: Survey and classification,” in Handbook of Combinatorial Optimization, vol. 1–5, 2013, pp. 455–531, doi: 10.1007/978-1-4419-7997-1_35.

E. Falkenauer, “A hybrid grouping genetic algorithm for bin packing,” Journal of heuristics, vol. 2, no. 1, pp. 5–30, 1996, doi: 10.1007/BF00226291.

A. Stawowy, “Evolutionary based heuristic for bin packing problem,” Computers & Industrial Engineering, vol. 55, no. 2, pp. 465–474, Sep. 2008, doi: 10.1016/j.cie.2008.01.007.

Q. Liu et al., “Algorithms for the variable-sized bin packing problem with time windows,” Computers & Industrial Engineering, vol. 155, p. 107175, May 2021, doi: 10.1016/j.cie.2021.107175.

F. Luo, I. D. Scherson, and J. Fuentes, “A novel genetic algorithm for bin packing problem in jmetal,” in 2017 IEEE International Conference on Cognitive Computing (ICCC), 2017, pp. 17–23.

C. Munien, S. Mahabeer, E. Dzitiro, S. Singh, S. Zungu, and A. E.-S. Ezugwu, “Metaheuristic Approaches for One-Dimensional Bin Packing Problem: A Comparative Performance Study,” IEEE Access, vol. 8, pp. 227438–227465, 2020, doi: 10.1109/ACCESS.2020.3046185.

D. T. Pham, A. Ghanbarzadeh, E. Koç, S. Otri, S. Rahim, and M. Zaidi, “- The Bees Algorithm — A Novel Tool for Complex Optimisation Problems,” , Ed.D. T. Pham, E. E. Eldukhri, and A. J. Soroka Oxford: Elsevier Science Ltd, 2006, pp. 454–459.

A.H. Ismail, “Enhancing the Bees Algorithm using the traplining metaphor,” Ph.D. dissertation, Dept. Mech. Eng., Univ. of Birmingham, Birmingham, WM, 2021.

S. Zeybek, D. T. Pham, E. Koç, and A. Seçer, “An Improved Bees Algorithm for Training Deep Recurrent Networks for Sentiment Classification,” Symmetry, vol. 13, no. 8, p. 1347, Aug. 2021, doi: 10.3390/sym13081347.

D.T. Pham, E. Koc, J. Lee, and J. Phrueksanant, “Using the bees algorithm to schedule jobs for a machine,” in Proceedings Eighth International Conference on Laser Metrology, CMM and Machine Tool Performance, LAMDAMAP, Euspen, UK, Cardiff, 2007, pp. 430–439.

A. H. Ismail, N. Hartono, S. Zeybek, and D. T. Pham, “Using the Bees Algorithm to solve combinatorial optimisation problems for TSPLIB,” IOP Conference Series: Materials Science and Engineering, vol. 847, no. 1, p. 12027, Apr. 2020, doi: 10.1088/1757-899X/847/1/012027.

S. Zeybek, A. H. Ismail, N. Hartono, M. Caterino, and K. Jiang, “An Improved Vantage Point Bees Algorithm to Solve Combinatorial Optimization Problems from TSPLIB,” Macromolecular Symposia, vol. 396, no. 1, p. 2000299, 2021, doi: https://doi.org/10.1002/masy.202000299.

M. ŞAHİN, “Improvement of the Bees Algorithm for Solving the Traveling Salesman Problems,” Bilişim Teknolojileri Dergisi, vol. 15, no. 1, pp. 65–74.

A. H. Ismail, N. Hartono, S. Zeybek, M. Caterino, and K. Jiang, “Combinatorial Bees Algorithm for Vehicle Routing Problem,” Macromolecular Symposia, vol. 396, no. 1, p. 2000284, 2021, doi: https://doi.org/10.1002/masy.202000284.

C. Natalia, V. Triyanti, G. Setiawan, and M. Haryanto, “Completion of Capacitated Vehicle Routing Problem (CVRP) and Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) Using Bee Algorithm Approach to Optimise Waste Picking Transportation Problem,” Journal of Modern Manufacturing Systems and Technology, vol. 5, no. 2, pp. 69–77, 2021.

J. Liu, Z. Zhou, D. T. Pham, W. Xu, C. Ji, and Q. Liu, “Robotic disassembly sequence planning using enhanced discrete bees algorithm in remanufacturing,” International Journal of Production Research, vol. 56, no. 9, pp. 3134–3151, May 2018, doi: 10.1080/00207543.2017.1412527.

B. Yuce, M. S. Packianather, E. Mastrocinque, D. T. Pham, and A. Lambiase, “Honey Bees Inspired Optimization Method: The Bees Algorithm,” Insects, vol. 4, no. 4, pp. 646–662, Nov. 2013, doi: 10.3390/insects4040646.

S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer implementations. John Wiley and Sons Ltd: Chichester, UK, 1990.

N. Hartono, A. H. Ismail, S. Zeybek, M. Caterino, K. Jiang, and M. Sahin, “Parameter Tuning for Combinatorial Bees Algorithm in Travelling Salesman Problems,” presented at the 13th ISIEM, Bandung, West Java, Indonesia, July 28th, 2021, Paper 22

J. E. Beasley, June 1990 to February 2018, ”OR-Library,” [Online]. Available: http://people.brunel.ac.uk/~mastjjb/jeb/info.html




DOI: http://dx.doi.org/10.36055/jiss.v7i2.14387

Refbacks

  • There are currently no refbacks.


  is supported by