Packing circles in the smallest circle: an adaptive hybrid algorithm

Packing circles in the smallest circle: an adaptive hybrid algorithm

0.00 Avg rating0 Votes
Article ID: iaor20119860
Volume: 62
Issue: 11
Start Page Number: 1917
End Page Number: 1930
Publication Date: Nov 2011
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: heuristics: tabu search
Abstract:

The circular packing problem (CPP) consists of packing n circles Ci of known radii ri, i∈N={1,…,n}, into the smallest containing circle ℂ. The objective is to determine the coordinates (xi,yi) of the centre of Ci, 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.

Reviews

Required fields are marked *. Your email address will not be published.