The Decoder, Not the Metaheuristic: A Systematic Benchmark of 3D Bin Packing with Compatibility Constraints

Abstract

The three-dimensional single bin packing problem with categorical compatibility constraints (3D-SBPP-CC) extends the classical NP-hard packing problem by adding pairwise incompatibility rules over item categories. Although such constraints arise in hazardous materials logistics, no prior study has provided a complete mathematical formulation or a systematic multi-algorithm benchmark for this problem. This paper presents a novel mixed-integer linear programming (MILP) formulation of the 3D-SBPP-CC together with a strong NP-hardness proof. Four population-based metaheuristics—genetic algorithm (GA), particle swarm optimization (PSO), ant colony optimization (ACO), and differential evolution (DE)—are each implemented with two constraint-handling strategies (penalty function and repair operator), yielding eight configurations. These are evaluated against three baselines under a uniform budget of 10,000 fitness evaluations. Experiments on 45 stratified benchmark instances with 10 independent runs per configuration (4950 total runs) produce three findings. First, the eight metaheuristic variants and random search form a statistically homogeneous tier (Friedman χ2=197.49, p<10−36; CD=2.21). Second, constraint density strongly moderates algorithm ranking (Kendall’s W: 0.69 → 0.08). Third, decoder-embedded compatibility filtering renders explicit repair and penalty strategies equivalent (p>0.05 at all constraint levels). The greedy heuristic achieves 84.2% of the best metaheuristic’s utilization in under 0.1 s; random search reaches 98.7%. These results demonstrate that the DBLF placement decoder, not the choice of metaheuristic, governs packing quality for this problem class.