A Perturbation-Based Iterative Heuristic and Local Search for the Variable Sized Bin-Packing Problem

The Variable Sized Bin-Packing Problem (VSBPP) is an NP-hard combinatorial optimization problem that consists of allocating items into bins, minimizing the total packing cost. Items are characterized by their weights, while bins are defined by their capacities and costs. This work proposes an iterative heuristic based on item order perturbation and local search over multiple neighborhoods, including bin type reduction, bin merging, and adjacent pair refinement. Computational experiments were conducted on 199 benchmark instances from the literature, using state-ofthe-art results as reference. The results demonstrate that the approach is promising, as seven new best-known solutions were found, with particular highlight on convex cost instances, in which the algorithm matched or outperformed the state of the art on all tested instances.