Solving Offline 3D Bin Packing Problem with Large-sized Bin via Two-stage Deep Reinforcement Learning
Authors: 
Hao Yin, Fan Chen, Hongjie HeAuthors Info & Claims
Pages 2576 - 2578
Abstract
Existing Deep Reinforcement Learning (DRL) algorithms address the 3D Bin Packing Problem (3D-BPP) by decomposing the packing action into three sub-stages. However, this three-stage scheme makes it necessary for information to be passed between sub-networks, which may increase the computational cost of training and inference. This paper proposes a two-stage DRL algorithm, combining index and orientation into a single sub-stage to simplify learning. Additionally, a Bidirectional Cooperative Packing (BCP) method is introduced to compress the action space during position selection while retaining exploration capability. The experimental results show that the two-stage DRL algorithm, which incorporates BCP, achieves 0.3%-1.7% improvement in space utilization compared to the currently best-performing algorithm.
References
[1]
Andreas Bortfeldt and Hermann Gehring. 1998. Applying Tabu Search to Container Loading Problems. In Operations Research Proceedings 1997. Springer-Verlag, 533--538.
[2]
Andreas Bortfeldt and Gerhard W"ascher. 2013. Constraints in container loading - A state-of-the-art review. European Journal of Operational Research, Vol. 229, 1 (2013), 1--20.
[3]
Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei. 2008. Extreme Point-Based Heuristics for Three-Dimensional Bin Packing. Informs Journal on Computing, Vol. 20, 3 (2008), 368--384.
[4]
Lu Duan, Haoyuan Hu, Yu Qian, Yu Gong, Xiaodong Zhang, Jiangwen Wei, and Yinghui Xu. 2019. 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. 1386--1394.
[5]
Emanuel Falkenauer. 1996. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, Vol. 2 (1996), 5--30.
[6]
M Zahid Gurbuz, Selim Akyokus, Ibrahim Emiroglu, and Aysun Guran. 2009. An Efficient Algorithm for 3D Rectangular Box Packing, 2009. Applied Automatic Systems: Proceedings of Selected AAS (2009), 131--134.
[7]
Chi Trung Ha, Trung Thanh Nguyen, Lam Thu Bui, and Ran Wang. 2017. An Online Packing Heuristic for the Three-Dimensional Container Loading Problem in Dynamic Environments and the Physical Internet. In Applications of Evolutionary Computation. Springer International Publishing, 140--155.
[8]
Haoyuan Hu, Xiaodong Zhang, Xiaowei Yan, Longfei Wang, and Yinghui Xu. 2017. Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method. arxiv: 1708.05930 [cs.AI]
[9]
Jinshan Jiang and Lingzhi Cao. 2012. A hybrid simulated annealing algorithm for three-dimensional multi-bin packing problems. In 2012 international conference on systems and informatics (ICSAI2012). IEEE, 1078--1082.
[10]
Yuan Jiang, Zhiguang Cao, and Jie Zhang. 2023. Learning to Solve 3-D Bin Packing Problem via Deep Reinforcement Learning and Constraint Programming. IEEE Transactions on Cybernetics, Vol. 53, 5 (2023), 2864--2875. https://doi.org/10.1109/TCYB.2021.3121542
[11]
Korhan Karabulut and Mustafa Murat. Inceoug lu. 2004. A Hybrid Genetic Algorithm for Packing in 3d with Deepest Bottom Left with Fill Method. In Proceedings of the Third International Conference on Advances in Information Systems. Springer-Verlag, 441--450.
[12]
Alexandre Laterre, Yunguan Fu, Mohamed Khalil Jabri, Alain-Sam Cohen, David Kas, Karl Hajjar, Torbjorn S. Dahl, Amine Kerkeni, and Karim Beguir. 2018. Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization. arxiv: 1807.01672 [cs.LG]
[13]
Dongda Li, Changwei Ren, Zhaoquan Gu, Yuexuan Wang, and Francis Lau. 2020. Solving Packing Problems by Conditional Query Learning. https://openreview.net/forum?id=BkgTwRNtPB
[14]
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. 2021. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, Vol. 134 (2021), 105400.
[15]
Quanqing Que, Fang Yang, and Defu Zhang. 2023. Solving 3D packing problem using Transformer network and reinforcement learning. Expert Systems with Applications, Vol. 214 (2023), 119153. https://doi.org/10.1016/j.eswa.2022.119153
[16]
Liu Sheng, Shang Xiuqin, Cheng Changjian, Zhao Hongxia, Shen Dayong, and Wang Feiyue. 2017. Heuristic algorithm for the container loading problem with multiple constraints. Computers & Industrial Engineering, Vol. 108 (2017), 149--164.
[17]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 5998--6008.
[18]
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer Networks. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2692--2700.
[19]
Yong Wu, Wenkai Li, Mark Goh, and Robert De Souza. 2010. Three-dimensional bin packing problem with variable bin height. European Journal of Operational Research, Vol. 202, 2 (2010), 347--355.
[20]
Jingwei Zhang, Bin Zi, and Xiaoyu Ge. 2021. Attend2Pack: Bin Packing through Deep Reinforcement Learning with Attention. arxiv: 2107.04333 [cs.LG]
[21]
Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, and Kai Xu. 2021. Online 3D Bin Packing with Constrained Deep Reinforcement Learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 741--749. https://doi.org/10.1609/aaai.v35i1.16155
Index Terms
- Solving Offline 3D Bin Packing Problem with Large-sized Bin via Two-stage Deep Reinforcement Learning
Recommendations
Solving 3D Bin Packing Problem via Multimodal Deep Reinforcement Learning
AAMAS '21: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent SystemsRecently, there is growing attention on applying deep reinforcement learning (DRL) to solve the 3D bin packing problem (3D BPP), given its favorable generalization and independence of ground-truth label. However, due to the relatively less informative ...
Improved lower bounds for the online bin packing problem with cardinality constraints
The bin packing problem has been extensively studied and numerous variants have been considered. The $$k$$ k - item bin packing problem is one of the variants introduced by Krause et al. (J ACM 22:522---550, 1975 ). In addition to the formulation of the ...
A new variable-sized bin packing problem
The problem of BLASTing a genome against a database of DNA sequences to identify potential relationships with other genomes can be divided into subproblems quite naturally. We consider a setting where the problem is distributed to PCs having idle time. ...
Comments
Information & Contributors
Information
Published In
May 2024
2898 pages
ISBN:9798400704864
- General Chairs:
- Mehdi Dastani,
- Jaime Simão Sichman,
- Program Chairs:
- Natasha Alechina,
- Virginia Dignum
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 06 May 2024
Check for updates
Author Tags
Qualifiers
- Extended-abstract
Conference
AAMAS '23
Sponsor:
AAMAS '23: International Conference on Autonomous Agents and Multiagent Systems
May 6 - 10, 2024
Auckland, New Zealand
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 33Total Downloads
- Downloads (Last 12 months)33
- Downloads (Last 6 weeks)5
Reflects downloads up to 30 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in