Source-linked AI summary
Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method
Haoyuan Hu, Xiaodong Zhang, Xiaowei Yan, Longfei Wang, Yinghui Xu
TL;DR
The paper studies a new 3D bin-packing problem in which cuboid items are packed into a smallest-surface-area bin, motivated by settings without fixed-size bins. It uses a deep-reinforcement-learning method based on Pointer Networks to optimize item order, achieving about 5% improvement over a heuristic method in numerical experiments.
Problem
The paper asks how to pack cuboid items into a bin with minimum surface area when fixed-size bins are unavailable and bin cost is proportional to surface area.
Method
A Pointer Network-based deep-reinforcement-learning method optimizes the sequence in which items are packed, assigning higher probability to sequences with smaller surface areas.
Results
The proposed method achieves 4.89%, 4.88%, and 5.33% improvement over a heuristic algorithm for Bin8, Bin10, and Bin12, respectively.
Takeaways & Limitations
The results show that optimizing item sequence with the DRL method can produce packing solutions close to optimal sequences for the tested Bin8 samples.
Takeaways & Limitations
Future work identifies more effective network architectures and training algorithms, and integrating orientation and empty maximal-space selection into the neural architecture.
Abstract
from arXiv · showhide
In this paper, a new type of 3D bin packing problem (BPP) is proposed, in which a number of cuboid-shaped items must be put into a bin one by one orthogonally. The objective is to find a way to place these items that can minimize the surface area of the bin. This problem is based on the fact that there is no fixed-sized bin in many real business scenarios and the cost of a bin is proportional to its surface area. Our research shows that this problem is NP-hard. Based on previous research on 3D BPP, the surface area is determined by the sequence, spatial locations and orientations of items. Among these factors, the sequence of items plays a key role in minimizing the surface area. Inspired by recent achievements of deep reinforcement learning (DRL) techniques, especially Pointer Network, on combinatorial optimization problems such as TSP, a DRL-based method is applied to optimize the sequence of items to be packed into the bin. Numerical results show that the method proposed in this paper achieve about 5% improvement than heuristic method.
1 Introduction
The paper introduces a 3D bin-packing variant for real-world settings without fixed-size bins, where the goal is to minimize the surface area and associated packing cost. It motivates a deep-reinforcement-learning approach because heuristic methods can lack generality across problem types.
- Classical BPP: 3D bin packing places differently sized cuboid items orthogonally into bins and is an NP-hard combinatorial optimization problem.Effective algorithms can reduce computation time and packing cost while improving resource utilization.
- Motivation: In many business scenarios, flexible or soft packing materials replace fixed-size bins, while packing-material cost is mainly determined by surface area.Cross-border e-commerce is given as an example.
- New problem: The proposed problem packs all items into a bin whose surface area is minimized.This objective differs from classical BPP, which minimizes the number of fixed-size bins used.
- Approach: Heuristic algorithms often require problem-specific design, limiting their generality, whereas deep reinforcement learning has shown potential for combinatorial optimization.The paper applies a DRL-based method to the new 3D bin-packing problem and evaluates it with numerical experiments based on real data.
2 Related Work
Prior work on 3D packing includes approximation, heuristic, exact, and real-world variant methods. Related research also considers strip packing and learning-based approaches, while neural combinatorial optimization uses attention-based sequence models such as Pointer Networks.
- 3D bin packing: Research on 3D bin packing includes approximation algorithms, heuristic methods, mixed-integer programming, and exact branch-and-bound approaches.Examples include Tabu Search, guided local search, extreme-point heuristics, hybrid genetic algorithms, and exact methods solving instances with up to 90 items within reasonable time limits.
- 3D bin packing: Real-world BPP variants studied in prior work include variable-size bins, conflicts between items, and fragile objects.These variants extend the classical packing setting to practical constraints.
- Strip packing: Strip packing similarly packs cuboid items orthogonally but minimizes packing height within a strip whose length and width are fixed and whose height is unlimited.The problem has applications in steel and textile industries.
- Learning-based optimization: Learning-based combinatorial optimization research includes reinforcement-learning hyper-heuristics that update heuristic-selection probabilities.The cited work discusses learning mechanisms for selecting among heuristics.
- Neural combinatorial optimization: Sequence-to-sequence and attention models contributed to neural combinatorial optimization, including Pointer Networks for solving combinatorial problems.Attention mechanisms had also been applied in machine translation and algorithm learning.
3 Deep Reinforcement Learning Method for 3D Bin Packing Problem
The problem minimizes the surface area of a bin packing all items, while the method uses deep reinforcement learning to optimize packing decisions, especially item sequence. A Pointer Net-style architecture models item sequences, and reinforcement learning trains it using surface-area outcomes.
- 3.1 Definition of the problem: The new 3D bin packing problem minimizes the surface area of a bin that contains all cuboid-shaped items.This setting differs from fixed-bin packing because the bin is designed around the items.
- 3.1 Definition of the problem: The formulation minimizes L · W + L · H + W · H while assigning item positions, non-overlapping relations, and orientations.The decision variables include bin dimensions, item coordinates, relative positions, and six possible orientations.
- 3.1 Definition of the problem: Constraints (1), (3), (4), and (5) prevent item overlap, while constraints (6), (7), and (8) keep items inside the bin.Constraints (9), (10), and (11) calculate each item's dimensions after orientation.
- 3.2 Deep Reinforcement Learning Method: The constructive method makes decisions about packing sequence, item orientation, and the empty maximal space receiving each item.A heuristic evaluates empty spaces and six orientations, then selects remaining items according to waste space.
- 3.2 Deep Reinforcement Learning Method: The Pointer Net-style network receives item dimensions and outputs the order in which items are packed.An encoder processes item size data, while a decoder selects encoder outputs using attention and glimpse mechanisms.
- 3.2 Deep Reinforcement Learning Method: The policy assigns probabilities to item sequences, and training seeks high probabilities for sequences producing small surface areas.REINFORCE-style updates use a surface-area baseline to reduce gradient variance; testing uses greedy selection and beam search.
4 Experiments
The experiments evaluate the method on orders containing 8, 10, or 12 items using real data, reporting average surface area as the performance indicator. Across these settings, beam search improves on the heuristic baseline and approaches exhaustive-search solutions for Bin8.
- Experiments use real data with 8, 10, and 12 items per customer order, using 150,000 training samples and 150,000 test samples in each category.The same hyper-parameters are used across item-count categories.
- Average surface area (ASA) is the performance indicator, and testing uses beam search with size 3.
- 4.89%, 4.88%, and 5.33% improvement over the heuristic algorithm is achieved for Bin8, Bin10, and Bin12, respectively.
- For 5,000 Bin8 samples, the heuristic-to-optimal gap is about 10%, while reinforcement-learning beam-search results are reported as very close to optimal sequences.
5 Conclusion
The paper proposes a surface-area-minimizing 3D bin packing problem and applies a Pointer Network-based deep reinforcement learning method to optimize packing sequences. Experiments on real data report that the method significantly outperforms a well-designed heuristic algorithm, while future work targets network, training, orientation, and empty-space decisions.
- The new problem minimizes the surface area of the smallest bin that can pack all items, unlike classical 3D BPP, which uses fixed bin size and minimizes bin count.
- A Pointer Network framework and deep reinforcement learning optimize the sequence of items packed into the bin.
- Experiments with a large amount of real data show that the DRL-based method significantly outperforms a well-designed, effective heuristic algorithm.
- Future research will investigate more effective network architectures and training algorithms, and integrate orientation and empty maximal-space selection into the neural-network architecture.
A 3D Bin Packing Heuristic Algorithm
The heuristic algorithm combines least-surface-area placement with least-waste-space item selection. It evaluates candidate spaces and orientations for placement, then selects the remaining item producing the least waste space.
- The heuristic uses both least surface area and least waste space, whereas the DRL method uses only least surface area.
B NP-hardness of New Type of 3D BPP
The paper proves the new 3D bin packing problem is NP-hard through a reduction from one-dimensional bin packing. The construction uses a base item and constrained item dimensions so minimizing surface area corresponds to minimizing the number of capacity-W bins.
- The new type of 3D bin packing problem is NP-hard.
- The proof begins by reducing one-dimensional bin packing, whose objective is minimizing the number of bins needed for items with sizes w1, ···, wn and capacity W.
- The reduction creates n items with widths wi and height 1/(n · max(wi)), plus a Base Item with width W and height W · n · max(wi).
- The construction assumes the Base Item is at the bin's left-bottom position and analyzes whether other items are placed to its right or above it.
- The heuristic algorithm initializes a large bin, selects the largest-surface-area item first, then chooses subsequent items using least waste space and placements using least surface area.
- The 3D construction adds length 1/(n · max(wi))^2 to each item, ensuring that no item is added on the length side.