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.
References
Addis B, Locatelli M and Schoen F (2008). Efficiently packing unequal disks in a circle. Opns Res Lett 36: 37–42.
Akeb H, Hifi M and M'Hallah R (2009). A beam search algorithm for the circular packing problem. Comput Opns Res 36: 1513–1528.
Anstreicher KM (2009). Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J Global Optim 43: 471–484.
Appelbaum J and Weiss Y (1999). The packing of circles on a hemisphere. Meas Sci Technol 10: 1015–1019.
Barclay DR and Buckingham MJ (2009). On the shapes of natural sand grains. J Geophys Res B: Solid Earth 114: B02209, (doi:10.1029/2008JB005993).
Birgin EG and Gentil JM (2010). New and improved results for packing identical unitary radius circles within triangles, rectangles, and strips. Comput Opns Res 37: 1318–1327.
Birgin EG and Sobral FNC (2008). Minimizing the object dimensions in circle and sphere packing problems. Comput Opns Res 35: 2357–2375.
Butler S, Graham R, Guettler G and Mallows C (2009). Irreducible Apollonian configurations and packings. Discrete Comput Geom. (doi:10.1007/s00454-009-9216-9).
Castillo I, Kampas FJ and Pintér JD (2008). Solving circle packing problems by global optimization: Numerical results and industrial applications. Eur J Opl Res 191: 786–802.
Cassioli A, Locatelli M and Schoen F (2010). Dissimilarity measures for population-based global optimization algorithms. Comput Optim Appl 45: 257–281.
Collins CR and Stephenson K (2003). A circle packing algorithm. Comput Geom 25: 233–256.
Cui Y and Xu D (2010). Strips minimization in two-dimensional cutting stock of circular items. Comput Opns Res 37: 621–629.
Dowsland KA, Gilbert M and Kendall G (2007). A local search approach to a circle cutting problem arising in the motor cycle industry. J Opl Res Soc 58: 429–438.
Fukshansky L (2009). On similarity classes of well-rounded sublattices of ℤ2. J Number Theory 129: 2530–2556.
Giachetti RE and Sanchez JC (2009). A model to design recreational boat mooring fields. Nav Res Log 56: 158–174.
Grosso A, Jamali ARMJU, Locatelli M and Schoen F (2010). Solving the problem of packing equal and unequal circles in a circular container. J Global Optim 47: 63–81.
Hifi M and M'Hallah R (2007). A dynamic adaptive local search based algorithm for the circular packing problem. Eur J Opl Res 183: 1280–1294.
Hifi M and M'Hallah R (2008). Adaptive and restarting techniques-based algorithms for circular packing problems. Comput Optim Appl 39: 17–35.
Huang W and Chen M (2006). Note on: An improved algorithm for the packing of unequal circles within a larger containing circle. Comput Indust Eng 50: 338–344.
Huang WQ, Li Y, Li CM and Xu RC (2006). New heuristics for packing unequal circles into a circular container. Comput Opns Res 33: 2125–2142.
Huang X and Shen L (2009). On the convergence of circle packings to the quasiconformal map. Acta Math Sci 29: 1173–1181.
Huang X, Liu J and Shen L (2010). Schwarz's lemma for the circle packings with the general combinatorics. Sci CHINA Math 53: 275–288.
Ishizaka K (2009). New spatial measure for dispersed dot halftoning assuring good point distribution in any density. IEEE T Image Process 18: 2030–2047.
Lazarus SB, Tsourdos A, White BA, Zbikowski R and Silson P (2009). Cooperative UAVs mapping complex environment using 2D splinegon. In: Filipe J, Cetto JA and Ferrier JL (eds). Proceedings of the International Conference on Informatics in Control, Automation and Robotics. Institute for Systems and Technologies of Information, Control and Communication; Portugal, pp 413–416.
Lazos L, Poovendran R and Ritcey JA (2009). Detection of mobile targets on the plane and in space using heterogeneous sensor networks. Wirel Netw 15: 667–690.
Li W and Sun T (2009). Silica artificial opal incorporated with silver nanoparticles. Mater Chem Phys 116: 164–168.
Liu J, Shengjun X, Zhaoxia L and Danhua X (2009a). An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle. Comput Indust Eng 57: 1144–1149.
Liu J, Xu D, Yao Y and Zheng Y (2009b). Energy landscape paving algorithm for solving circles packing problem. International Conference on Computational Intelligence and Natural Computing. Vol. 1. IEEE Computer Society: Wuhan, China, pp. 107–110.
Locatelli M and Schoen F (2003). Efficient algorithms for large scale global optimization: Lennard-Jones clusters. Comput Optim Appl 26: 173–190.
Longuet-Higgins MS (2009). Snub polyhedra and organic growth. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. Vol. 456. The Royal Society: UK, pp 477–491.
Lü Z and Huang W (2008). PERM for solving circle packing. Comput Opns Res 35: 1742–1755.
Mladenović N, Plastria F and Urosevic D (2005). Reformulation descent applied to circle packing problems. Comput Opns Res 32: 2419–2434.
Nordbakke MW, Ryum N and Hunderi O (2004). Curvilinear polygons, finite circle packings, and normal grain growth. Mat Sci and Eng A 385: 229–234.
Pinter JD and Kampas FJ (2005). Nonlinear optimization in Mathematica with MathOp-timizer professional. Math Educ Res 10: 1–18.
Shi L, Olafsson S and Chen Q (1999a). A new hybrid optimization algorithm. Comput Indust Eng 36: 409–426.
Shi L, Olafsson S and Sun N (1999b). New parallel randomized algorithms for the traveling salesman problem. Comput Opns Res 47: 371–394.
Shi L and Men S (2003). Optimal buffer allocation in production lines. IIE Trans 35: 1–10.
Stoyan YG and Yaskov GN (2004). A mathematical model and a solution method for the problem of placing various sized circles into a strip. Eur J Opl Res 156: 590–600.
Sugihara K, Sawai M, Sano H, Kim DS and Kim D (2004). Disk packing for the estimation of the size of a wire bundle. Jpn J Indust Appl Math 21: 259–278.
Szabo PG, Markot MC, Csendes T, Specht E, Casado LG and Garcya I (2007). New approaches to circle packing in a square: With program codes. In: Springer Optimization and Its Applications. Vol. 6. Springer: New York, NY, USA.
Wang H, Huang W, Zhanga Q and Xua D (2002). An improved algorithm for the packing of unequal circles within a larger containing circle. Eur J Opl Res 141: 440–453.
Wang YS, Teng HF and Shi YJ (2009). Cooperative co-evolutionary scatter search for satellite module layout design. Eng Comput 26: 761–785.
Yang YL, Guo R, Luo F, Hu SM and Gu X (2009). Generalized discrete Ricci flow. Comput Graph Forum 28: 2005–2014.
Zhang D and Deng A (2005). An effective hybrid algorithm for the problem of packing circles into a larger containing circle. Comput Opns Res 32: 1941–1951.
Zhang W and Zhang Q (2009). Finite circle method for component approximation and packing design optimization. Eng Optimiz 41: 971–987.
Zhu JH, Beckers P and Zhang WH (2010). On the multi-component layout design with inertial force. J Comput Appl Math 234: 2222–2230.
http://recmath.com/contest/CirclePacking/index.php, accessed 19 May 2010.
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.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Al-Mudahka, I., Hifi, M. & M'Hallah, R. Packing circles in the smallest circle: an adaptive hybrid algorithm. J Oper Res Soc 62, 1917–1930 (2011). https://doi.org/10.1057/jors.2010.157
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2010.157