Learning to solve 3-D bin packing problem via deep reinforcement learning and constraint programming

Publication Type

Journal Article

Publication Date

5-2023

Abstract

Recently, there is a growing attention on applying deep reinforcement learning (DRL) to solve the 3-D bin packing problem (3-D BPP). However, due to the relatively less informative yet computationally heavy encoder, and considerably large action space inherent to the 3-D BPP, existing DRL methods are only able to handle up to 50 boxes. In this article, we propose to alleviate this issue via a DRL agent, which sequentially addresses three subtasks of sequence, orientation, and position, respectively. Specifically, we exploit a multimodal encoder, where a sparse attention subencoder embeds the box state to mitigate the computation while learning the packing policy, and a convolutional neural network subencoder embeds the view state to produce auxiliary spatial representation. We also leverage an action representation learning in the decoder to cope with the large action space of the position subtask. Besides, we integrate the proposed DRL agent into constraint programming (CP) to further improve the solution quality iteratively by exploiting the powerful search framework in CP. The experiments show that both the sole DRL and hybrid methods enable the agent to solve large-scale instances of 120 boxes or more. Moreover, they both could deliver superior performance against the baselines on instances of various scales.

Keywords

Bin packing problem (BPP), constraint programming (CP), deep reinforcement learning (DRL), multi-task learning

Discipline

Programming Languages and Compilers

Research Areas

Intelligent Systems and Optimization

Publication

IEEE Transactions on Cybernetics

Volume

53

Issue

5

First Page

2864

Last Page

2875

ISSN

2168-2267

Identifier

10.1109/TCYB.2021.3121542

Publisher

Institute of Electrical and Electronics Engineers

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TCYB.2021.3121542

This document is currently not available here.

Share

COinS