Can Deep Reinforcement Learning Shrink Packing Costs? A New 3D Bin Packing Study

Introduction

Three‑dimensional bin packing is a classic combinatorial optimization problem widely used in logistics and manufacturing. In many practical scenarios the container size is not fixed and the material cost is proportional to its surface area. This paper defines a new variant whose objective is to minimize the surface area of a single container that can accommodate all items.

Related Work

The two‑dimensional version of the problem is known to be NP‑hard, and consequently the three‑dimensional version is also NP‑hard. Prior research has focused on heuristic and approximate algorithms, as well as exact branch‑and‑bound methods for small instances. Recent advances in deep reinforcement learning (DRL) have shown promise for combinatorial optimization. In particular, the Pointer Network (Ptr‑Net) architecture (Vinyals et al., 2015; Bello et al., 2016) has been successfully applied to the traveling salesman problem and knapsack problem.

Problem Definition

Given a set of rectangular items \(i\) with length \(l_i\), width \(w_i\) and height \(h_i\), the decision variables are the placement order \((x_i, y_i, z_i)\) and orientation of each item. The goal is to find a placement that fits all items without overlap and yields the minimum possible container surface area. The mathematical formulation is illustrated in Figure 1.

Deep Reinforcement Learning Approach

We adopt the Pointer Network architecture to predict the insertion order of items. The network consists of an encoder LSTM that embeds each item’s dimensions and a decoder LSTM that attends to encoder states via a Glimpse mechanism. The predicted order is then fed to a heuristic that selects the position and orientation minimizing the incremental surface area.

Training Details

Training uses a memory‑replay baseline. For each sample \(s_i\) a heuristic provides an initial surface‑area baseline \(b(s_i)\). The REINFORCE update with baseline is applied as shown in the equation image.

During training we sample actions from the model’s probability distribution; during evaluation we use greedy selection or beam search (beam width \(k=3\)).

Experiments

We trained on 150 k samples and tested on 150 k samples for order sizes of 8, 10 and 12 items. Hyper‑parameters: batch size 128, LSTM hidden size 128, Adam learning rate 0.001 with decay factor 0.96 every 5 000 steps, L2 regularization, and baseline decay 0.7. Training ran for 1 M steps on a Tesla M40 GPU (≈12 h). Results show that the DRL method with beam search reduces the average surface area by 4.9 %–5.3 % compared with the heuristic, and is within about 10 % of the optimal order obtained by exhaustive search for 8‑item instances.

Conclusion

The proposed surface‑area‑minimizing 3D packing problem is NP‑hard. A deep reinforcement learning solution based on Pointer Net effectively learns insertion orders and outperforms existing heuristics. Future work will integrate position and orientation decisions into the learning framework and explore more powerful network architectures.