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 r_i and its demand b_i. 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.