Online Three-Dimensional Bin Packing: A DRL Algorithm with the Buffer Zone

• Autorzy: Zhang Jiawei , Shuai Tianping

Identyfikatory

DOI

10.2478/fcds-2024-0005

• Języki publikacji: EN

Abstrakty

EN

The online 3D bin packing problem(3D-BPP) is widely used in the logistics industry and is of great practical significance for promoting the intelligent transformation of the industry. The heuristic algorithm relies too much on manual experience to formulate more perfect packing rules. In recent years, many scholars solve 3D-BPP via deep reinforcement learning(DRL) algorithms. However, they ignore many skills used in manual packing, one of the most important skill is workers put the item aside if the item is packed improperly. Inspired by this skill, we propose a DRL algorithm with a buffer zone. Firstly, we define the wasted space and the buffer zone. And then, we integrate them into the DRL algorithm framework. Importantly, we compare the bin utilization with different thresholds of wasted space and different buffer zone sizes. Experimental results show that our algorithm outperforms existing heuristic algorithms and DRL algorithms.

Słowa kluczowe

EN

3D bin packing; buffer zone; wasted space; actor-critic

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2024
• Tom: Vol. 49, No. 1
• Strony: 63--74
• Opis fizyczny: Bibliogr. 26 poz., rys., tab.

Twórcy

autor

Zhang Jiawei

• School of Science Beijing University of Posts and Telecommunications, Beijing, China

autor

Shuai Tianping

• School of Science Beijing University of Posts and Telecommunications, Beijing, China

Bibliografia

• [1] Alvim A. C. F., Ribeiro C. C., Glover F., et al. A hybrid improvement heuristic for the one-dimensional bin packing problem Journal of Heuristics, 10, 2004, 205-229.
• [2] Baker B. S., Coffman E. G. A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing SIAM Journal on Algebraic Discrete Methods, 2, 2, 1981, 147-152.
• [3] Bortfeldt A., Gehring H. A hybrid genetic algorithm for the container loading problem European Journal of Operational Research, 131, 1, 2001, 143-161.
• [4] Cappart Q., Moisan T., Rousseau L. M., et al. Combining reinforcement learning and constraint programming for combinatorial optimization Proceedings of the AAAI Conference on Artificial Intelligence, 35, 5, 2021, 3677-3687.
• [5] Galambos G. A new heuristic for the classical bin-packing problem Univ. Augsburg, Inst. für Mathematik, 1985.
• [6] Galambos G., Woeginger G. J. Repacking helps in bounded space on-line bind-packing, 49, 4, 1993, 329-338.
• [7] Ha C. T., Nguyen T. T., Bui L. T., et al. An online packing heuristic for the three-dimensional container loading problem in dynamic environments and the Physical Internet In European Conference on the Applications of Evolutionary Computation, 2017, 140-155.
• [8] He C., Zhang Y. B., Wu J. W., et al. Research of three-dimensional container-packing problems based on discrete particle swarm optimization algorithm 2009 International Conference on Test and Measurement, 2, 2009, 425-428.
• [9] Hu H., Zhang X., Yan X., et al. Solving a new 3d bin packing problem with deep reinforcement learning method arXiv preprint arXiv:1708.05930, 2017.
• [10] Jiang Y., Cao Z., Zhang J. Solving 3D bin packing problem via multimodal deep reinforcement learning Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, 2021, 1548-1550.
• [11] Kang K., Moon I., Wang H. A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem Applied Mathematics and Computation, 219, 3, 2012, 1287-1299.
• [12] Karabulut K., İnceoğlu M. M. A hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method International Conference on Advances in Information Systems, 2005, 441-450.
• [13] Kundu O., Dutta S., Kumar S. Deep-pack: A vision-based 2d online bin packing algorithm with deep reinforcement learning 2019 28th IEEE International Conference on Robot and Human Interactive Communication (RO-MAN), 2019, 1-7.
• [14] Labbé M., Laporte G., Martello S. Upper bounds and algorithms for the maximum cardinality bin packing problem European Journal of Operational Research, 149, 3, 2003, 490-498.
• [15] Lodi A., Martello S., Vigo D. Approximation algorithms for the oriented two-dimensional bin packing problem European Journal of Operational Research, 112, 1, 1999, 158-166.
• [16] Lodi A., Martello S., Vigo D. Heuristic algorithms for the three-dimensional bin packing problem European Journal of Operational Research, 141, 2, 2002, 410-420.
• [17] Martello S., Pisinger D., Vigo D. The three-dimensional bin packing problem Operations research, 48, 2, 2000, 256-267.
• [18] Mnih V., Kavukcuoglu K., Silver D., et al. Human-level control through deep reinforcement learning Nature, 518, 7540, 2015, 529-533.
• [19] Puche A. V., Lee S. Online 3D Bin Packing Reinforcement Learning Solution with Buffer 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2022, 8902-8909.
• [20] Que Q., Yang F., Zhang D. Solving 3D packing problem using Transformer network and reinforcement learning Expert Systems with Applications, 214, 2023, 119-153.
• [21] Scholl A., Klein R., Jürgens C. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem Computers Operations Research, 24, 7, 1997, 627-645.
• [22] Song S., Yang S., Song R., et al. Towards Online 3D Bin Packing: Learning Synergies between Packing and Unpacking via DRL Conference on Robot Learning, 2023, 1136-1145.
• [23] Wang H., Chen Y. A hybrid genetic algorithm for 3D bin packing problems 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 2010, 703-707.
• [24] Wei L., Oon W. C., Zhu W., et al. Andrew Lim, A skyline heuristic for the 2D rectangular packing and strip packing problems European Journal of Operational Research, 215, 2, 2011, 337-346.
• [25] Zhao H., She Q., Zhu C., et al. Online 3D BinPacking with Constrained Deep Reinforcement Learning Proceedings of the AAAI Conference on Artificial Intelligence, 35, 1, 2021, 741-749.
• [26] Zheng F. F., Luo L., Zhang E. NF-based algorithms for online bin packing with buffer and bounded item size Journal of Combinatorial Optimization, 30, 2015, 30: 360-369.