Optimizing Three-Dimensional Bag Packing

Jixuan Feng

doi:10.1109/TASE.2025.3648318

2026-01-01

PRE

Jixuan Feng

Hong Ma

Zhou Xu

DOI：10.1109/TASE.2025.3648318

原文链接

原文求助

摘要

En 中文

装箱作业因其灵活性和便利性而在物流领域得到广泛应用。对企业而言，减少使用包装袋不仅有助于降低成本，还能保护环境并促进可持续的废物管理实践。本研究提出了一种新型三维包装袋装箱问题（3D-BGPP），旨在考虑旋转的情况下将一组物品装入一组柔性包装袋中。我们构建了一个混合整数线性规划模型，并证明该问题属于强NP难问题。为更高效地求解该问题，我们开发了一种混合组合Benders分解-Beam Search算法（CBD-BS）。该算法基于组合Benders分解对3D-BGPP进行分解，其中主问题通过增强模型求解，子问题则通过一种新颖的极点基Beam Search算法以及数学规划求解。具体而言，Beam Search算法解决了柔性容器中未使用空间的表示挑战，并采用有限树搜索构建有前景的装箱方案。该整体算法进一步融入了有效不等式、变量固定及其他加速技术。我们在电子商务公司提供的真实订单数据和生成的实例上进行了计算实验。结果表明，CBD-BS算法在小规模和中规模实例中可在秒级内获得高质量解，在大型规模实例中可在分钟级内获得解。实践者注意事项——本文的研究动机源于与一家中国主要电子商务公司合作开展的项目，该公司在物流和配送中广泛使用包装袋。这是首次针对三维包装袋装箱问题（3D-BGPP）的研究，旨在最小化所用包装袋的总成本。我们提出了重塑规则以建模包装袋的柔性，并构建了优化模型。此外，我们还设计了一种基于组合Benders分解的Beam Search算法。行业参与者可应用我们的算法高效且有效地求解3D-BGPP，从而鼓励降低运营成本并保护环境。

Keyword:

Bag packing

reshaping rules

combinatorial benders decomposition

beam search