Packing circles in the smallest circle: an adaptive hybrid algorithm

Abstract

The circular packing problem (CPP) consists of packing n circles C_i of known radii r_i, i∈N={1, …, n}, into the smallest containing circle ℂ. The objective is to determine the coordinates (x_i, y_i) of the centre of C_i, i∈N, as well as the radius r and centre (x, y) of ℂ. 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.

Keywords:

• heuristics
• tabu search
• non-linear programming
• circular packing
• nested partitioning

Acknowledgements

We thank the anonymous referees for their helpful comments and suggestions that contributed to the improvement of the presentation and contents of this paper. We are grateful to Prof Nenad Mladenović for his insight regarding the NLP models.