Adaptive beam search lookahead algorithms for the circular packing problem

摘要

This paper addresses the circular packing problem (CPP), which consists in packing n circles C_i each of known radius rh ieN= {1, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i)itCloNsh es oclevnetdeP reu osifn Cgf _Ptiw,.o adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level e,e = 1,...,n, , of the beam search tree corresponds to a partial packing of Q circles of N into C. The potential of each node of the tree is assessed using a lookahcad strategy that; starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms.