Solving two-dimensional bin packing problems with two-stage guillotine cutting by combined local search heuristics

Abstract

In this paper, a new efficient algorithm named combined local search heuristics which comprise two local search heuristics, Variable Neighborhood Descent (VND) and Random Neighbor Selection (RNS), is designed and proposed to solve two-dimensional guillotine bin packing problems. The objective of these problems is to pack smaller pieces of rectangular items into large rectangular bins without overlapping such that the total number of used bins is minimized. A constructive heuristic (CH) is conceived to construct a solution by packing items into bins with the use of a defined item packing sequence. VND and RNS, which consist of three deterministic neighborhood structures and three random neighbor selection operators, respectively, are used for improving a solution given by the CH. Benchmark instances were adopted to verify the effectiveness of the designed algorithm via computational experiments. Computational results show that, in terms of the quality of solutions, the proposed approach is better than other heuristics and meta-heuristics. In terms of computational times, the proposed algorithm cannot be compared to other algorithms and the computational experiments cannot offer enough evidence of showing any good running-time behavior of the proposed algorithm because of different models of computers used. However, from a practical point of view, easy implementation and reasonable and affordable computational times confirm the usefulness of the proposed algorithm.