Fast Non-dominated Sorting in Multi Objective Genetic Algorithm for Bin Packing Problem

https://doi.org/10.22146/ijccs.70677

Muhammad Bintang Bahy(1*), Aina Musdholifah(2)

(1) Undergraduate Program of Computer Science, FMIPA UGM, Yogyakarta
(2) Department of Computer Science and Electronics, FMIPA UGM, Yogyakarta
(*) Corresponding Author

Abstract


The bin packing problem is a problem where goods with different volumes and dimensions are put into a container so that the volume of goods inserted is maximized. The problem of multi-objective bin packing is a problem that is more commonly found in everyday life, because what is considered in packing is usually not only volume.

In this research, a multi-objective genetic algorithm is proposed to solve the multi-objective bin packing problem. The proposed genetic algorithm uses non-dominated sorting and crowding distance methods to get the best solution for each objective and to avoid bias. The algorithm is then tested with several test classes that represent different combinations of item and container sizes.

From the results of the tests carried out, it was found that the proposed algorithm can find several solutions which are the best candidate solutions for each objective. Also found how the correlation of each objective in the population.


Keywords


Genetic algorithm; bin packing problem; multi objective; multi solution; non-dominated sorting

Full Text:

PDF


References

R. E. Korf, “A new algorithm for optimal bin packing,” Proc. Natl. Conf. Artif. Intell., pp. 731–736, 2002.

S. Martello, D. Pisinger, and D. Vigo, “Universita degli Studi di Bologna The Three-Dimensional Bin Packing Problem The Three-Dimensional Bin Packing Problem,” Rev. Politécnica, vol. 29, 2010.

X. Feng, I. Moon, and J. Shin, “Hybrid genetic algorithms for the three-dimensional multiple container packing problem,” Flex. Serv. Manuf. J., vol. 27, no. 2–3, pp. 451–477, 2015, doi: 10.1007/s10696-013-9181-8.

Z. Jin, T. Ito, and K. Ohno, “The three-dimensional bin packing problem and its practical algorithm,” JSME International Journal, Series C: Mechanical Systems, Machine Elements and Manufacturing, vol. 46, no. 1. pp. 60–66, 2003, doi: 10.1299/jsmec.46.60.

P. A. Wibowo, “Algoritme Genetika Multi Objektif untuk Mengoptimalkan Penyusunan Barang dalam Kontainer,” Tesis, Univ. Gadjah Mada, 2017.

C. He, Y. B. Zhang, J. W. Wu, and C. Chang, “Research of three-dimensional container-packing problems based on discrete particle swarm optimization algorithm,” Proc. Int. Symp. Test Meas., vol. 2, pp. 425–428, 2009, doi: 10.1109/ICTM.2009.5413015.

J. N. Zheng, C. F. Chien, and M. Gen, “Multi-objective multi-population biased random-key genetic algorithm for the 3-D container loading problem,” Comput. Ind. Eng., vol. 89, pp. 80–87, Nov. 2015, doi: 10.1016/j.cie.2014.07.012.

D. S. Liu, K. C. Tan, S. Y. Huang, C. K. Goh, and W. K. Ho, “On solving multiobjective bin packing problems using evolutionary particle swarm optimization,” Eur. J. Oper. Res., vol. 190, no. 2, pp. 357–382, Oct. 2008, doi: 10.1016/j.ejor.2007.06.032.

J. Hasan, “Multi-objective 3D bin-packing problem,” 2019 8th Int. Conf. Model. Simul. Appl. Optim., pp. 1–5, 2019.

J. Kaabi, Y. Harrath, H. E. Bououdina, and A. T. Qasim, “Toward smart logistics: A new algorithm for a multi-objective 3D bin packing problem,” IET Conf. Publ., vol. 2018, no. CP747, pp. 4–8, 2018, doi: 10.1049/cp.2018.1384.

N. Srinivas and K. Deb, “Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms,” Evol. Comput., vol. 2, no. 3, pp. 221–248, 1994, doi: 10.1162/evco.1994.2.3.221.

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, 2002, doi: 10.1109/4235.996017.

K. Kang, I. Moon, and H. Wang, “A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem,” Appl. Math. Comput., vol. 219, no. 3, pp. 1287–1299, 2012, doi: 10.1016/j.amc.2012.07.036.



DOI: https://doi.org/10.22146/ijccs.70677

Article Metrics

Abstract views : 449 | views : 223

Refbacks

  • There are currently no refbacks.




Copyright (c) 2022 IJCCS (Indonesian Journal of Computing and Cybernetics Systems)

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.



Copyright of :
IJCCS (Indonesian Journal of Computing and Cybernetics Systems)
ISSN 1978-1520 (print); ISSN 2460-7258 (online)
is a scientific journal the results of Computing
and Cybernetics Systems
A publication of IndoCEISS.
Gedung S1 Ruang 416 FMIPA UGM, Sekip Utara, Yogyakarta 55281
Fax: +62274 555133
email:ijccs.mipa@ugm.ac.id | http://jurnal.ugm.ac.id/ijccs



View My Stats1
View My Stats2