A Hybrid Adaptive Iterated Local Search for the Variable-Sized Bin Packing Problem with Conflicts

This paper addresses the Variable-Sized Bin Packing Problem with Conflicts (VSBPPC), a bin packing generalization combining heterogeneous bin types and item incompatibilities. We propose a hybrid Adaptive Iterated Local Search (AILS) that explores feasible and infeasible solutions through a penalized objective function, applies RVND-based local search, and adjusts the perturbation strength according to search stagnation. The method also includes a set-covering neighborhood that recombines high-quality bins collected during the search, with both set-covering and set-partitioning variants; duplicated items in the set-covering variant are removed by a repair procedure. Experiments are conducted on the hardest benchmark instances, with 1000 items, large item sizes, and high conflict densities. Compared with previous Large Neighborhood Search Algorithm (LNSA) approaches, AILS improves the best-known values, obtaining an average gap of $-0.27\%$ with respect to the benchmark best-known values.