Reinforcement Learning Applied to 2D Strip Packing Problem: A Q-Learning Approach

Authors

https://doi.org/10.48313/scodm.vi.64

Abstract

This study addresses the two-dimensional rectangular strip packing problem (2D-SPP), a significant combinatorial optimization challenge. A novel approach combining Q-learning with the Bottom-Left-Fill (BLF) algorithm, referred to as QL-BLF, is proposed. Our method aims to enhance packing efficiency by optimizing the sequence and orientation of items. We evaluated the performance of the QL-BLF algorithm against the traditional BLF algorithm using two datasets of 10 and 15 items, each tested across 10 distinct series to ensure comprehensive and reliable results. The computational experiments demonstrated that the QL-BLF algorithm consistently outperformed the BLF algorithm by significantly reducing the strip height and minimizing free space. These findings underscore the effectiveness of reinforcement learning in enhancing traditional heuristic methods for solving complex packing problems.

Keywords:

Combinatorial optimization, Reinforcement learning, 2D strip packing problem, Q-learning, Bottom-left-fill

References

  1. [1] Fang, J., Rao, Y., Zhao, X., & Du, B. (2023). A hybrid reinforcement learning algorithm for 2D irregular packing problems. Mathematics, 11(2), 327. https://www.mdpi.com/2227-7390/11/2/327
  2. [2] Gilmore, P. C., & Gomory, R. E. (1965). Multistage cutting stock problems of two and more dimensions. Operations Research, 13(1), 94–120. https://doi.org/10.1287/opre.13.1.94
  3. [3] Hopper, E., & Turton, B. C. H. (2001). A review of the application of meta-heuristic algorithms to 2D strip packing problems. Artificial Intelligence Review, 16(4), 257–300. https://doi.org/10.1023/A:1012590107280
  4. [4] Tian, R., Kang, C., Bi, J., Ma, Z., Liu, Y., Yang, S., & Li, F. (2023). Learning to multi-vehicle cooperative bin packing problem via sequence-to-sequence policy network with deep reinforcement learning model. Computers & Industrial Engineering, 177, 108998. https://doi.org/10.1016/j.cie.2023.108998
  5. [5] Bezerra, V. M. R., Leao, A. A. S., Oliveira, J. F., & Santos, M. O. (2020). Models for the two-dimensional level strip packing problem-a review and a computational evaluation. Journal of the Operational Research Society, 71(4), 606–627. https://doi.org/10.1080/01605682.2019.1578914
  6. [6] Zhang, H., Yao, S., Zhang, S., Leng, J., Wei, L., & Liu, Q. (2024). A block-based heuristic search algorithm for the two-dimensional guillotine strip packing problem. Engineering Applications of Artificial Intelligence, 134, 108624. https://doi.org/10.1016/j.engappai.2024.108624
  7. [7] Lastra-Díaz, J. J., & Ortuño, M. T. (2024). Mixed-integer programming models for irregular strip packing based on vertical slices and feasibility cuts. European Journal of Operational Research, 313(1), 69-91. https://doi.org/10.1016/j.ejor.2023.08.009
  8. [8] Cid-Garcia, N. M., & Rios-Solis, Y. A. (2021). Exact solutions for the 2d-strip packing problem using the positions-and-covering methodology. Plos One, 16(1), e0245267. https://doi.org/10.1371/journal.pone.0245267
  9. [9] Burke, E. K., Hyde, M., Kendall, G., & Woodward, J. (2010). A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics. IEEE Transactions on Evolutionary Computation, 14(6), 942–958. https://www.graham-kendall.com/papers/bhkw2010b.pdf
  10. [10] Rakotonirainy, R. G., & van Vuuren, J. H. (2020). Improved metaheuristics for the two-dimensional strip packing problem. Applied Soft Computing, 92, 106268. https://doi.org/10.1016/j.asoc.2020.106268
  11. [11] Bengio, Y., Lodi, A., & Prouvost, A. (2021). Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2), 405–421. https://doi.org/10.1016/j.ejor.2020.07.063
  12. [12] Júnior, A. N., Silva, E., Gomes, A. M., Soares, C., & Oliveira, J. F. (2019). Data mining based framework to assess solution quality for the rectangular 2D strip-packing problem. Expert Systems With Applications, 118, 365–380. https://doi.org/10.1016/j.eswa.2018.10.006
  13. [13] Guerriero, F., & Saccomanno, F. P. (2023). A machine learning approach for the bin packing problem. 2023 IEEE 12th International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS) (Vol. 1, pp. 436-441). IEEE. https://doi.org/10.1109/IDAACS58523.2023.10348703
  14. [14] Zhu, K., Ji, N., & Li, X. D. (2020). Hybrid heuristic algorithm based on improved rules & reinforcement learning for 2d strip packing problem. IEEE Access, 8, 226784–226796. https://doi.org/10.1109/ACCESS.2020.3045905
  15. [15] Oliveira, J. F., Neuenfeldt, A., Silva, E., & Carravilla, M. A. (2016). A survey on heuristics for the two-dimensional rectangular strip packing problem. Pesquisa Operacional, 36(2), 197–226. https://doi.org/10.1590/0101-7438.2016.036.02.0197
  16. [16] Ernst, D., & Louette, A. (2024). Introduction to reinforcement learning. Feuerriegel, S., Hartmann, J., Janiesch, C., and Zschech, P, 111-126. https://damien-ernst.be/wp-content/uploads/2026/02/introduction_to_reinforcement_learning.pdf

Downloads

Published

2026-11-13

Issue

Vol. 3 No. 4 (2026): Supply Chain and Operations Decision Making

Section

Articles

License

Copyright (c) 2024 Supply Chain and Operations Decision Making

Creative Commons License

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

How to Cite

Shabani , S. ., & Husseinzadeh Kashan , A. . (2026). Reinforcement Learning Applied to 2D Strip Packing Problem: A Q-Learning Approach. Supply Chain and Operations Decision Making, 3(4), 267-276. https://doi.org/10.48313/scodm.vi.64

Similar Articles

1-10 of 36

You may also start an advanced similarity search for this article.