Packing circles in the smallest circle: an adaptive hybrid algorithm |
| |
Authors: | I Al-Mudahka M Hifi R M'Hallah |
| |
Institution: | 1.Kuwait University,Kuwait;2.Université de Picardie Jules Verne,Amiens,France |
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|