Daire Paketleme Problemi: Bir Literatür Çalışması

Yıl 2020, Cilt: 2 Sayı: 1, 18 - 31, 30.06.2020

Sedat Hakyemez Uğur Özcan

Öz

Daire Paketleme Problemi (DPP), palet veya farklı bir alan içine daire şeklindeki nesnelerin birbirleriyle çakışmayacak ve yerleştirildiği alandan dışarı taşmayacak şekilde yerleştirilmesi problemini ifade etmektedir. Bu problemin amacı, dairelerin yerleştirilmesi sırasında kapladığı alanı (veya daire sayısını) maksimize etmek ve yerleşim sırasında oluşan atık alanları minimize etmektir. Yerleştirilen daireler, kendi aralarında özdeş veya özdeş olmayan türden olmakla birlikte, dairelerin yerleştirildiği alanlar daire, kare, dikdörtgen, üçgen gibi farklı geometrik şekillerde olabilmektedir. DPP’ye yönelik olarak, doğa bilimlerinden mühendislik tasarımına kadar birçok uygulama alanın olduğu söylenebilir. Çalışma kapsamında konuya ilişkin literatür incelendiğinde, tesis planlaması, otomotiv, elektronik, havacılık, savunma sanayi, gıda, inşaat, boya, cam, ahşap sanayi vb. gibi gerçek dünya alanlarında ihtiyaç duyulmaktadır. Bu sebeple son yıllarda DPP ile ilgili çalışmaların literatürde hızlı bir biçimde arttığı görülmektedir. Görülen bu artışla birlikte, çalışmaları bir araya getiren güncel bir literatür çalışmasına ihtiyacın olduğu anlaşılmaktadır. Bu çalışmada, DPP ve bu problemin çözümüyle ilgili kapsamlı bir literatür araştırması ve matematiksel modeller yer almaktadır. Ayrıca dairelerin, daire-kare-dikdörtgen alanlara yerleştirilmesi ile ilgili literatürdeki çalışmalar ayrı ayrı kategorize edilerek araştırmacılara sunulmuştur.

Anahtar Kelimeler

Daire Paketleme Problemi, Kutu Paketleme, Literatür Araştırması

Kaynakça

• [1] M. Chen, X. Tang, T. Song, Z. Zeng, X. Peng, S. Liu, “Greedy heuristic algorithm for packing equal circles into a circular container”, Computer & Industrial Engineering, 119, 114–120, (2018).
• [2] C. O. Lopez, J. E. Beasley, “Packing unequal circles using formulation space search”, Computer & Operations Research, 40, 1276–1288, (2013).
• [3] H. Dyckhoff, “A typology of cutting and packing problems”, European Journal of Operational Research, 44, 145–159, (1990).
• [4] G. Wascher, H. Haußner, H. Schumann, “An improved typology of cutting and packing problems”, European Journal of Operational Research, 183, 1109–1130, (2007).
• [5] M. Hifi, R. M'hallah, “A literature review on circle and sphere packing problems: models and methodologies”, Advances in Operations Research, 150624, 22, (2009).
• [6] G. Malfatti, “Memoria sopra un problema sterotomico”, Memorie di Matematica e di Fisica della Societa Italiana delle Scienze, 10, 235–244, (1803).
• [7] H. Lob, H. W. Richmond, “On the solutions of Malfatti’s problem for triangle” Proceedings of the London Mathematical Society, s2-30, 287-304, (1930).
• [8] K. He, M. Huang, C. Yang, “An action-space-based global optimization algorithm for packing circles into a square container”, Computer & Operations Research, 58, 67–74, (2015).
• [9] P.G. Szabo, M.Cs. Markot, T. Csendes, E. Specht, L.G. Casado, I. Garcia, “New Approaches to Circle Packing in a Square: With Program Codes”, Springer Optimization and Its Applications, Springer, New York, NY, USA, vol.6, (2007).
• [10] E. Specht, “High density packings of equal circles in rectangles with variable aspect ratio”, Computers & Operations Research, 40, 58–69, (2013).
• [11] M. Goldberg, “The packing of equal circles in a square”, Mathematics Magazine, 43, 24-30, (1970).
• [12] J. Schaer, A. Meir, “On a geometric extremum problem”, Canadian Mathematical Bulletin, 8, 21-27, (1965).
• [13] J. Schaer, “The densest packing of nine circles in a square”, Canadian Mathematical Bulletin, 8, 273–277, (1965).
• [14] J. Schaer, “On the packing of ten equal circles in a square”, Mathematics Magazine, 44, 139–140, 1971.
• [15] H. Melissen, “Densest packing of eleven congruent circles in a circle.”, Geometriae Dedicata, 50, 15–25, (1994).
• [16] K. Schlüter, “Kreispackung in Quadraten. In German.”, Elemente der Mathematik, 34, 12-14, (1979).
• [17] G. Valette, “A better packing of ten circles in a square.”, Discrete Mathematics, 76, 57-59, (1989).
• [18] B. Grünbaum, “An improved packing of ten circles in a square.” Manuscript, (1990).
• [19] M. Grannell, “An even better packing of ten equal circles in a square.”, Manuscript, (1990).
• [20] M. Mollard, C. Payan, “Some progress in the packing of equal circles in a square.”, Discrete Mathematics, 84, 303-307, (1990).
• [21] C. de Groot, R. Peikert, D. Würtz, “The optimal packing of ten equal circles in a square.”, IPS Research Report, 90-12, (1990).
• [22] F. Fodor, “The densest packing of 19 congruent circles in a circle.”, Geometriae Dedicata, 74, 139–145, (1999).
• [23] F. Fodor, “The densest packing of 12 congruent circles in a circle.”, Contributions to Algebra and Geometry, 41(2), 401–409, (2000).
• [24] B.D. Lubachevsky, R.L. Graham, “Curved hexagonal packings of equal disks in a circle”, Discrete & Computational Geometry, 18, 179-194, (1997).
• [25] R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Östergard, “Dense packings of congruent circles in a circle”, Discrete Mathematics, 181, 139–154, (1998).
• [26] M. Locatelli, U. Raber, “Packing equal circles in a square: a deterministic global optimization approach”, Discrete Applied Mathematics, 122, 139-166, (2002).
• [27] N. Mladenovic, F. Plastria, D.Urosevic, ”Reformulation descent applied to circle packing problems”, Computers&Operations Research, 32, 2419–2434, (2005).
• [28] J. Liu, S. Xue, Z. Liu, D. Xu, “An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle”, Computers&Industrial Engineering, 57(3), 1144–1149, (2009).
• [29] E.G. Birgin, J.M. Gentil, “New and improved results for packing identical unitary radius circles within triangles, rectangles and strips”, Computers&Operations Research, 37(7), 1318–1327, (2010).
• [30] W. Huang, T. Ye, “Global optimization method for finding dense packings of equal circles in a circle”, European Journal of Operational Research, 210, 474–481, (2011).
• [31] S.I. Galiev, M.S. Lisafina, “Linear models for the approximate solution of the problem of packing equal circles into a given domain”, European Journal of Operational Research. 230, 505-514, (2013).
• [32] K. He, H. Ye, Z. Wang, J. Liu, ”An efficient quasi-physical quasi-human algorithm for packing equal circles in a circular container”, Computers and Operations Research, 92, 26–36, (2018).
• [33] H. Wang, W. Huang, Q. Zhang, D. Xu, “An improved algorithm for the packing of unequal circles within a larger containing circle”, European Journal of Operational Research, 141, 440–453, (2002).
• [34] H. Wenqi, K. Yan, “A short note on a simple search heuristic for the diskspacking problem”, Annals of Operations Research, 131, 101–108, (2004).
• [35] D. Zhang, A. Deng, “An efective hybrid algorithm for the problem of packing circles into a larger containing circle”, Computers & Operations Research, 32, 1941–1951, (2005).
• [36] W. Huang, Y. Li, H. Akeb, C. Li, “36] algorithms for packing unequal circles into a rectangular container”, Journal of the Operational Research Society, 56(5), (2005).
• [37] H. Akeb, M. Hifi, R. M’Hallah, “A beam search algorithm for circular packing problem”, Computers & Operations Research, 36, 1513–1528, (2009).
• [38] H. Akeb, M. Hifi, S. Negre, “An augmented beam search-based algorithm for the circular open dimension problem”, Computers & Industrial Engineering, 61, 373–381, (2011).
• [39] Y.J. Ahm, C.M. Hoffmann, P. Rosen, “A note on circles packing”, Computers & Electronics, 13(8), 559-564, (2012).
• [40] C.O. Lopez, J.E. Beasley, “Packing unequal circles using formulation space search.”, Computers & Operations Research, 40, 1276–1288, (2013).
• [41] C. Francesco, C. Cerrone, R. Cerulli, “A tabu search approach for the circle packing problem”, Network-Based Information Systems (NBiS) 17th International Conference, Salerno, Italy, 165-171, (2014).
• [42] E.Specht, “A precise algorithm to detect voids in polydisperse circle packings”, Proc. R. Soc. A 471, (2015).
• [43] C.O. Lopez, J.E. Beasley, “A formulation space search heuristic for packing unequal circles in a fixed size circular container”, European Journal of Operational Research, 251, 64-73, (2016).
• [44] G. L. Orick, K, Stephenson, C. Collins, “A linearized circle packing algorithm”, Computational Geometry, 64, 13–29, (2017).
• [45] Y. Wang, Y. Wang, J. Sun, C. Huang, X. Zhang, “A stimulus – response - based allocation method for the circle packing problem with equilibrium constraints”, Physica A, 522, 232–247, (2019).
• [46] R. L. Graham, B. D. Lubachevsky, “Dense packings of equal disks in an equilateral triangle: from 22 to 34 and beyond”, The Electronic J. of Combinatorics,2, (1995).
• [47] E. G. Birgin, L. H. Bustamante, H. F. Callisaya, J. M. Martinez, “Packing circles within ellipses”, Internatıonal Transactions Inoperational Research, 20, 365–389, (2013).
• [48] K. A. Dowsland “Optimising the palletisation of cylinders in cases”, OR Spektrum, 13, 204-212, (1991).
• [49] J. A. George, J. M. George, B. W. Lamar, “Packing different-sized circles into a rectangular container”, European Journal of Operational Research, 84, 693-712, (1995).
• [50] M. H. Correia, J. F. Oliveira, J. S. Ferreira, “Cylinder packing by simulated annealing”, Pesquisa Operacional, 20(2), 269-286, (2000).
• [51] E. G. Birgin, J. M. Martinez, D. P. Ronconi, “Optimizing the packing of cylinders into a rectangular container: A nonlinear approach”, European Journal of Operational Research, 160(1), 19-33, (2005).
• [52] K. A. Dowsland, M. Gilbert, G. Kendall, “A local search approach to a circle cutting problem arising in the motor cycle industry”, Journal of the Operational Research Society, 58(4), 429-438, (2007).
• [53] Y. Stoyan, G. Yaskov, “Packing unequal circles into a strip of minimal length with a jump algorithm”, Optimization Letters, 8(3), 949–970, (2014).
• [54] R. Peikert, D.Würtz, M. Monagan, C. de Groot“Packing circles in a square: A review and new results”, Lecture Notes in Control and Information Sciences, 180, 45-52, (1992).
• [55] Z. Drezner, E. Erkut, “Solving the continuous p-dispersion problem using non-linear programming”, The Journal of the Operational Research Society, 46(4), 516-520, (1995).
• [56] V. E. Theodoracatos, J. L. Grimsley, “The optimal packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules”, Computer Methods in Applied Mechanics Engineering, 125, 53-70, (1995).
• [57] K. J. Nurmela, P. R. J. Östergard, “Packing up to 50 equal circles in a square”, Discrete&Computational Geometry, 18, 111–120 (1997).
• [58] D. W. Boll, J. Donovan, R. L. Graham, B. D. Lubachevsky, “Improving dense packing of equal disks in a square”, The electronic journal of combinatorics, 7, (2000).
• [59] M. C. Markot, T. Csendes, “A new verified optimization technique for the packing circles in a unit square problems”, SIAM Journal on Optimization, 16(1), 193-219, (2005).
• [60] A. Costa, P. Hansen, L. Liberti, “On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square”, Discrete Applied Mathematics, 161, 96–106, (2013).
• [61] Z. Zeng, X. Yu, M. Chen, Y. Liu, “A memetic algorithm to pack unequal circles into a square”, Computers and Operations Research, 92, 47–55, (2018).
• [62] J. J. Flores, J. Martínez, F. Calderon, “Evolutionary computation solutions to the circle packing problem”, Soft. Comput, 20, 1521–1535, (2016).
• [63] W. Q. Huang, Y. Li, B. Jurkowiak, C. M. Li, R. C. Xu, “A two-level search strategy for packing unequal circles into a circle container.” Conference: Principles and Practice of Constraint Programming - CP 2003, 9th International, Kinsale, Ireland, 2833, 868–872, (2003).
• [64] M. Hifi, R. M’Hallah, “Approximate algorithms for constrained circular cutting problems” Computers&Operations Research, 31(5), 675–694, (2004).
• [65] Z. Lü, W. Huang, “Perm for solving circle packing problem”, Computers&Operataions Research, 35(5), 1742–1755, (2008).
• [66] H. Akeb, M. Hifi, “A hybrid beam search looking-ahead algorithm for the circular packing problem”, Journal of Combinatorial Optimization, 20(2), 101-130, (2010).
• [67] D. Zhang, A. Deng, “An effective hybrid algorithm for the problem of packing circles into a larger containing circle”, Computers& Operations Research, 32, 1941–1951, (2005).
• [68] M. H. Correia, J. F. Oliveira, J. S. Ferreira, “A new upper bound fort he cylinder packing problem”, Intl. Trans. İn Op. Res, 8, 571-583, (2001).
• [69] M. Hifi, V. T. Paschos, V. Zissimopoulos, “A simulated annealing approach for the circular cutting problem”, European Journal of Operational Research, 159, 430-448, (2004).
• [70] Y. G. Stoyan, G. Yaskov, “A matematical model and a solution method for the problem of placing various-sized circles into a strip”, European Journal of Operational Research, 156, 590–600, (2004).
• [71] D. Zhang, Y. Liu, S. Chen, “Packing Different-sized Circles into a Rectangular Container Using Simulated Annealing Algorithm”, International Conference on Computational Intelligence, Istanbul, Turkey, 388-391, (2004).
• [72] Y. He, Y. Wu, “Packing non-identical circles within a rectangle with open length”, Journal of Global Optimization, 56, 1187-1215, (2013).
• [73] D. Zhang, W. Huang, “A Simulated Annealing Algorithm for the Circles Packing Problem”, Conference: Computational Science - ICCS 2004, 4th International Conference, Kraków, Poland, 3036, 206-214, (2004).
• [74] R. Torres-Escobar, J. A. Marmolejo-Saucedo, I. Litvinchev, P. Vasant, “Monkey Algorithm for Packing Circles with Binary Variables”, Intelligent Computing & Optimization, 547-559, (2019).
• [75] K. He, M. Zhang, J. Zhou, Y. Jin, C. Li, “Stochastic Item Descent Method for Large Scale Equal Circle Packing Problem”, arXiv preprint arXiv:2001.08540, (2020).
• [76] Y. Wang, L. Zhang, “Swarm intelligence labor division algorithm for solving unequal circle packing problem”, Journal of ZheJiang University (Engineering Science) , 53, 2129-2138, (2020).