2023/05/24 by Yulle G. F. Borges, Borges, Yulle G. F., Rafael C. S. Schouery +3
Engineering · #Advanced Manufacturing and Logistics Optimization #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.2305.15291
openalex publication_date 2023/05/24 · openalex created_date 2023/05/27 · openalex updated_date 2026/07/31
This paper focuses on exact approaches for the Colored Bin Packing Problem (CBPP), a generalization of the classical one-dimensional Bin Packing Problem in which each item has, in addition to its length, a color, and no two items of the same color can appear consecutively in the same bin. To simplify modeling, we present a characterization of any feasible packing of this problem in a way that does not depend on its ordering. Furthermore, we present four exact algorithms for the CBPP. First, we propose a generalization of Valério de Carvalho's arc flow formulation for the CBPP using a graph with multiple layers, each representing a color. Second, we present an improved arc flow formulation that uses a more compact graph and has the same linear relaxation bound as the first formulation. And finally, we design two exponential set-partition models based on reductions to a generalized vehicle routing problem, which are solved by a branch-cut-and-price algorithm through VRPSolver. To compare the proposed algorithms, a varied benchmark set with 574 instances of the CBPP is presented. Results show that the best model, our improved arc flow formulation, was able to solve over 62% of the proposed instances to optimality, the largest of which with 500 items and 37 colors. While being able to solve fewer instances in total, the set-partition models exceeded their arc flow counterparts in instances with a very small number of colors.