Abstract
We consider the problem of packing convex polytopes in a cuboid of minimum volume. To describe analytically the non-overlapping constraints for convex polytopes that allow continuous translations and rotations, we use phi-functions and quasi-phi-functions. We provide an exact mathematical model in the form of an NLP-problem and analyze its characteristics. Based on the general solution strategy, we propose two approaches that take into account peculiarities of phi-functions and quasi-phi-functions. Computational results to compare the efficiency of our approaches are given with respect to both the value of the objective function and runtime.
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(2), 114–119 (2010).
K. Karabulut and M. Ínceğlu, “A hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method,” Advances in Information Systems, Vol. 3261, 441–450 (2004).
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 Conf. and Computers and Information in Engineering Conf. (August 02, 2015), Vol. 2A: 41st Design Automation Conference, V02AT03A052 (2015), DOI: https://doi.org/10.1115/DETC2015-47670.
L. Guangqiang, Z. Fengqiang, Z. Rubo, Du Jialu Du., G. Chen, and Z. Yiran, “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, Iss. 4, 709–743 (2016).
G. A. Fasano, “Global optimization point of view for non-standard packing problems,” J. of Global Optimization, Vol. 55, Iss. 2, 279–299 (2013).
M. Verkhoturov, A. Petunin, G. Verkhoturova, K. Danilov, and D. Kurennov, “The 3D object packing problem into a parallelepiped container based on discrete-logical representation,” IFAC-PapersOnLine, Vol. 49, No. 12, 001–005 (2016).
J. Egeblad, B. K. Nielse, and A. Odgaar, “Fast neighborhood search for two- and three-dimensional nesting problems,” Europ. J. of Operations Research, Vol. 183, Iss. 3, 1249–1266 (2007).
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).
Y. Stoyan and T. Romanova, “Mathematical models of placement optimization: Two- and three-dimensional problems and applications,” in: Springer Optimization and Its Applications, Vol. 73, 363–388 (2013).
Y. G. Stoyan, T. Romanova, A. Pankratov, and A. Chugay, “Optimized object packings using quasi-phi-functions,” in: Springer Optimization and Its Applications, Vol. 105, 265–293 (2015).
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. Stoyan, A. Pankratov, and T. Romanova, “Quasi-phi-functions and optimal packing of ellipses,” J. of Global Optimization, Vol. 65, Iss. 2, 283–307 (2016).
Y. G. Stoyan and A. M. Chugay, “Packing different cuboids with rotations and spheres into a cuboid,” Advances in Decision Sciences, Vol. 2014, Article ID 571743 (2014), DOI: https://doi.org/10.1155/2014/571743.
T. Romanova, J. Bennell, Y. Stoyan, and A. Pankratov, “Packing of concave polyhedra with continuous rotations using nonlinear optimization,” Europ. J. of Operational Research, Vol. 268, Iss. 1, 37–53 (2018).
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).
A. Wachter and L. T. Biegler, “On the implementation of an interior-pointfilter line-search algorithm for large-scale nonlinear programming,” Mathematical Programming, Vol. 106, Iss. 1, 25–57 (2006).
Yu. Stoyan, T. Romanova, A. Pankratov, A. Kovalenko, and P. Stetsyuk, “Balance layout problems: Mathematical modeling and nonlinear optimization,” in: G. Fasano and J. Pintér (eds.), Space Engineering. Modeling and Optimization with Case Studies. Springer Optimization and its Applications, Vol. 114, XV, Springer, New York (2016), pp. 369–400.
A. Pankratov, T. Romanova, Y. Stoian, and A. Chugay, “Problem of optimization packing of polytopes within spherical and cylindrical containers,” Eastern-Europ. J. of Enterprise Technologies, No. 1, 39–47 (2016).
S. V. Yakovlev, “The method of artificial dilation in problems of optimal packing of geometric objects,” Cybern. Syst. Analysis, Vol. 53, No. 5, 725–731 (2017).
I. V. Grebennik, A. A. Kovalenko, T. E. Romanova, I. A. Urniaeva, and S. B. Shekhovtsov, “Combinatorial configurations in balance layout optimization problems,” Cybern. Syst. Analysis, Vol. 54, No. 2, 221– 231 (2018).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 4, July–August, 2018, pp. 81–90.
Rights and permissions
About this article
Cite this article
Stoian, Y.E., Chugay, A.M., Pankratov, A.V. et al. Two Approaches to Modeling and Solving the Packing Problem for Convex Polytopes. Cybern Syst Anal 54, 585–593 (2018). https://doi.org/10.1007/s10559-018-0059-3
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-018-0059-3