A Crow Search-Based Genetic Algorithm for Solving Two-Dimensional Bin Packing Problem

摘要

The two-dimensional bin packing problem (2D-BPP) consists of packing, without overlapping, a set of rectangular items with different sizes into smallest number of rectangular containers, called "bins", having identical dimensions. According to the real-word requirements, the items may either have a fixed orientation or they can be rotated by 90°. In addition, it may or not be subjugate to the guillotine cutting. In this article, we consider the two-dimensional bin packing problem with fixed orientation and free cutting. In fact, we propose a hybrid approach by combining two bio-inspired algorithms that are the crow search algorithm (CSA) and the genetic algorithm (GA) to solve the considered problem. So, the main idea behind this hybridization is to expect reaching a sort of cooperative synergy between the operators of the two combined algorithms. That is, the CSA is discretized and adapted to the 2D-BPP context, while using genetic operators to improve individuals (i.e. crows) adaptation. The average performance of the proposed hybrid approach is evaluated on the standard benchmark instances of the considered problem and compared with two other bio-inspired algorithms having closely similar nature; namely standard genetic algorithm and binary particle swarm optimization algorithm. The obtained results are very promising.