Methodology to Solve Optimal Placement Problems for 3D Objects

Authors

Yurii H. Stoian, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharskyi St., Kharkiv, 61046, Ukraine), e-mail: stoyan@ipmach.kharkov.ua, ORCID: 0000-0002-8053-0276

Andrii M. Chuhai, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharskyi St., Kharkiv, 61046, Ukraine), e-mail: chugay.andrey80@gmail.com, ORCID: 0000-0002-4079-5632

Abstract

This paper is devoted to solving optimization problems of packing 3D objects both by constructing exact mathematical models and by developing approaches based on the application of non-linear optimization methods and modern solvers. Developed are constructive tools for both mathematical and computer modeling of relations between oriented and non-oriented 3D objects, whose boundaries are formed by cylindrical, conical, and spherical surfaces and planes in the form of new classes of both Stoyan’s Φ-functions (further referred to as phi-functions) and quasi-phi-functions. Based on the developed mathematical modeling tools, constructed and investigated is the basic mathematical model of the problem of optimally packing 3D objects, whose boundaries are formed by cylindrical, conical, and spherical surfaces and planes, as well as the model’s various implementations, which cover a wide class of scientific and applied problems of packing 3D objects. Developed is the methodology for solving the problems of packing 3D objects that allow both continuous rotations and translations at the same time. Proposed are strategies, methods and algorithms for solving the optimization problems of packing 3D objects with taking into account technological constraints (minimum admissible distances, prohibited zones, the possibility of continuous translations and rotations). On the basis of the proposed mathematical modeling tools, mathematical models, methods, and algorithms, developed is the software that uses parallel computing technology to automatically solve the optimization problems of packing 3D objects. The results obtained can be used for solving problems of optimizing layout solutions; for computer modeling in materials science, powder metallurgy, and nanotechnologies; in optimizing the 3D printing process for the SLS technology of additive production; in information and logistics systems that optimize transportation and storage of goods.

Keywords: packing, 3D objects, geometric design, phi-functions, mathematical modeling, continuous rotations, nonlinear optimization.

Full text: Download in PDF

References

1. Petrov, M. S., Gaidukov, V. V., & Kadushnikov, R. M. (2004). Numerical method for modelling the microstructure of granular materials. Powder Metallurgy and Metal Ceramics, no. 43, pp. 330–335. https://doi.org/10.1023/B:PMMC.0000048126.87171.f9.
2. Wang, Y., Lin, C. L., & Miller, J. D. (2016). 3D image segmentation for analysis of multisize particles in a packed particle bed. Powder Technology, vol. 301, pp. 160–168. https://doi.org/10.1016/j.powtec.2016.05.012.
3. Verkhoturov, M., Petunin, A., Verkhoturova, G., Danilov, K., & Kurennov, D. (2016). The 3D object packing problem into a parallelepiped container based on discrete-logical representation. IFAC-PapersOnLine, vol. 49, iss. 12, pp. 1–5. https://doi.org/10.1016/j.ifacol.2016.07.540.
4. Karabulut, K. A. & İnceoğlu, M. (2004). Hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method. Advances in Information Systems, no. 3261, pp. 441–450. https://doi.org/10.1007/978-3-540-30198-1_45.
5. Cao, P., Fan, Z., Gao, R., & Tang, J. (2016). Complex housing: modelling and optimization using an improved multi-objective simulated annealing algorithm. Proceedings of ASME, no. 60563, V02BT03A034. https://doi.org/10.1115/DETC2016-60563.
6. Guangqiang, L., Fengqiang, Z., Rubo, Z., Jialu, Du., Chen, G., & Yiran, Z. (2016). Parallel particle bee colony algorithm approach to layout optimization. Journal of Computational and Theoretical Nanoscience, vol. 13, no. 7, pp. 4151–4157. https://doi.org/10.1166/jctn.2016.5263.
7. Torczon, V. & Trosset, M. W. (1998). From evolutionary operation to parallel direct search: Pattern search algorithms for numerical optimization. Computing Science and Statistics, vol. 29, pp. 396–401.
8. Birgin, E. G., Lobato, R. D., & Martіnez, J. M. (2016). Packing ellipsoids by nonlinear optimization. Journal of Global Optimization, no. 65, pp. 709–743. https://doi.org/10.1007/s10898-015-0395-z.
9. Stoyan, Y., Pankratov, A., & Romanova, T. (2016). Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization, no. 65 (2), pp. 283–307. https://doi.org/10.1007/s10898-015-0331-2.
10. Fasano, G. A. (2013). Global optimization point of view to handle non-standard object packing problems. Journal of Global Optimization, no. 55 (2), pp. 279–299. https://doi.org/10.1007/s10898-012-9865-8.
11. Egeblad, J., Nielsen, B. K., & Brazil, M. (2009). Translational packing of arbitrary polytopes. Computational Geometry: Theory and Applications, vol. 42, iss. 4, pp. 269–288. https://doi.org/10.1016/j.comgeo.2008.06.003.
12. Liu, X., Liu, J., Cao, A., Yao, Z. (2015). HAPE3D ‑ a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Technology and Electronic Engineering, no. 16 (5), pp. 380–390. https://doi.org/10.1631/FITEE.1400421.
13. Youn-Kyoung, J. & Sang, D. N. (2014). Intelligent 3D packing using a grouping algorithm for automotive container engineering. Journal of Computational Design and Engineering, vol. 1, iss. 2, pp. 140–151. https://doi.org/10.7315/JCDE.2014.014.
14. Kallrath, J. (2017). Packing ellipsoids into volume-minimizing rectangular boxes. Journal of Global Optimization, no. 67, pp. 151–185. https://doi.org/10.1007/s10898-015-0348-6.
15. Stoyan, Y. G. & Chugay, A. M. (2014). Packing different cuboids with rotations and spheres into a cuboid. Advances in Decision Sciences, vol. 2014, 571743, 19 p. https://doi.org/10.1155/2014/571743.
16. Stoyan, Y. G., Semkin, V. V., & Chugay, A. M. (2016). Modeling close packing of 3D objects. Cybernetics and Systems Analysis, no. 52, pp. 296–304. https://doi.org/10.1007/s10559-016-9826-1.
17. Pankratov, O., Romanova, T., Stoyan, Y., & Chuhai, A. (2016). Optimization of packing polyhedra in spherical and cylindrical containers. Eastern-European Journal of Enterprise Technology, vol. 1, no. 4 (79), pp. 39–47. https://doi.org/10.15587/1729-4061.2016.60847.
18. Stoyan, Y. G. & Chugay, A. M. (2012). Mathematical modeling of the interaction of non-oriented convex polytopes. Cybernetic Systems Analysis, no. 48, pp. 837–845. https://doi.org/10.1007/s10559-012-9463-2.
19. Chugay, A. M. (2005). Resheniye zadachi upakovki krugov v vypuklyy mnogougolnik s pomoshchyu modifitsirovannogo metoda suzhayushchikhsya okrestnostey [Solution of the problem of packing circles into a convex polygon using the modified method of tapering neighborhoods]. Radioelektronika i informatika – Radioelectronics and Informatics, no. 1, pp. 58–63 (in Russian).
20. Stoian, Y. E., Chugay, A. M., & Pankratov, A. V. (2018). Two approaches to modeling and solving the packing problem for convex polytopes. Cybernetics and Systems Analysis, no. 54, pp. 585–593. https://doi.org/10.1007/s10559-018-0059-3.

Received 11 February 2020

Published 30 June 2020