Adaptive algorithms for Circular Cutting/packing problems

In this paper, the Circular Cutting (CC)/packing problem is studied. Its objective is to cut/pack a set of circular pieces into a rectangular plate R of dimensions L × W. Each piece's type i, i = 1, …,m, is characterised by its radius ri and its demand bi. This problem is solved using an adaptive algorithm that combines Beam Search (BS) and various hill-climbing strategies. Decisions at each node of the truncated tree are based on the so-called best local position using a Minimum Local-Distance Position (MLDP) rule. The computational results show, on a set of problem instances of the literature, the effectiveness of the proposed algorithm.