Abstract
The paper considers the problem of packing nonconvex polyhedra into a container of minimum volume. An exact mathematical model of the problem of packing nonconvex polyhedra with continuous translations and rotations is constructed. Characteristics of the mathematical model are analyzed and are used as the basis to develop a multistage solution approach to obtain a nearly optimal solution, which is not the global minimum but is a proved local minimum. Numerical examples are given.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Y. Wang, C. L. Lin, and J. D. Miller, “3D image segmentation for analysis of multisize particles in a packed particle bed,” Powder Technology, Vol. 301, 160–168 (2016).
A. C. J. Korte and H. J. H. Brouwers, “Random packing of digitized particles,” Powder Technology, Vol. 233, 319–324 (2013).
S. X. Li, J. Zhao, P. Lu, and Y. Xie, “Maximum packing densities of basic 3D objects,” China Science Bulletin, Vol. 55, Iss. 2, 114–119 (2010).
K. Karabulut and M. Ínceoğlu, “A hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method,” in: T. Yakhno (ed.), Advances in Information Systems, ADVIS 2004, Lecture Notes in Computer Science, Vol. 3261, Springer, Berlin–Heidelberg (2004), pp. 441–450.
Pei Cao, Zhaoyan Fan, Robert Gao, and Jiong Tang, “A multi-objective simulated annealing approach towards 3D packing problems with strong constraints,” in: ASME 2015, Intern. Design Engineering Technical Conferences and Computers and Information in Engineering Conf., Vol. 2A, Paper No. DETC2015-47670, V02AT03A052 (2015). https://doi.org/https://doi.org/10.1115/DETC2015-47670.
Guangqiang Li, Fengqiang Zhao, Rubo Zhang, Jialu Du, Chen Guo, and Yiran Zhou, “A parallel particle bee colony algorithm approach to layout optimization,” J. of Computational and Theoretical Nanoscience, Vol. 13, No. 7, 4151–4157 (2016).
V. Torczon and M. Trosset, “From evolutionary operation to parallel direct search: Pattern search algorithms for numerical optimization,” Computing Science and Statistics, Vol. 29, 396–401 (1998).
E. G. Birgin, R. D. Lobato, and J. M. Martinez, “Packing ellipsoids by nonlinear optimization,” J. of Global Optimization, Vol. 65, 709–743 (2016).
G. A. Fasano, “Global optimization point of view for non-standard packing problems,” J. of Global Optimization, Vol. 55, 279–299 (2013).
Y. G. Stoyan, V. V. Semkin, and A. M. Chugay, “Optimization of 3D objects layout into a multiply connected domain with account for shortest distances,” Cybern. Syst. Analysis, Vol. 50, No. 3, 374–385 (2014).
I. V. Grebennik, A. V. Pankratov, A. M. Chugay, and A. V. Baranov, “Packing n-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an n-dimensional parallelepiped,” Cybern. Syst. Analysis, Vol. 46, No. 5, 393–802 (2010).
X. Liu, J. Liu, and A. Cao, “HAPE3D — a new constructive algorithm for the 3D irregular packing problem,” Frontiers Inf. Technol. Electronic Eng., Vol. 16, 380–390 (2015).
N. Chernov, Y. Stoyan, and T. Romanova, “Mathematical model and efficient algorithms for object packing problem,” Computational Geometry, Theory and Application, Vol. 43, Iss. 5, 535–553 (2010).
Y. Stoyan and A. Chugay, “Mathematical modeling of the interaction of non-oriented convex polytopes,” Cybern. Syst. Analysis, Vol. 48, No. 6, 837–845 (2012).
Y. G. Stoyan and A. M. Chugay, “Packing different cuboids with rotations and spheres into a cuboid,” in: Advances in Decision Sciences (2014). URL: https://www.hindawi.com/journals/ads/2014/571743.
Y. G. Stoyan, V. V. Semkin, and A. M. Chugay, “Modeling close packing of 3D objects,” Cybern. Syst. Analysis, Vol. 52, No. 2, 296–304 (2016).
Y. E. Stoian, A. M. Chugay, A. V. Pankratov, and T. E. Romanova, “Two approaches to modeling and solving the packing problem for convex polytopes,” Cybern. Syst. Analysis, Vol. 54, No. 4, 585–593 (2018).
A. Wachter and L. T. Biegler, “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” Mathematical Programming, Vol. 106, Iss. 1, 25–57 (2006).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 2, March–April, 2020, pp. 108–118.
Rights and permissions
About this article
Cite this article
Stoyan, Y.G., Chugay, A.M. Multistage Approach to Solving the Optimization Problem of Packing Nonconvex Polyhedra. Cybern Syst Anal 56, 259–268 (2020). https://doi.org/10.1007/s10559-020-00241-w
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-020-00241-w