Packing circles in the smallest circle: an adaptive hybrid algorithm

The circular packing problem (CPP) consists of packing n circles C-i of known radii r(i), i is an element of N = {1, ..., n}, into the smallest containing circle C. The objective is to determine the coordinates (x(i), y(i)) of the centre of C-i, i is an element of N, as well as the radius r and centre (x,y) of C. CPP, which is a variant of the two-dimensional open-dimension problem, is NP hard. This paper presents an adaptive algorithm that incorporates nested partitioning within a tabu search and applies some diversification strategies to obtain a (near) global optimum. The tabu search is to identify the n circles' ordering, whereas the nested partitioning is to determine the n circles' positions that yield the smallest r. The computational results show the efficiency of the proposed algorithm. Journal of the Operational Research Society (2011) 62, 1917-1930. doi:10.1057/jors.2010.157 Published online 24 November 2010