2019/05/08 by Luiz Felipe de Oliveira Moura Santos, Santos, Luiz F. O. Moura, Hugo Tsugunobu Yoshida Yoshizaki +3
Engineering · #Advanced Manufacturing and Logistics Optimization #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1905.03427
openalex publication_date 2019/05/08 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Bin Packing with Conflicts (BPC) are problems in which items with\ncompatibility constraints must be packed in the least number of bins, not\nexceeding the capacity of the bins and ensuring that non-conflicting items are\npacked in each bin. In this work, we introduce the Bin Packing Problem with\nCompatible Categories (BPCC), a variant of the BPC in which items belong to\nconflicting or compatible categories, in opposition to the item-by-item\nincompatibility found in previous literature. It is a common problem in the\ncontext of last mile distribution to nanostores located in densely populated\nareas. To efficiently solve real-life sized instances of the problem, we\npropose a Variable Neighborhood Search (VNS) metaheuristic algorithm.\nComputational experiments suggest that the algorithm yields good solutions in\nvery short times while compared to linear integer programming running on a\nhigh-performance computing environment.\n