Deep Study on the Application of Machine Learning in Bin Packing Problems

• Autores: Jessica González-San-Martín, Laura Cruz-Reyes , Bernabé Dorronsoro Díaz , Hector Joaquin Fraire Huacuja , Fausto Balderas-Jaramillo, Marcela Quiroz Castellanos, Nelson Rangel-Valdez
• Localización: Computación y Sistemas (CyS), ISSN 1405-5546, ISSN-e 2007-9737, Vol. 28, Nº. 3, 2024, págs. 1275-1290
• Idioma: inglés
• DOI: 10.13053/cys-28-3-5184
• Enlaces
  • Texto completo
• Resumen

  • Abstract: This paper conducts a comprehensive review of literature focusing on strategies applied in the realm of Machine Learning (ML) in a period from ten years ago to the present to address the Bin Packing Problem (BPP) and its various variants. The Bin Packing Problem, a renowned optimization challenge, involves efficiently allocating items of varying sizes into containers of fixed capacity to minimize the number of containers used. Despite the extensive body of research and the existence of heuristic algorithms, unresolved challenges persist in BPP's solution. This deep study systematically explores the landscape of ML applications, delving into innovative approaches and methodologies proposed for tackling BPP and its diverse extensions, including 2D-BPP, 3D-BPP, Multi-objective BPP, and dynamic variants. The review critically examines the performance and contributions of ML-based strategies, shedding light on their efficacy in optimizing the packing process. Key findings highlight the promising directions taken by ML in solving complex optimization problems, emphasizing its potential to enhance BPP solution methodologies. The synthesis of diverse ML strategies and their integration with traditional heuristics forms a central theme, showcasing the evolving landscape of research in this domain. Additionally, this review identifies gaps and future research directions, emphasizing the relevance and effectiveness of ML as a valuable tool for improving performance in resolving BPP and its related challenges. The insights derived from this study aim to guide researchers, practitioners, and decision-makers in understanding the current state of ML applications in the context of Bin Packing Problems and inspire further advancements in this field.

• Referencias bibliográficas
  • Falkenauer, E.. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics. 2. 5-30
  • Martello, S.,Toth, P.. (1990). Lower bounds and reduction procedures for the bin packing problem. Discrete applied mathematics. 28. 59-70
  • Rivera, G.,Cisneros, L.,Sánchez-Solís, P.,Rangel-Valdez, N.,Rodas-Osollo, J.. (2020). Genetic algorithm for scheduling optimization considering...
  • Gilmore, P. C.,Gomory, R. E.. (1965). Multistage cutting stock problems of two and more dimensions. Operations research. 13. 94-120
  • Lodi, A.,Martello, S.,Monaci, M.. (2002). Two-dimensional packing problems: A survey. European journal of operational research. 14. 241
  • Lodi, A.,Martello, S.,Monaci, M.,Vigo, M.. (2014). Two-dimensional bin packing problems. Paradigms of combinatorial optimization: Problems...
  • Martello, S.,Pisinger, D.,Vigo, D.. (2000). The three-dimensional bin packing problem. Operations research. 48. 256
  • Geiger, M. J.. (2008). Bin packing under multiple objectives heuristic approximation approach.
  • Coffman-Jr, E. G.,Garey, M. R.,Johnson, D. S.. (1983). Dynamic bin packing. SIAM Journal on Computing. 12. 227
  • Talbi, E. G.. (2021). Machine learning into metaheuristics: A survey and taxonomy. ACM Computing Surveys (CSUR). 54. 1-32
  • De-Almeida, R.,Steiner, M. T. A.. (2015). Resolution of 1-D bin packing problem using augmented neural networks and minimum bin slack. Latin...
  • Sim, K.,Hart, E.,Paechter, B.. (2015). A lifelong learning hyper-heuristic method for bin packing. Evolutionary computation. 23. 37-67
  • Laterre, A.,Fu, Y.,Jabri, M. K.,Cohen, A. S.,Kas, D.,Hajjar, K.,Beguir, K.. (2019). Ranked reward: enabling self-play reinforcement learning...
  • Kroes, M.,Petrica, L.,Cotofana, S.,Blott, M.. (2020). Evolutionary bin packing for memory-efficient dataflow inference acceleration on FPGA....
  • Hu, H.,Zhang, X.,Yan, X.,Wang, L.,Xu, Y.. (2017). Solving a new 3d bin packing problem with deep reinforcement learning method.
  • Mao, F.,Blanco, E.,Fu, M.,Jain, R.,Gupta, A.,Mancel, S.,Tian, Y.. (2017). Small boxes big data: A deep learning approach to optimize variable...
  • Nanda, S.,Hacker, T. J.. (2018). RACC: Resource-aware container consolidation using a deep learning approach. First Workshop on Machine Learning...
  • Li, F.,Hu, B.. (2019). DeepJS: Job scheduling based on deep reinforcement learning in cloud data center. 4th International Conference on...
  • Verma, R.,Singhal, A.,Khadilkar, H.,Basumatary, A.,Nayak, S.,Singh, H. V.,Sinha, R.. (2020). A generalized reinforcement learning algorithm...
  • Goyal, A.,Deng, J.. (2020). Packit: A virtual environment for geometric planning. 119. International Conference on Machine Learning.
  • Silva-Gálvez, A.,Orozco-Sanchez, J.,Lara-Cárdenas, E.,Ortiz-Bayliss, J. C.,Amaya, I.,Cruz-Duarte, J. M.,Terashima-Marín, H.. (2020). Discovering...
  • Zhao, H.,She, Q.,Zhu, C.,Yang, Y.,Xu, K.. (2021). Online 3D bin packing with constrained deep reinforcement learning. 35. AAAI Conference...
  • Yang, T.,Luo, F.,Fuentes, J.,Ding, W.,Gu, C.. (2021). A flexible reinforced bin packing framework with automatic slack selection. Mathematical...
  • Zhang, J.,Zi, B.,Ge, X.. (2021). Attend2pack: Bin packing through deep reinforcement learning with attention.
  • Jiang, Y.,Cao, Z.,Zhang, J.. (2021). Solving 3D bin packing problem via multimodal deep reinforcement learning. 3. 20th International Conference...
  • Murdivien, S. A.,Um, J.. (2023). BoxStacker: Deep reinforcement learning for 3D bin packing problem in virtual environment of logistics systems....
  • Fang, J.,Rao, Y.,Zhao, X.,Du, B.. (2023). A hybrid reinforcement learning algorithm for 2D irregular packing problems. Mathematics. 11. 327
  • Guerriero, F.,Saccomanno, F. P.. (2023). A machine learning approach for the bin packing problem. 1. IEEE 12th International Conference on...
  • Duan, L.,Hu, H.,Qian, Y.,Gong, Y.,Zhang, X.,Xu, Y.,Wei, J.. (2018). A multi-task selected learning approach for solving 3D flexible bin packing...
  • Mohiuddin, I.,Almogren, A.,Al Qurishi, M.,Hassan, M. M.,Al-Rassan, I.,Fortino, G.. (2019). Secure distributed adaptive bin packing algorithm...
  • Sim, K.,Hart, E.,Paechter, B.. (2013). Learning to solve bin packing problems with an immune inspired hyper-heuristic. 856
  • Sim, K.,Hart, E.. (2013). Generating single and multiple cooperative heuristics for the one-dimensional bin packing problem using a single...
  • Scholl, A.,Klein, R.,Jürgens, C.. (1997). Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers...
  • Falkenauer, E.. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics. 2. 5-30
  • Ha, C. T.,Nguyen, T. T.,Bui, L. T.,Wang, R.. (2017). An online packing heuristic for the three-dimensional container loading problem in dynamic...