×

Packing different cuboids with rotations and spheres into a cuboid. (English) Zbl 1307.90217

Summary: The paper considers a packing optimization problem of different spheres and cuboids into a cuboid of the minimal height. Translations and continuous rotations of cuboids are allowed. In the paper, we offer a way of construction of special functions (\(\Phi\)-functions) describing how rotations can be dealt with. These functions permit us to construct the mathematical model of the problem as a classical mathematical programming problem. Basic characteristics of the mathematical model are investigated. When solving the problem, the characteristics allow us to apply a number of original and state-of-the-art efficient methods of local and global optimization. Numerical examples of packing from 20 to 300 geometric objects are given.

MSC:

90C90 Applications of mathematical programming
05C10 Planar graphs; geometric and topological aspects of graph theory
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Sriramya and B. Varthini Parvatha, “A state-of-the-art review of bin packing techniques,” European Journal of Scientific Research, vol. 86, no. 3, pp. 360-364, 2012.
[2] J. Egeblad, B. K. Nielsen, and M. Brazil, “Translational packing of arbitrary polytopes,” Computational Geometry, vol. 42, no. 4, pp. 269-288, 2009. · Zbl 1178.90286 · doi:10.1016/j.comgeo.2008.06.003
[3] M. Gan, N. Gopinathan, X. Jia, and R. A. Williams, “Predicting packing characteristics of particles of arbitrary shapes,” KONA, vol. 22, pp. 82-93, 2004.
[4] S. Torquato and Y. Jiao, “Dense packings of polyhedra: platonic and Archimedean solids,” Physical Review E, vol. 80, no. 4, Article ID 041104, 21 pages, 2009.
[5] S. Torquato and F. H. Stillinger, “Jammed hard-particle packings: from Kepler to Bernal and beyond,” Reviews of Modern Physics, vol. 82, no. 3, pp. 2633-2672, 2010.
[6] http://www.smartimtech.com/.
[7] F. Maggi, S. Stafford, T. L. Jackson, and J. Buckmaster, “Nature of packs used in propellant modeling,” Physical Review E, vol. 77, no. 4, Article ID 046107, 2008.
[8] F. Eisenbrand, S. Funke, A. Karrenbauer, J. Reichel, and E. Schömer, “Packing a trunk-now with a twist!,” in Proceedings of ACM Symposium on Solid and Physical Modeling (SPM ’05), pp. 197-206, New York, NY, USA, June 2005.
[9] J. Cagan, K. Shimada, and S. Yin, “A survey of computational approaches to three-dimensional layout problems,” CAD Computer Aided Design, vol. 34, no. 8, pp. 597-611, 2002.
[10] H. Minkowski, “Dichteste gitterformige Lagerung kongruenter Kbrper,” Nachrichten der Konig. Gesellschaft der Wissenschaften zu Gottingen, vol. 5, pp. 311-355, 1904. · JFM 35.0508.02
[11] U. Betke and M. Henk, “Densest lattice packings of 3-polytopes,” Computational Geometry, vol. 16, no. 3, pp. 157-186, 2000. · Zbl 1133.52307 · doi:10.1016/S0925-7721(00)00007-9
[12] G. Fasano, “MIP-based heuristic for non-standard 3D-packing problems,” 4OR, vol. 6, no. 3, pp. 291-310, 2008. · Zbl 1175.90428 · doi:10.1007/s10288-007-0049-1
[13] G. Fasano, “A global optimization point of view to handle non-standard object packing problems,” Journal of Global Optimization, vol. 55, no. 2, pp. 279-299, 2012. · Zbl 1268.90062 · doi:10.1007/s10898-012-9865-8
[14] J. A. Bennell and J. F. Oliveira, “The geometry of nesting problems: a tutorial,” European Journal of Operational Research, vol. 184, no. 2, pp. 397-415, 2008. · Zbl 1136.90030 · doi:10.1016/j.ejor.2006.11.038
[15] N. Chernov, Y. Stoyan, and T. Romanova, “Mathematical model and efficient algorithms for object packing problem,” Computational Geometry, vol. 43, no. 5, pp. 535-553, 2010. · Zbl 1228.05117 · doi:10.1016/j.comgeo.2009.12.003
[16] G. Scheithauer, Y. G. Stoyan, and T. Y. Romanova, “Mathematical modeling of interactions of primary geometric 3D objects,” Cybernetics and Systems Analysis, vol. 41, no. 3, pp. 332-342, 2005. · Zbl 1102.68684 · doi:10.1007/s10559-005-0067-y
[17] Y. Stoyan, J. Terno, G. Scheithauer, M. Gil, and T. Romanova, “Construction of a Phi-function for two convex polytopes,” Applicationes Mathematicae, vol. 29, no. 2, pp. 199-218, 2002. · Zbl 1053.90009 · doi:10.4064/am29-2-6
[18] N. Chernov, Y. Stoyan, T. Romanova, and A. Pankratov, “Phi-functions for 2D objects formed by line segments and circular arcs,” Advances in Operations Research, vol. 2012, Article ID 346358, 26 pages, 2012. · Zbl 1246.90127 · doi:10.1155/2012/346358
[19] G. Yu. Stoyan and A. M. Chugay, “Mathematical modeling of the interaction of non-oriented convex polytopes,” Cybernetics and Systems Analysis, vol. 48, no. 6, pp. 837-845, 2012. · Zbl 1308.52010 · doi:10.1007/s10559-012-9463-2
[20] Y. G. Stoyan, M. V. Novozhilova, and A. V. Kartashov, “Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem,” European Journal of Operational Research, vol. 92, no. 1, pp. 193-210, 1996. · Zbl 0916.90234 · doi:10.1016/0377-2217(95)00038-0
[21] J. K. Lenstra and A. H. G. Rinnooy, “Complexity of packing, covering, and partitioning problems,” in Packing and Covering in Combinatorics, A. Schrijver, Ed., pp. 275-291, Mathematisch Centrum, Amsterdam, The Netherlands, 1979. · Zbl 0438.05024
[22] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2009, 3rd edition. · Zbl 1187.68679
[23] Y. Stoyan and A. Chugay, “Packing cylinders and rectangular parallelepipeds with distances between them into a given region,” European Journal of Operational Research, vol. 197, no. 2, pp. 446-455, 2009. · Zbl 1159.90487 · doi:10.1016/j.ejor.2008.07.003
[24] G. Zoutendijk, Nonlinear Programming, Computational Methods, Integer and Nonlinear Programming, North Holland, Amsterdam, The Netherlands, 1970. · Zbl 0336.90057
[25] E. Polak, Optimization: Algorithms and Consistent Approximations, Springer, New York, NY, USA, 1997. · Zbl 0899.90148
[26] Y. G. Stoyan, M. V. Zlotnik, and A. M. Chugay, “Solving an optimization packing problem of circles and non-convex polygons with rotations into a multiply connected region,” Journal of the Operational Research Society, vol. 63, no. 3, pp. 379-391, 2012.
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.