Fast Neighborhood Search Heuristics for the Colorful Bin Packing Problem

Abstract

The Colorful Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number of used bins and satisfying the constraint that two items of the same color cannot be packed side by side in the same bin. In this article, we proposed an adaptation of BPP heuristics and new heuristics for the CBPP. Moreover, we propose a set of fast neighborhood search algorithms for CBPP. These neighborhoods are applied in a meta-heuristic approach based on the Variable Neighborhood Search (VNS) and a matheuristic approach that mixes linear programming with the meta-heuristics VNS and Greedy Randomized Adaptive Search (GRASP). The results indicate that our matheuristic is superior to VNS and that both approaches can find near-optimal solutions for a large number instances, even for instances with many items.

Keywords: Cutting; Packing; Meta-heuristic; Matheuristic; Neighborhood Search

1 Introduction

In the Bin Packing Problem (BPP), there is a set of items and an unlimited set of bins of equal capacity. The objective is to allocate the items in bins, respecting their capacities and minimizing the number of used bins. A generalization of BPP is the Colorful Bin Packing Problem (CBPP), where each item also has a color, and there is an additional constraint that two items of the same color cannot be packed side by side in the same bin.

The CBPP was proposed independently by B¨ohm et al [5] and D´osa and Epstein [17], being studied in these articles only from the point of view of online algorithms and approximation algorithms. In particular, B¨ohm et al. show that the adaptations of the BPP classic algorithms First Fit, Best Fit, and Worst Fit for the CBPP have unbounded approximation ratios. Moreover, the authors prove that any online algorithm has an asymptotic competitive ratio of at least 2.5 and show an (absolute) 3.5-competitive algorithm. Also, some years before these works, Balogh et al [2] introduced the Black and White Bin Packing Problem (BWBPP), a particular case of CBPP with only two colors.

Just like Balogh et al [2], the following works Chen et al [13], Balogh et al [3], and B¨ohm et al [6] studied approximation algorithms for online and offline versions of BWBPP and CBPP.

An exact and linear algorithm for CBPP was proposed by Alsarhan et al [1] for the particular case where all items have zero weight. Later, Borges and Schouery [7], Borges et al [8] proposed four exact algorithms for the CBPP. The first two are pseudo-polynomial formulations based on Arc Flow Formulation for the BPP proposed by Carvalho [11]. On the other hand, the last two are set-partition formulations solved by the VRPSolver framework proposed by Pessoa et al [30].

Balogh et al [2] presents two applications for CBPP. The first one is in packing problems of twodimensional objects of similar widths that must be packed alternately. For example, consider the contents of information and advertisement on video-content sharing portals (like YouTube) and Social Media, which should fit under each other due to the tiny display of smartphones. Thus, the maximum content that fits in one screen is the bin capacity, the content height is the item size, the information contents have the color white, and advertisement contents have the color black.

The second application is commercial breaks on radio or TV, where commercials of different lengths and genres must be scheduled for commercial blocks. In this case, the length of the commercial blocks represents the bin capacity, and the commercial duration is the item size. Two commercials of the same genre have the same color to prohibit them from being transmitted in sequence.

The CBPP is an NP-hard problem since it is a generalization of BPP (Karp [25]). For dealing with NP-hard problems, in addition to the exact algorithm approach, another interesting approach is heuristic algorithms, in particular, the meta-heuristic approach, which commonly finds high-quality solutions in reasonable computational time.

In this article, we study CBPP using meta-heuristic and matheuristic approaches, and, as far as we know, it is the first study in the literature to use this approach. Next, we present a literature review of heuristic approaches to BPP and present our contribution to CBPP.

1.1 Literature Review

Many authors have studied BPP and its variants in the literature, using much as exact algorithms as meta-heuristic algorithms. Next, we present a review of the best-known algorithms for BPP and its generalization called the Cutting Stock Problem (CSP). Also, we introduce the main studies that utilize the VNS in the BPP.

The BPP exact algorithms are based on two main formulation types: the formulation of Gilmore and Gomory [21] and the Arc Flow Formulation of Carvalho [11]. Other works that use Gilmore and Gomory Formulation are Vance [31], Belov and Scheithauer [4], and Wei et al [32]. On the other hand, for the arc flow, there are the following works Brand˜ao and Pedroso [9], Delorme and Iori [14], and de Lima et al [26].

Conversely, in the heuristic algorithm approach, Fleszar and Hindi [19] study the Variable Neighborhood Search (VNS) meta-heuristic applied to BPP. In this work, the authors use a variation of the heuristic called Minimum Bin Slack, proposed by Gupta and Ho [23] as an initial solution for VNS. This combination proved to be quite powerful and is able to find the optimal solution in 1329 of the 1370 instances evaluated.

Sequentially, Loh et al [27] use the Weight Annealing meta-heuristic in the BPP, which finds optimal solutions in all instances used by Fleszar and Hindi. Castelli and Vanneschi [12] propose a BPP heuristic called BPHS, which is used as the initial solution of the VNS. Despite promising results, this combination has shown a lower performance than two previous studies.

Finally, Gonz´alez-San-Mart´ın et al [22] presents a comparative study among nineteen heuristic algorithms proposed in the last two decades. The best algorithm in the study was the Consistent Neighborhood Search (CNS) introduced by Buljubaˇsi´c and Vasquez [10], which solved 99.81% of the studied instances.

1.2 Our Contributions

In this article, we study the CBPP using five initial construction heuristics. The first two are adaptations of heuristics of the BPP called Best Fit Decreasing and Minimum Bin Slack. The last three are heuristics proposed by us called Good Ordering, Hard BFD, and Two-by-Two. In sequence, we present a meta-heuristic approach for CBPP using the VNS, which uses the previous heuristics to build the initial solution. Lastly, we propose a new matheuristic that mixes linear programming with the meta-heuristics VNS and Greedy Randomized Adaptive Search (GRASP). Our results show that our approaches can find near-optimal solutions for instances of up to 104 items in seconds. In particular, for all instances studied of up to 2 × 103 items and with the known optimal solution, our approaches, in 60 seconds, find solutions that use at most one extra bin than an optimal solution.

The article is organized as follows. In Section 2, we present a formal definition for CBPP. Next, in Section 3, we present some convenient notations and prove a proposition that provides easy handling of color constraints. In Section 4, we propose an Auxiliary Algorithm, which we use as a subroutine in some of our algorithms. The initial heuristics, the VNS, and the matheuristic are introduced, respectively, in Sections 5, 6, and 7. Finally, the computational results and conclusion are present in Sections 8 and 9.