Intelligent Heuristic Selection for the Variable-Sized Bin Packing Problem with Conflicts: A Decision Tree-Based Approach

In this article, we look at the Variable-Sized Bin Packing Problem with Conflicts (VSBPPC). This problem consists of allocating items of specific sizes in bins with varying capacities and costs, respecting conflict restrictions between pairs of items, with the objective of minimizing the total cost of the bins used. Given its practical applicability in contexts such as resource allocation, production planning, and logistics distribution, and motivated by the high computational complexity of existing approaches, we present improvements to the Large Neighborhood Search Algorithm (LNSA), which include variations in constructive heuristics and the integration of machine learning models to guide algorithm decisions. The proposed approach was compared to the LNSA present in the literature, demonstrating an average improvement of 0.085%, while reducing the execution time to approximately one third of that required by the original algorithm.