求解在线三维装箱问题的启发式深度强化学习算法

doi:10.3778/j.issn.1002-8331.2407-0069

摘要/Abstract

摘要： 货物装载是物流运输过程中的关键一环，属于NP-Hard问题。为解决智慧物流领域货物“即到即码”的实时性问题，提出了一种候选启发式与深度强化学习相结合的在线三维装箱算法。将在线三维装箱表述为带约束的马尔科夫决策过程，并考虑七种实际约束条件，在此基础上设计强化学习要素。设置货物码垛的候选缓存区，根据人工启发式生成有价值的先验知识，以此来初始化深度强化学习算法的训练过程，最终经过对决网络评估后输出最优动作。实验结果表明，算法空间利用率为85.3%，收敛速度提高25%，决策时间平均快15 ms，有效解决了面对大规模动作空间增长导致的智能体初期探索困难的问题，提高了算法的效率和实用性，更适用于实际在线装箱场景。

关键词: NP-Hard问题, 在线三维装箱, 候选启发式, 深度强化学习, 马尔可夫决策

Abstract: Cargo loading is a key part of the logistics transportation process, which belongs to the NP-Hard problem. In order to solve the real-time problem of “real-time palletizing” in the field of intelligent logistics, a candidate heuristic deep reinforcement learning algorithm for online 3D case loading is proposed. The palletizing process of online 3D bin packing is expressed as a Markov decision process, and the reinforcement learning elements are designed to satisfy seven practical constraints. A candidate cache is set on the basis of the deep reinforcement learning algorithm. Candidate solutions are generated according to the heuristic experience, from which the algorithm filters the optimal solutions for training, and finally outputs the optimal action after evaluation by the dueling network. Experimental results show that the algorithm has a space utilization of 85.3%, a 25% improvement in convergence speed, and an average of 15 ms faster decision time, which effectively solves the problem of initial exploration difficulty of the intelligent body caused by facing the large-scale growth of the action space, and improves the efficiency and practicability of the algorithm, which is more suitable for the actual on-line crating scenarios.

Key words: NP-Hard problem, online 3D bin packing, candidate heuristic, deep reinforcement learning, Markov decision

张长勇, 姚凯超, 张宇浩. 求解在线三维装箱问题的启发式深度强化学习算法[J]. 计算机工程与应用, 2025, 61(17): 329-336.

ZHANG Changyong, YAO Kaichao, ZHANG Yuhao. Heuristic Deep Reinforcement Learning Algorithm for Solving Online 3D Bin Packing Problem[J]. Computer Engineering and Applications, 2025, 61(17): 329-336.

参考文献

[1] WR??BEL S. Constraint programming methods in three-dimensional container packing[J]. arXiv:2311.06314, 2023.
[2] FEKETE S P, SCHEPERS J, VEEN V D J C. An exact algorithm for higher-dimensional orthogonal packing[J]. Operations Research, 2007, 55(3): 569-587.
[3] DELL’AMICO M, FURINI F, IORI M. A branch-and-price algorithm for the temporal bin packing problem[J]. Computers & Operations Research, 2020, 114: 104825.
[4] HE K, HUANG W Q. An efficient placement heuristic for three-dimensional rectangular packing[J]. Computers & Operations Research, 2011, 38(1): 227-233.
[5] HE K, HUANG W Q. A caving degree based flake arrangement approach for the container loading problem[J]. Compu-ters & Industrial Engineering, 2010, 59(2): 344-351.
[6] KANG Z J, GUAN Y, WANG J K, et al. Research on genetic algorithm optimization with fusion tabu search strategy and its application in solving three-dimensional packing problems[J]. Symmetry, 2024, 16(4): 449.
[7] SANGCHOOLI A S, SAJADIFAR S M. A heuristic and GRASP algorithm for three-dimensional multiple bin-size bin packing problem based on the needs of a spare-part company[J]. International Journal of Services and Operations Management, 2021, 38(1): 73.
[8] ZHANG B, YAO Y, KAN H K, et al. A GAN-based genetic algorithm for solving the 3D bin packing problem[J]. Scientific Reports, 2024, 14(1): 7775.
[9] 刘胜, 沈大勇, 商秀芹, 等. 求解三维装箱问题的多层树搜索算法[J]. 自动化学报, 2020, 46(6): 1178-1187.
LIU S, SHEN D Y, SHANG X Q, et al. A multi-level tree search algorithm for three dimensional container loading problem[J]. Acta Automatica Sinica, 2020, 46(6): 1178-1187.
[10] ?AFAK ?, ERDO?AN G. A large neighbourhood search algorithm for solving container loading problems[J]. Computers & Operations Research, 2023, 154: 106199.
[11] SILVER D, SCHRITTWIESER J, SIMONYAN K, et al. Mastering the game of go without human knowledge[J]. Nature, 2017, 550(7676): 354-359.
[12] MNIH V, KAVUKCUOGLU K, SILVER D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(7540): 529-533.
[13] 李凯文, 张涛, 王锐, 等. 基于深度强化学习的组合优化研究进展[J]. 自动化学报, 2021, 47(11): 2521-2537.
LI K W, ZHANG T, WANG R, et al. Research reviews of combinatorial optimization methods based on deep reinforcement learning[J]. Acta Automatica Sinica, 2021, 47(11): 2521-2537.
[14] JIA J, SHANG H L, CHEN X. Robot online 3D Bin packing strategy based on deep reinforcement learning and 3D vision[C]//Proceedings of the IEEE International Conference on Networking, Sensing and Control. Piscataway: IEEE, 2022: 1-6.
[15] ZHAO H, SHE Q J, ZHU C Y, et al. Online 3D bin packing with constrained deep reinforcement learning[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2021: 741-749.
[16] ZHAO H, YU Y, XU K. Learning efficient online 3D bin packing on packing configuration trees[C]//Proceedings of the 10th International Conference on Learning Representations, 2022.
[17] YANG S, SONG S, CHU S L, et al. Heuristics integrated deep reinforcement learning for online 3D bin packing[J]. IEEE Transactions on Automation Science and Engineering, 2024, 21(1): 939-950.
[18] XIONG H, DING K, DING W, et al. Towards reliable robot packing system based on deep reinforcement learning[J]. Adva-nced Engineering Informatics, 2023, 57: 102028.
[19] ZHAO A H, LI T R, LIN L C. A dynamic multi-modal deep reinforcement learning framework for 3D bin packing problem[J]. Knowledge-Based Systems, 2024, 299: 111990.
[20] 张长勇, 姚凯超, 王彤. 基于无监督深度融合机制的货物在线装箱算法[J]. 包装工程, 2024, 45(11): 153-162.
ZHANG C Y, YAO K C, WANG T. Online cargo packing algorithm based on unsupervised deep fusion mechanism[J]. Packaging Engineering, 2024, 45(11): 153-162.
[21] ZHANG J W, SHUAI T P. Online three-dimensional bin pac-king: a DRL algorithm with the buffer zone[J]. Foundations of Computing and Decision Sciences, 2024, 49(1): 63-74.
[22] WEI C Y, LI Y J, OUYANG Y P, et al. Deep reinforcement learning with heuristic corrections for UGV navigation[J]. Journal of Intelligent & Robotic Systems, 2023, 109(1): 18.
[23] KALLESTAD J, HASIBI R, HEMMATI A, et al. A general deep reinforcement learning hyperheuristic framework for sol-ving combinatorial optimization problems[J]. European Journal of Operational Research, 2023, 309(1): 446-468.
[24] CHEN D, CHEN Z, HE Z, et al. Learning heuristics for weig-hted CSPs through deep reinforcement learning[J]. Applied Intelligence, 2023, 53(8): 8844-8863.