A Q-learning-based algorithm for the 2D-rectangular packing problem | Soft Computing Skip to main content
Springer Nature Link
Log in

A Q-learning-based algorithm for the 2D-rectangular packing problem

  • Optimization
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

This paper presents a Q-learning-based algorithm for sequence and orientation optimization toward the 2D rectangular strip packing problem. The width-filled skyline is used to represent the interior packing state, and a constructive rectangular packing algorithm with the commonly adopted fitness evaluation for placement is designed. Then, the consecutive item packing is simulated as Markov Decision Process, where the state is defined as the set of already packed items, and the action is defined as the rectangle selected to be packed along with its orientation. We propose the reverse updating of Q-value in the paradigm of Q-learning and use the algorithm to optimize the sequence and orientation of the rectangles. The decreasing-size-choice mechanism in Q-learning is studied on randomly generated problems to optimize the setting of ε-greedy policy. We also test the Q-learning-based algorithm on the benchmark instances of C21, N13, N-series from NT, Cgcut and Beng. Compared with a few state-of-the-art algorithms, the computational results show that the proposed algorithm can produce good packing quality when adequate execution time allowed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availability

Enquiries about data availability should be directed to the authors.

References

  • Aşık ÖB, Özcan E (2009) Bidirectional best-fit heuristic for orthogonal rectangular strip packing. Ann Oper Res 172(1):405–427

    MathSciNet  MATH  Google Scholar 

  • Baker BS, Coffman EG Jr, Rivest RL (1980) Orthogonal packings in two dimensions. SIAM J Comput 9(4):846–855

    MathSciNet  MATH  Google Scholar 

  • Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur J Oper Res 290(2):405–421

    MathSciNet  MATH  Google Scholar 

  • Bengtsson BE (1982) Packing rectangular pieces—a heuristic approach. Comput J 25(3):353–357

    MathSciNet  Google Scholar 

  • Bennell JA, Oliveira JF (2008) The geometry of nesting problems: a tutorial. Eur J Oper Res 184(2):397–415

    MathSciNet  MATH  Google Scholar 

  • Bennell JA, Lee LS, Potts CN (2013) A genetic algorithm for two-dimensional bin packing with due dates. Int J Prod Econ 145(2):547–560

    Google Scholar 

  • Burke EK, Kendall G, Whitwell G (2004) A new placement heuristic for the orthogonal stock-cutting problem. Oper Res 52(4):655–671

    MATH  Google Scholar 

  • Burke EK, Kendall G, Whitwell G (2009) A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock-cutting problem. INFORMS J Comput 21(3):505–516

    MATH  Google Scholar 

  • Chazelle B (1983) The bottomn-left bin-packing heuristic: an efficient implementation. IEEE Trans Comput 32(8):697–709

    MATH  Google Scholar 

  • Chen M, Wu C, Tang X, Peng X, Zeng Z, Liu S (2019) An efficient deterministic heuristic algorithm for the rectangular packing problem. Comput Ind Eng 137:106097

    Google Scholar 

  • Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper Res 25(1):30–44

    MATH  Google Scholar 

  • Clautiaux F, Sadykov R, Vanderbeck F, Viaud Q (2018) Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem. Discret Optim 29:18–44

    MathSciNet  MATH  Google Scholar 

  • Dolatabadi M, Lodi A, Monaci M (2012) Exact algorithms for the two-dimensional guillotine knapsack. Comput Oper Res 39(1):48–53

    MathSciNet  MATH  Google Scholar 

  • Drugan MM (2019) Reinforcement learning versus evolutionary computation: a survey on hybrid algorithms. Swarm Evol Comput 44:228–246

    Google Scholar 

  • Duan, L., Hu, H., Qian, Y., Gong, Y., Zhang, X., Wei, J., & Xu, Y. (2019, May). A Multi-task Selected Learning Approach for Solving 3D Flexible Bin Packing Problem. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (pp 1386–1394).

  • Furini F, Malaguti E (2013) Models for the two-dimensional two-stage cutting stock problem with multiple stock size. Comput Oper Res 40(8):1953–1962

    MathSciNet  MATH  Google Scholar 

  • Gu S, Hao T, Yao H (2020) A pointer network based deep learning algorithm for unconstrained binary quadratic programming problem. Neurocomputing 390:1–11

    Google Scholar 

  • He K, Huang W, Jin Y (2012) An efficient deterministic heuristic for two-dimensional rectangular packing. Comput Oper Res 39(7):1355–1363

    MathSciNet  MATH  Google Scholar 

  • He K, Jin Y, Huang W (2013) Heuristics for two-dimensional strip packing problem with 90 rotations. Expert Syst Appl 40(14):5542–5550

    Google Scholar 

  • He K, Ji P, Li C (2015) Dynamic reduction heuristics for the rectangle packing area minimization problem. Eur J Oper Res 241(3):674–685

    MathSciNet  MATH  Google Scholar 

  • Hopper EBCH, Turton BC (2001) An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. Eur J Oper Res 128(1):34–57

    MATH  Google Scholar 

  • Hopper, E. (2000). Two-Dimensional packing utilising evolutionary algorithms and other meta-heuristic methods [Ph. D. Thesis]. Cardiff: Cardiff University.

  • Hottung A, Tanaka S, Tierney K (2020) Deep learning assisted heuristic tree search for the container pre-marshalling problem. Comput Oper Res 113:104781

    MATH  Google Scholar 

  • Hu R, Xu J, Chen B, Gong M, Zhang H, Huang H (2020) TAP-Net: transport-and-pack using reinforcement learning. ACM Transactions on Graphics (TOG) 39(6):1–15

    Google Scholar 

  • James JQ, Yu W, Gu J (2019) Online vehicle routing with neural combinatorial optimization and deep reinforcement learning. IEEE Trans Intell Transp Syst 20(10):3806–3817

    Google Scholar 

  • Jiang, Y., Cao, Z., & Zhang, J. (2021). Learning to Solve 3-D Bin Packing Problem via Deep Reinforcement Learning and Constraint Programming. IEEE transactions on cybernetics.

  • Kwon SJ, Joung S, Lee K (2019) Comparative analysis of pattern-based models for the two-dimensional two-stage guillotine cutting stock problem. Comput Oper Res 109:159–169

    MathSciNet  MATH  Google Scholar 

  • Leung SC, Zhang D (2011) A fast layer-based heuristic for non-guillotine strip packing. Expert Syst Appl 38(10):13032–13042

    Google Scholar 

  • Leung SC, Zhang D, Sim KM (2011) A two-stage intelligent search algorithm for the two-dimensional strip packing problem. Eur J Oper Res 215(1):57–69

    Google Scholar 

  • Leung SC, Zhang D, Zhou C, Wu T (2012) A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem. Comput Oper Res 39(1):64–73

    MATH  Google Scholar 

  • Mao F, Blanco E, Fu M, Jain R, Gupta A, Mancel S, Tian Y (2017, April). Small boxes big data: A deep learning approach to optimize variable sized bin packing. In 2017 IEEE Third International Conference on Big Data Computing Service and Applications (BigDataService) (pp. 80–89). IEEE

  • Özcan E, Kai Z, Drake JH (2013) Bidirectional best-fit heuristic considering compound placement for two dimensional orthogonal rectangular strip packing. Expert Syst Appl 40(10):4035–4043

    Google Scholar 

  • Queiroz TA, Miyazawa FK (2013) Two-dimensional strip packing problem with load balancing, load bearing and multi-drop constraints. Int J Prod Econ 145(2):511–530

    Google Scholar 

  • Silva E, Oliveira JF, Wäscher G (2014) 2DCPackGen: A problem generator for two-dimensional rectangular cutting and packing problems. Eur J Oper Res 237(3):846–856

    MathSciNet  MATH  Google Scholar 

  • Sutskever, I., Vinyals, O., & Le, Q. V. (2014). Sequence to sequence learning with neural networks. Advances in neural information processing systems, 27.

  • Velasco AS, Uchoa E (2019) Improved state space relaxation for constrained two-dimensional guillotine cutting problems. Eur J Oper Res 272(1):106–120

    MathSciNet  MATH  Google Scholar 

  • Verstichel J, De Causmaecker P, Berghe GV (2013) An improved bestg with neural networks l rectangular cutting and palem. Int Trans Opera Res 20(5):711–730

    MATH  Google Scholar 

  • Vinyals O, Bengio S, Kudlur M (2015a) Order matters: Sequence to sequence for sets. arXiv preprint arXiv:1511.06391

  • Vinyals O, Fortunato M, Jaitly N (2015b) Pointer networks. Advances in neural information processing systems, 28

  • Wang Y, Chen L (2015) Two-dimensional residual-space-maximized packing. Expert Syst Appl 42(7):3297–3305

    Google Scholar 

  • Wäscher G, Haußner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183(3):1109–1130

    MATH  Google Scholar 

  • Wei L, Oon WC, Zhu W, Lim A (2011) A skyline heuristic for the 2D rectangular packing and strip packing problems. Eur J Oper Res 215(2):337–346

    MathSciNet  MATH  Google Scholar 

  • Wei L, Hu Q, Leung SC, Zhang N (2017) An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation. Comput Oper Res 80:113–127

    MathSciNet  MATH  Google Scholar 

  • Wei L, Zhu W, Lim A, Liu Q, Chen X (2018) An adaptive selection approach for the 2D rectangle packing area minimization problem. Omega 80:22–30

    Google Scholar 

  • Wei L, Wang Y, Cheng H, Huang J (2019) An open space based heuristic for the 2D strip packing problem with unloading constraints. Appl Math Model 70:67–81

    MathSciNet  MATH  Google Scholar 

  • Wu L, Zhang L, Xiao WS, Liu Q, Mu C, Yang Y (2016) A novel heuristic algorithm for two-dimensional rectangle packing area minimization problem with central rectangle. Comput Ind Eng 102:208–218

    Google Scholar 

  • Wu L, Tian X, Zhang J, Liu Q, Xiao W, Yang Y (2017) An improved heuristic algorithm for 2D rectangle packing area minimization problems with central rectangles. Eng Appl Artif Intell 66:1–16

    Google Scholar 

  • Wuttke DA, Heese HS (2018) Two-dimensional cutting stock problem with sequence dependent setup times. Eur J Oper Res 265(1):303–315

    MathSciNet  MATH  Google Scholar 

  • Xin L, Song W, Cao Z, Zhang J (2020) Step-wise deep learning models for solving routing problems. IEEE Trans Industr Inf 17(7):4861–4871

    Google Scholar 

  • Yang S, Han S, Ye W (2013) A simple randomized algorithm for two-dimensional strip packing. Comput Oper Res 40(1):1–8

    MATH  Google Scholar 

Download references

Funding

This work was supported by the National Natural Science Foundation of China (Grant No. 51975231), the Foundational Research Funds for the Central Universities (Grant No. 2019kfyXKJC043) and Open fund of Hubei Key Laboratory of hydropower engineering construction and management (Grant No: 2020KSD15).

Author information

Authors and Affiliations

  1. School of Mechanical Science & Engineering, Huazhong University of Science and Technology, Wuhan, Hubei, China

    Xusheng Zhao, Yunqing Rao & Jie Fang

  2. College of Mechanical & Power Engineering, China Three Gorges University, Yichang, Hubei, China

    Ronghua Meng

Authors
  1. Xusheng Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yunqing Rao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ronghua Meng
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jie Fang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yunqing Rao.

Ethics declarations

Conflict of interest

No conflict of interest exits in the submission of this manuscript.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhao, X., Rao, Y., Meng, R. et al. A Q-learning-based algorithm for the 2D-rectangular packing problem. Soft Comput 27, 12057–12070 (2023). https://doi.org/10.1007/s00500-023-08381-9

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-023-08381-9

Keywords

Search

Navigation