Multi-Constraint Three-Dimensional Bin Packing Optimization for Mixed Vehicle Types: A Heuristic Approach

Abstract

Aiming at the multi-constraint three-dimensional bin packing problem for mixed vehicle types in urban logistics, where traditional exact algorithms are limited by NP-hard computational complexity and practical engineering constraints, this study proposes a progressive optimization framework for vehicle loading and fleet allocation optimization. First, a heuristic loading algorithm based on the extreme point method and greedy strategy is developed to maximize single-vehicle loading efficiency by balancing space and weight utilization. Second, an NSGA-II based evolutionary framework with sequential encoding is constructed to minimize fleet size while improving loading balance for single-vehicle-type optimization. Third, a three-stage hybrid algorithm integrating greedy packing, enumerative search, and tail vehicle replacement is designed to optimize mixed-vehicle fleet composition and minimize total transportation cost. Experimental results demonstrate that the proposed heuristic achieves high composite loading performance across vehicle types, and the evolutionary framework significantly reduces fleet size compared with theoretical lower bounds. Under mixed-fleet optimization, the model identifies cost-effective vehicle configurations that outperform single-type dispatching strategies. Sensitivity analysis reveals that cargo composition, particularly the number of fragile items, is the most critical factor affecting system performance, while validation on 16 vehicle types confirms the robustness and practical generalizability of the method. This study verifies the effectiveness and stability of heuristic-evolutionary hybrid optimization methods, providing a reliable decision-making reference for logistics enterprises in vehicle selection, cargo allocation, and transportation planning.