5 Smart Heuristic Methods for Solving Bin Packing Problems

5 Initial Heuristics

In this section, we present five fast CBPP heuristics. The solutions found by these heuristics are utilized as the initial solution of the VNS and the matheuristic.

5.1 Best Fit Decreasing

For BPP, Best Fit heuristic processes the items in a given permutation and packs the current item in the bin with the lowest residual capacity that it fits. We create a new bin if the item does not fit in any bin. The Best Fit Decreasing (BFD) heuristic is similar to Best Fit, with the difference that the items are processed in non-increasing order of weight.

A direct adaptation of both heuristics for the CBPP is to pack the current item in the fullest bin so that it fits and does not violate the color constraints.

5.2 Good Ordering

order may lead to a poor performance of Best Fit. With this in mind, we propose the Good Ordering (GO) heuristic that uses the Best Fit heuristic with a “good ordering”.

5.3 Minimum Bin Slack

The Minimum Bin Slack (MBS) is a BPP heuristic proposed by Gupta and Ho [23]. In each step of the MBS, we create a bin Br with the subset of remaining items that better fill it. To find this subset, we enumerate all valid sets, using the items in non-increasing order of weight. The MBS’ is a proposed modification by Fleszar and Hindi [19] that replaces the enumeration with Branch-and-Bound and forces the heaviest remaining item to be part of the chosen subset.

We also consider MBS’ for the CBPP. For the adaptation of this algorithm, it would be sufficient to impose that all partial solutions of the Branch-and-Bound respected the color constraints, i.e., each subset should be a valid pattern for CBPP (defined in the Section 2). However, this proved to be slow and led to low-quality solutions.

Seen this, we have made two modifications. The first one imposes a limit of n log n iterations to choose each pattern, where an iteration is an attempt to pack an item in the bin, improving the time execution. Upon reaching the iteration limit, we choose the best pattern seen so far. We decide this iteration limit empirically, based only on its apparent lack of significant influence on the quality of the solutions found. Moreover, the algorithm version using this first modification in our experiments is called MBS’.

The second modification focuses on improving the quality of solutions, and we do it by replacing the non-increasing order with the good-ordering. The algorithm with both modifications is called MBS’-GO.

5.4 Hard BFD

The Hard BFD is a new heuristic that tries to pack an item i using BFD in the opened bins. If it fails, then we run an alternative routine. In this routine, we select an item j, among the items with a color different from the color of i, that produces the destination bin Br with the lower residual capacity when i and j are packed together. If there is no valid move in the above routine, then we pack i alone in a new bin.

The pseudocode of the Hard BFD heuristic is presented in Algorithm 2. Since all lines inside the while loop have complexity O(n), this algorithm has time complexity O(n2 ).

5.5 Two-by-Two