Learning to Solve 3-D Bin Packing Problem via Deep Reinforcement Learning and Constraint Programming.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• The 3-D bin packing problem (3-D BPP) is a complex combinatorial optimization challenge.
• Existing deep reinforcement learning (DRL) methods struggle with large-scale 3-D BPP due to computationally intensive encoders and vast action spaces, limiting them to around 50 boxes.

Purpose of the Study:

• To develop an advanced DRL agent capable of efficiently solving large-scale 3-D bin packing problems.
• To enhance DRL performance by addressing limitations in state representation and action space complexity.

Main Methods:

• A multimodal encoder combining sparse attention for box states and CNNs for view states to improve computational efficiency and spatial representation.
• An action representation learning technique in the decoder to manage the large action space inherent in the position subtask.
• Integration of the DRL agent with constraint programming (CP) to iteratively refine solutions using CP's search capabilities.

Main Results:

• The proposed DRL agent successfully solves large-scale 3-D BPP instances with 120 or more boxes.
• Both the standalone DRL approach and the hybrid DRL-CP method demonstrate superior performance compared to baseline methods across various instance sizes.
• The multimodal encoder and action representation learning effectively mitigate computational load and action space complexity.

Conclusions:

• The developed DRL agent offers a significant advancement in solving the 3-D bin packing problem, overcoming previous scalability limitations.
• The hybrid DRL-CP approach provides a powerful framework for achieving high-quality solutions in complex packing scenarios.
• This research paves the way for more efficient and scalable DRL applications in logistics and operational research.