×

A filtered beam search based heuristic algorithm for packing unit circles into a circular container. (English) Zbl 07877717

Summary: A constructive method for addressing the circular packing problem is proposed based on the filtered beam search framework, with the goal of minimizing the radius of a circular container that can hold \(N\) unit circles without overlapping. To position each circle in the container, the proposed method employs a corner-occupying placement strategy. Since there are often multiple possible positions for a circle to be packed, the method employs two steps to select the best placement. The positions are quickly assessed in the first phase, known as the filtering phase. In the second phase, known as the beam selection phase, a computationally intensive strategy is used to evaluate the positions more accurately. To balance the accuracy and efficiency of the method, two parameters are utilized, namely filterwidth and beamwidth. These parameters control the pruning operations in the tree-based search procedure. The performance of the proposed method is assessed utilizing two sets of 19 publicly available instances from the literature, and a comparative analysis is conducted against five constructive-based algorithms and one global optimization method. The computational results demonstrate its competitive performance, surpassing all constructive-based reference algorithms. Furthermore, a thorough investigation is conducted into the suggested method’s parameter settings and essential components.

MSC:

90Bxx Operations research and management science
Full Text: DOI

References:

[1] Akeb, H.; Hifi, M.; M’Hallah, R., A beam search algorithm for the circular packing problem, Comput. Oper. Res., 36, 1513-1528, 2009 · Zbl 1177.90330
[2] Akeb, H.; Hifi, M.; M’Hallah, R., Adaptive beam search lookahead algorithms for the circular packing problem, Int. Trans. Oper. Res., 17, 553-575, 2010 · Zbl 1220.90103
[3] J. Akiyama, R. Mochizuki, N. Mutoh, G. Nakamura. Maximin distance for n points in a unit square or a unit circle. In: J. Akiyama, M. Kano (Eds.). Japanese Conference on Discrete and Computational Geometry, JCDCG 2002, Tokyo, Japan, 2002, December 6-9. · Zbl 1179.68173
[4] Boll, D. W.; Donovan, J.; Graham, R. L.; Lubachevsky, B. D., Improving dense packings of equal disks in a square, Electron. J. Comb., 7, R46, 2000 · Zbl 0962.52004
[5] Castillo, I.; Kampas, F. J.; Pintér, J. D., Solving circle packing problems by global optimization: Numerical results and industrial applications, Eur. J. Oper. Res., 191, 3, 786-802, 2008 · Zbl 1156.90013
[6] Chen, M.; Tang, X. Y.; Song, T.; Zeng, Z. Z.; Peng, X. C.; Liu, S. Y., Greedy heuristic algorithm for packing equal circles into a circular container, Comput. Ind. Eng., 119, 114-120, 2018
[7] Croft, H. T.; Falconer, K.; Guy, R. K., Unsolved problems in geometry, 1991, Springer: Springer New York · Zbl 0748.52001
[8] Derrac, J.; García, S.; Molina, D.; Herrera, F., A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms, Swarm Evol. Comput., 1, 3-18, 2011
[9] Fodor, F., The densest packing of 19 congruent circles in a circle, Geom. Dedicata., 74, 139-145, 1999 · Zbl 0927.52024
[10] Fodor, F., The densest packing of 12 congruent circles in a circle, Contributions to Algebra and Geometry, 41, 401-409, 2000 · Zbl 0974.52015
[11] Galiev, S. I.; Lisafina, M. S., Linear models for the approximate solution of the problem of packing equal circles into a given domain, Eur. J. Oper. Res., 230, 505-514, 2013 · Zbl 1317.52029
[12] Graham, R. L.; Lubachevsky, B. D.; Nurmela, K. J.; Östergård, P. R., Dense packings of congruent circles in a circle, Discret. Math., 181, 139-154, 1998 · Zbl 0901.52017
[13] Grebennik, I. V.; Kovalenko, A. A.; Romanova, T. E.; Urniaieva, I. A.; Shekhovtsov, S. B., Combinatorial configurations in balance layout optimization problems, Cybern. Syst. Anal., 54, 221-231, 2018 · Zbl 1393.90102
[14] Grosso, A.; Jamali, A. R.M. J.U.; Locatelli, M.; Schoen, F., Solving the problem of packing equal and unequal circles in a circular container, J. Glob. Optim., 47, 63-81, 2009 · Zbl 1190.90161
[15] He, K.; Ye, H.; Wang, Z. L.; Liu, J. F., An efficient quasi-physical quasi-human algorithm for packing equal circles in a circular container, Comput. Oper. Res., 92, 26-36, 2018 · Zbl 1391.90519
[16] Hifi, M.; M’hallah, R., A literature review on circle and sphere packing problems: models and methodologies, Adv. Oper. Res., Article 150624 pp., 2009 · Zbl 1198.90337
[17] Huang, W. Q.; Li, Y.; Li, C. M.; Xu, R. C., New heuristics for packing unequal circles into a circular container, Comput. Oper. Res., 33, 2125-2142, 2006 · Zbl 1086.90063
[18] Huang, W. Q.; Ye, T., Global optimization method for finding dense packing of equal circle in a circle, Eur. J. Oper. Res., 210, 474-481, 2011 · Zbl 1213.90201
[19] Huang, W. Q.; Li, Y.; Akeb, H.; Li, C. M., Greedy algorithms for packing unequal circles into a rectangular container, J. Oper. Res. Soc., 56, 539-548, 2005 · Zbl 1095.90095
[20] Lai, X. J.; Hao, J. K.; Yue, D.; Lü, Z. P.; Fu, Z. H., Iterated dynamic thresholding search for packing equal circles into a circular container, Eur. J. Oper. Res., 299, 1, 137-153, 2022 · Zbl 1495.90157
[21] Litvinchev, I.; Espinosa, E. L.O., Integer programming formulations for approximate packing circles in a Rectangular container, Math. Probl. Eng., 317697, 2014 · Zbl 1407.90239
[22] Litvinchev, I.; Espinosa, E. L.O., Approximate packing circles in a rectangular container: valid inequalities and nesting, J. Appl. Res. Technol., 12, 716-723, 2014
[23] Litvinchev, I.; Infante, L.; Espinosa, E. L.Q., Using valid inequalities and different grids in LP-based heuristic for packing circular objects, Lect. Notes Comput. Sci, 9622, 681-690, 2016
[24] Liu, J. F.; Xue, S. J.; Liu, Z. X.; Xu, D. H., An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle, Comput. Ind. Eng., 57, 1144-1149, 2009
[25] Markót, M. C.; Csendes, T., A new verified optimization technique for the “packing circles in a unit square” problems, SIAM J. Optim., 16, 1, 193-219, 2005 · Zbl 1089.90045
[26] Melissen, H., Densest packing of eleven congruent circles in a circle, Geom. Dedicata., 50, 15-25, 1994 · Zbl 0810.52013
[27] Mladenović, N.; Plastria, F.; Urošević, D., Reformulation descent applied to circle packing problems, Comput. Oper. Res., 32, 2419-2434, 2005 · Zbl 1066.90092
[28] Pirl, U., Der mindestabstand von n in der einheitskreisscheibe gelegenen punkten, Mathematishe Nachrichten, 40, 111-124, 1969 · Zbl 0182.25102
[29] Sabuncuoglu, I.; Bayiz, M., Job shop scheduling with beam search, Eur. J. Oper. Res., 118, 390-412, 1999 · Zbl 0940.90037
[30] E. Specht. Packomania website: http://www.packomania.com. November 2020 (Accessed).
[31] Stoyan, Y.; Yaskov, G., Packing congruent hyperspheres into a hypersphere, J. Glob. Optim., 52, 855-868, 2012 · Zbl 1244.90200
[32] Stoyan, Y.; Yaskov, G.; Romanova, T.; Litvinchev, I.; Yakovlev, S.; Cantú, J. M.V., Optimized packing multidimensional hyperspheres: a unified approach, Math. Biosci. Eng., 76, 6, 6601-6630, 2020 · Zbl 1476.90291
[33] Wang, H. Q.; Huang, W. Q.; Zhang, Q.; Xu, D. M., An improved algorithm for the packing of unequal circles within a larger containing circle, Eur. J. Oper. Res., 141, 440-453, 2002 · Zbl 1081.90593
[34] Wang, S. J.; Xi, L. F.; Zhou, B. H., Filtered-beam-search-based algorithm for dynamic rescheduling in FMS, Rob. Comput. Integr. Manuf., 23, 457-468, 2007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.