Abstract
The circular packing problem (CPP) consists of packing n circles C i 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.
| Original language | English |
|---|---|
| Pages (from-to) | 1917-1930 |
| Number of pages | 14 |
| Journal | Journal of the Operational Research Society |
| Volume | 62 |
| Issue number | 11 |
| DOIs | |
| State | Published - Nov 2011 |
Keywords
- circular packing
- heuristics
- nested partitioning
- non-linear programming
- tabu search
Fingerprint
Dive into the research topics of 'Packing circles in the smallest circle: An adaptive hybrid algorithm'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver