Palletization and Build-up Scheduling Problem from an Air Cargo Application

Abstract

With the rapid development of cross-border e-commerce logistics, how to efficiently load goods into Unit Loaders (ULDs) and ensure their on-time delivery has become a key issue in logistics systems. Based on Cainiao's actual logistics challenges, this paper proposes a comprehensive loading planning scheme in two phases: the first phase solves how each item can be efficiently packed into ULDs in 3D space, and the second phase solves when each ULD can be loaded on multiple parallel workstations. This design-oriented approach fine-tunes and integrates existing optimization techniques into a cohesive pipeline to tackle these interconnected problems systematically.

To tackle the 3D Bin Packing Problem (3DBPP), two approaches, Mixed Integer Programming (MIP) and Extreme Point Heuristic (EPH), are used in this paper. The MIP model maximizes space utilization through accurate optimization and is suitable for small-scale packing scenarios, while the EPH algorithm performs well in large-scale scenarios and generates high-quality approximate solutions in a short period. Although its space utilization is slightly lower than that of MIP, its solution efficiency is well suited to real logistics operations that require fast response time.

For the Build-up Scheduling Problem (BSP), a parallel machine scheduling model is used to optimize the assembly sequence and timing of ULDs to ensure that all ULDs can be loaded within a strict time window. Experimental results show that the model performs well in optimizing workstation load balancing and avoiding delays, which can significantly improve the scheduling efficiency of the whole system.

The research results in this paper are validated to show that the proposed two-stage framework has significant application value in improving space utilization, reducing cargo delays, and optimizing workstation scheduling in real logistics scenarios of Cainiao. Future research can introduce a feedback loop between the two phases, and combine real-time data with dynamic adjustment strategies, hybrid algorithms, and other methods to further improve the adaptability and efficiency of the model.