A memetic algorithm to pack unequal circles into a square. (English) Zbl 1391.90539
Summary: A circle packing problem involves packing given circles into a container. The objective is to minimize the size of the container without causing any overlap. This paper focuses on a representative circle packing problem where the circles are unequal and the container is a square, called packing unequal circles into a square (PUCS). It proposes a memetic algorithm to solve the problem. The memetic algorithm can be regarded as a combination of a genetic algorithm (GA) and an iterated local search (ILS). It is composed of a local search phase and a global transformation phase. The global transformation phase evolves a population; the local search phase optimizes the offsprings generated by the global transformation phase. The proposed approach exhibits several novel features in its global transformation phase, such as the \(z\)-crossover operator based on the symmetry of the container and the complementarity of the configuration, a perturbation operator inspired by gene-fragment-insertion, a reproduction selector based on the genetic relationships of the individuals, and a hybrid population updating strategy based on the diversity of the reproduction operators. Experimental results show that the memetic algorithm is effective for the problem.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C26 | Nonconvex programming, global optimization |
| 90B80 | Discrete location and assignment |
| 90B40 | Search theory |
| 52C15 | Packing and covering in \(2\) dimensions (aspects of discrete geometry) |
References:
| [1] | Addis, B.; Locatelli, M.; Schoen, F., Efficiently packing unequal disks in a circle, Oper. Res. Lett., 36, 1, 37-42, (2008) · Zbl 1151.90035 |
| [2] | Adickes, M. D.; Billo, R. E.; Norman, B. A.; Banerjee, S.; Nnaji, B. O.; Rajgopal, J., Optimization of indoor wireless communication network layouts, IIE Trans., 34, 9, 823-836, (2002) |
| [3] | Akeb, H.; Hifi, M., A hybrid beam search looking-ahead algorithm for the circular packing problem, J. Comb. Optim., 20, 101-130, (2010) · Zbl 1200.90141 |
| [4] | Akeb, H.; Hifi, M.; M’Hallah, R., A beam search algorithm for the circular packing problem, Comput. Oper. Res., 36, 5, 1513-1528, (2009) · Zbl 1177.90330 |
| [5] | Akeb, H.; Hifi, M.; Negre, S., An augmented beam search-based algorithm for the circular open dimension problem, Comput. Ind. Eng., 61, 2, 373-381, (2011) |
| [6] | Birgin, E. G.; Martinez, J. M.; Ronconi, D. P., Optimizing the packing of cylinders into a rectangular container: a nonlinear approach, Eur. J. Oper. Res., 160, 1, 19-33, (2005) · Zbl 1067.90133 |
| [7] | Castillo, I.; Kampas, F. J.; Pint´er, J. D., Solving circle packing problems by global optimization: numerical results and industrial application, Eur. J. Oper. Res., 191, 786-802, (2008) · Zbl 1156.90013 |
| [8] | Fraser, H. J.; George, J. A., Integrated container loading software for pulp and paper industry, Eur. J. Oper. Res., 77, 466-474, (1994) · Zbl 0800.90656 |
| [9] | Fu, Z. H; Huang, W. Q.; Lü, Z. P., Iterated tabu search for the circular open dimension problem, Eur. J. Oper. Res., 225, 236-243, (2013) · Zbl 1292.90164 |
| [10] | Fu, Z. H., Feasible approaches for solving the arbitrary sized circle packing problem (in Chinese), (2011), Huazhong University of Science and Technology Wuhan, China, Phd thesis |
| [11] | George, J. A.; George, J. M.; Lamar, G. B.W., Packing different-sized circles into a rectangular container, Eur. J. Oper. Res., 84, 3, 693-712, (1995) · Zbl 0928.90077 |
| [12] | Gill, P. E.; Murray, W.; Saunders, M. A., SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM J. Optim., 12, 4, 979-1006, (2002) · Zbl 1027.90111 |
| [13] | Grosso, A.; Jamali, A. R.; Locatelli, M.; Schoen, F., Solving the problem of packing equal and unequal circles in a circular container, J. Global Optim., 47, 1, 63-81, (2010) · Zbl 1190.90161 |
| [14] | Grosso, A.; Locatelli, M.; Schoen, F., A population-based approach for hard global optimization problems based on dissimilarity measures, Math. Programm., 110, 373-404, (2007) · Zbl 1116.90084 |
| [15] | He, K.; Huang, M.; Yang, C., An action-space-based global optimization algorithm for packing circles into a square container, Comput. Oper. Res., 58, 67-74, (2015) · Zbl 1348.90542 |
| [16] | He, K.; Huang, W., A cavingdegree based flake arrangement approach for the container loading problem, Comput. Ind. Eng., 59, 2, 344-351, (2010) |
| [17] | He, K.; Huang, W. Q.; Jin, Y., An efficient deterministic heuristic for two dimensional rectangular packing, Comput. Oper. Res., 39, 7, 1355-1363, (2012) · Zbl 1251.90321 |
| [18] | He, K.; Ji, P.; Li, C., A dynamic reduction algorithm for the rectangle packing area minimization problem, Eur. J. Oper. Res., 241, 3, 674-685, (2015) · Zbl 1339.90197 |
| [19] | He, K.; Jin, Y.; Huang, W., Heuristics fortwo-dimensional strip packing problem with 90° rotations, Expert Syst. Appl., 40, 14, 5542-5550, (2013) |
| [20] | He, K.; Mo, D.; Ye, T.; Huang, W., A coarse-to-fine quasi-physical optimization method for solving thecircle packing with equilibrium constraints problem, Comput. Ind. Eng., 66, 4, 1049-1060, (2013) |
| [21] | Hifi, M.; M’Hallah, R., Approximate algorithms for constrained circular cutting problems, Comput. Oper. Res., 31, 5, 675-694, (2004) · Zbl 1061.90095 |
| [22] | Hifi, M.; M’Hallah, R., A dynamic adaptive local search algorithm for the circular packing problem, Eur. J. Oper. Res., 183, 3, 1280-1294, (2007) · Zbl 1135.90037 |
| [23] | Hifi, M.; M’Hallah, R., Adaptive and restarting techniques-based algorithms for circular packing problems, Comput. Optim. Appl., 39, 17-35, (2008) · Zbl 1147.90390 |
| [24] | Hifi, M.; M’Hallah, R., A literature review on circle and sphere packing problems: models and methodologies, Adv. Oper. Res., (2009) · Zbl 1198.90337 |
| [25] | Huang, W. Q.; Fu, Z. H.; Xu, R. C., Tabu search algorithm combined with global perturbation for packing arbitrary sized circles into a circular container, Sci. China Inf. Sci., 56, 9, 1-14, (2013) |
| [26] | 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, 5, 539-548, (2005) · Zbl 1095.90095 |
| [27] | Huang, W. Q.; Li, Y.; Jurkowiak, B.; Li, C. M.; Xu, R. C., A two-level search strategy for packing unequal circles into a circle container, Principles and Practice of Constraint Programming-CP, 868-872, (2003), Springer Berlin Heidelberg |
| [28] | 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, 8, 2125-2142, (2006) · Zbl 1086.90063 |
| [29] | Huang, W. Q.; Zeng, Z. Z.; Xu, R. C.; Fu, Z. H., Using iterated local search for efficiently packing unequal disks in a larger circle, Adv. Mater. Res., 1477, 430-432, (2012) |
| [30] | Kubach, T.; Bortfeldt, A.; Gehring, H., Parallel greedy algorithms for packing unequal circles into a strip or a rectangle, Cent. Eur. J. Oper. Res., 17, 4, 461-477, (2009) · Zbl 1204.90083 |
| [31] | Liu, D. C.; Nocedal, J., On the limited memory BFGS method for large scale optimization, Math. Programm., 45, 1, 503-528, (1989) · Zbl 0696.90048 |
| [32] | Liu, J.; Xue, S.; Liu, Z.; Xu, D., An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle, Comput. Ind. Eng., 57, 3, 1144-1149, (2009) |
| [33] | Liu, J. F.; Li, G., Basin filling algorithm for the circular packing problem with equilibrium behavioral constraints, Sci. China Inf. Sci., 53, 5, 885-895, (2010) · Zbl 1497.52028 |
| [34] | López, C. O.; Beasley, J. E., Packing unequal circles using formulation space search, Comput. Oper. Res., 40, 5, 1276-1288, (2013) · Zbl 1352.90085 |
| [35] | Lü, Z.; Glover, F.; Hao, J. K., A hybrid metaheuristic approach to solving the UBQP problem, Eur. J. Oper. Res., 207, 3, 1254-1262, (2010) · Zbl 1206.90113 |
| [36] | Lü, Z. P.; Huang, W. Q., PERM for solving circle packing problem, Comput. Oper. Res., 35, 5, 1742-1755, (2008) · Zbl 1211.90198 |
| [37] | Müller, A.; Schneider, J. A.; Schömer, E., Packing a multidisperse system of hard disks in a circular environment, Phys. Rev. E, (2009) |
| [38] | Specht, E., 2012-2015. Packings of equal and unequal circles in variable-sized containers with maximum packing density <www.packomania.com; Specht, E., 2012-2015. Packings of equal and unequal circles in variable-sized containers with maximum packing density <www.packomania.com |
| [39] | Stoyan, Y.; Yaskov, G., Packing unequal circles into a strip of minimal length with a jump algorithm, Optim. Lett., 8, 3, 949-970, (2014) · Zbl 1292.90259 |
| [40] | Stoyan, Y. G.; Yas’kov, G., A mathematical model and a solution method for the problem of placing various-sized circles into a strip, Eur. J. Oper. Res., 156, 3, 590-600, (2004) · Zbl 1056.90018 |
| [41] | 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, 2, 440-453, (2002) · Zbl 1081.90593 |
| [42] | Wäscher, G.; Haussner, H.; Schumann, H., An improved typology of cutting and packing problems, Eur. J. Oper. Res., 183, 3, 1109-1130, (2007) · Zbl 1278.90347 |
| [43] | Ye, T., Huang, W.Q, & Lü, Z.P. (2013). Iterated tabu search algorithm for packing unequal circles in a circle. arXiv preprint arXiv:1306.0694; Ye, T., Huang, W.Q, & Lü, Z.P. (2013). Iterated tabu search algorithm for packing unequal circles in a circle. arXiv preprint arXiv:1306.0694 |
| [44] | Zeng, Z.; Yu, X.; He, K.; Huang, W.; Fu, Z., Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container, Eur. J. Oper. Res., 250, 2, 615-627, (2016) · Zbl 1346.90526 |
| [45] | Zhang, D. F.; Deng, A. S., An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Comput. Oper. Res., 32, 8, 1941-1951, (2005) · Zbl 1068.90095 |
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.
