A deep reinforcement learning algorithm for the rectangular strip packing problem.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• Rectangular strip packing is an NP-hard problem, often solved with heuristic algorithms that have limitations.
• Classical methods require manual design, leading to poor generalization and efficiency.

Purpose of the Study:

• To develop a novel deep reinforcement learning algorithm for solving the rectangular strip packing problem.
• To improve solution efficiency, generalization, and scale compared to traditional methods.

Main Methods:

• A deep reinforcement learning algorithm utilizing a pointer network (encoder-decoder) was designed.
• A model-free reinforcement learning approach trains network parameters to optimize packing sequences.
• The Maximum Rectangles Bottom-Left (Maxrects-BL) algorithm determines piece placement and calculates rewards.

Main Results:

• The proposed algorithm achieved superior or comparable results against classical heuristic algorithms.
• Experimental results demonstrated a calculation time under 1 second for all instances.
• The algorithm showed good generalization, efficiency, and practical application potential.

Conclusions:

• Deep reinforcement learning offers a powerful, adaptable approach to complex packing problems.
• The novel algorithm overcomes limitations of traditional heuristic methods.
• This method presents a promising direction for efficient and scalable packing solutions.