.png){kind=icon}
.png){kind=icon}
Return
Optimizing Three-Dimensional Bag Packing
.png){kind=icon}
PRE
AI
DOI：10.1109/TASE.2025.3648318.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Bag packing is widely used in logistics due to its flexibility and convenience. It is important for a firm to reduce the use of bags, not only to cut costs but also to protect the environment and promote sustainable waste management practices. In this study, we propose a novel Three-Dimensional Bag Packing Problem (3D-BGPP) which aims to pack a set of items into a set of flexible bags considering rotation. A mixed-integer linear programming model is formulated. We show that this problem is strongly NP-hard. To solve the problem more efficiently, we develop a hybrid combinatorial Benders decomposition-Beam Search algorithm (CBD-BS). This algorithm decomposes 3D-BGPP based on the combinatorial Benders decomposition, where the master problem is solved by an enhanced model and the subproblems are solved by a novel extreme point-based beam search as well as mathematical programming. Specifically, the beam search algorithm addresses the challenge of representing unused space in flexible containers and uses a limited tree search to construct promising packing solutions. The overall algorithm is further enriched with valid inequalities, variable fixing and other acceleration techniques. Computational experiments are conducted on both real order data provided by an e-commerce company and generated instances. The results show that CBD-BS can obtain high-quality solutions within seconds in small and medium scale instances, and within minutes in large scale instances. Note to Practitioners—This paper is motivated by a research project conducted with a major e-commerce company in China, where bags are widely utilized in logistics and delivery. This is the first study on the three-dimensional bag packing problem (3D-BGPP), aimed at minimizing the total cost of bags in use. We propose reshaping rules to model the flexibility of bags and formulate the optimization model. Additionally, we have designed a combinatorial Benders decomposition-based beam search algorithm. Industry participants can apply our algorithm to efficiently and effectively solve the 3D-BGPP, thus encouraging the reduction of operational costs and environmental protection.
Keywords:
Bag packing
reshaping rules
combinatorial benders decomposition
beam search
Journal
IF:
6.4
Papers:
4.9K
Citations:
1.6W
View more organizations