A 3D Cargo Loading Optimization Algorithm Based on Extreme Point

Abstract

As the logistics industry shifts toward a "multi-variety, small-batch, and high-frequency" operational model, the three-dimensional bin packing problem (3D-BPP) has become increasingly constrained by heterogeneous cargo mixing, multiple physical constraints, and real-time operational requirements. Consequently, traditional manual methods and classic heuristic algorithms suffer from low loading efficiency, insufficient space utilization, and poor robustness. By synthesizing an extreme-point heuristic with a hybrid framework of genetic and simulated annealing algorithms (HGA-SA), this work establishes an advanced methodology for packing optimization. First, a mixed-integer programming (MIP) model is established, encompassing multiple constraints such as geometry, weight-bearing capacity, and loading/unloading rules. Second, during the spatial decoding phase, a strategy combining maximum residual space, flat layering, and extreme-point spatial pruning is introduced to reduce spatial fragmentation and ensure loading flatness. At the algorithmic level, a dual-layer encoding, adaptive evolution, and logical repair mechanism are designed. This mechanism incorporates chaotic initialization and Lamarckian repair operators, and is integrated with simulated annealing criteria to construct a hybrid algorithm that balances global exploration and local exploitation capabilities. Based on testing with the OR-Library benchmark dataset, the HGA-SA algorithm achieves an average volume utilization rate across all test instances that is 6.90 percentage points higher than that of the improved genetic algorithm, elevating the overall space utilization from 82.83% (with the baseline genetic algorithm) to 89.73%. Additionally, 3D graphical representations demonstrate the distinct superiority of our algorithm with respect to spatial compactness and structural equilibrium.