Constructive Heuristics for Value-Driven 3D Bin Packing with Real-World Constraints

Abstract

This work presents a heuristic framework for value-driven three-dimensional bin packing for air cargo operation under practical constraints such as batch arrivals, box fragility, and stability requirements. The method builds on the extreme-point placement heuristic, enhanced with a two-stage box selection strategy that first filters boxes by value density and then sorts them with attention to geometric alignment. Stability checks including supporting surface area, corner support, and padding tolerance are introduced to ensure realistic placements, along with a dedicated procedure for safely placing fragile items. A batch-handling mechanism allows bins to be packed progressively as boxes arrive, using volume-based thresholds to lock or release partially filled bins. Performance is evaluated using several types of box sets that differ in shape regularity and distribution. Results show that relaxing stability conditions improves both value and volume metrics, and that sorting strategies which consider box dimensions outperform value-only sorting. The framework also highlights the limitations of packing overly uniform boxes and the quality of solutions decreased as the number of bins increases. The method aims to balance space usage and value considerations while accounting for constraints commonly found in logistics settings.