Variable Neighborhood Search for the Bin Packing Problem with Compatible Categories
This addresses a practical problem in last-mile distribution to nanostores in densely populated areas, but it is incremental as it adapts an existing metaheuristic to a new variant.
The authors tackled the Bin Packing Problem with Compatible Categories (BPCC), a variant with category-based conflicts, by proposing a Variable Neighborhood Search (VNS) metaheuristic algorithm, which yields good solutions in very short times compared to linear integer programming on high-performance computing.
Bin Packing with Conflicts (BPC) are problems in which items with compatibility constraints must be packed in the least number of bins, not exceeding the capacity of the bins and ensuring that non-conflicting items are packed in each bin. In this work, we introduce the Bin Packing Problem with Compatible Categories (BPCC), a variant of the BPC in which items belong to conflicting or compatible categories, in opposition to the item-by-item incompatibility found in previous literature. It is a common problem in the context of last mile distribution to nanostores located in densely populated areas. To efficiently solve real-life sized instances of the problem, we propose a Variable Neighborhood Search (VNS) metaheuristic algorithm. Computational experiments suggest that the algorithm yields good solutions in very short times while compared to linear integer programming running on a high-performance computing environment.