Solving non-oriented two dimensional bin packing problem using evolutionary particle swarm optimisation

The non-oriented two-dimensional bin packing problem (NO-2DBPP) deals with a set of integer sized rectangular pieces that are to be packed into identical square bins. The specific problem is to allocate the pieces to a minimum number of bins allowing the pieces to be rotated by 90° but without overlap. In this paper, an evolutionary particle swarm optimisation algorithm (EPSO) is proposed for solving the NO-2DBPP. Computational performance experiments of EPSO, simulating annealing (SA), genetic algorithm (GA) and unified tabu search (UTS) using published benchmark data were studied. Based on the results for packing 3000 rectangles, EPSO outperformed SA and GA. In addition; EPSO results were consistent with the results of UTS indicating that it is a promising algorithm for solving the NO-2DBPP.