Visn. Nac. Akad. Nauk Ukr. 2020.(6): 43-50
https://doi.org/10.15407/visn2020.06.043

Andrey M. Chugay
Pidgorny Institute of Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, Kharkiv
ORCID: https://orcid.org/0000-0002-4079-5632

MATHEMATICAL AND COMPUTER MODELLING OF OPTIMIZATION 3D PACKING PROBLEM
According to the scientific report at the meeting of the Presidium of NAS of Ukraine, March 11, 2020

The research is devoted to the solution of optimization problems of packing three-dimensional bodies by construction exact mathematical models and developing approaches based on the use of optimization methods of non-linear programming and modern solvers. Constructive tools of mathematical modeling and computer modeling of the relationship between oriented and non-oriented three-dimensional bodies which boundary is formed by cylindrical, conical, spherical surfaces and planes in the form of new classes of free of radicals Ф-functions and quasi-Ф-functions are developed. Based on the tools of mathematical modeling the basic mathematical model of the problem of optimal packing of three-dimensional bodies whose boundary is formed by cylindrical, conical, spherical surfaces and planes is constructed and investigated. Also various implementations that cover a wide class of scientific and applied problems of packing three-dimensional bodies are constructed. A general methodology for solving the problems of packing three-dimensional bodies that simultaneously allow continuous rotations and translations are developed. Strategies, methods and algorithms for solving optimization problems of packing three-dimensional bodies with account for technological constraints (minimum permissible distances, prohibition zones, the possibility of continuous translations and rotations) are proposed. Based on the proposed tools of mathematical modeling, mathematical models, methods and algorithms, software using parallel computing technology for automatically solving the optimization problems of packing three-dimensional bodies is created. The results obtained can be used to solve problems of optimization of layout solutions, computer modeling in materials science, powder metallurgy and nanotechnologies, optimization of the 3D printing process for SLS additive production technology, and in information and logistics systems that optimize transportation and storage of goods.
Keywords: packing, three-dimensional bodies, geometric projection, Ф-functions, mathematical modeling, continuous rotations, nonlinear optimization.

Language of article: ukrainian

Full text (PDF)

REFERENCES

1. Petrov M.S., Gaidukov V.V., Kadushnikov R.M., Antonov I.V., Nurkanov E.Yu. Numerical method for modelling the microstructure of granular materials. Powder Metallurgy and Metal Ceramics. 2004. 43(7–8): 330–335. DOI: https://doi.org/10.1023/B:PMMC.0000048126.87171.f9
2. Wang Y., Lin C.L., Miller J.D. 3D image segmentation for analysis of multisize particles in a packed particle bed. Powder Techn. 2016. 301: 160–168. DOI: https://doi.org/10.1016/j.powtec.2016.05.012
3. Verkhoturov M., Petunin A., Verkhoturova G., Danilov K., Kurennov D. The 3D Object Packing Problem into a Parallelepiped Container Based on Discrete-Logical Representation. IFAC-PapersOnLine. 2016. 49(12): 1–5. DOI: https://doi.org/10.1016/j.ifacol.2016.07.540
4. Karabulut K.A., Inceoglu M. Hybrid Genetic Algorithm for Packing in 3D with Deepest Bottom Left with Fill Method. In: Yakhno T. (ed.) Advances in Information Systems. ADVIS-2004. Lecture Notes in Computer Science, Vol. 3261. Springer, Berlin, Heidelberg, 2004. P. 441–450. DOI: https://doi.org/10.1007/978-3-540-30198-1_45
5. Cao P., Fan Z., Gao R., Tang J. Complex Housing: Modelling and Optimization Using an Improved Multi-Objective Simulated Annealing Algorithm. Proc. ASME. 2016. No. 60563, V02BT03A034. DOI: https://doi.org/10.1115/DETC2016-60563
6. Li G., Zhao F., Zhang R., Du J., Guo C., Zhou Y. Parallel Particle Bee Colony Algorithm Approach to Layout Optimization. Journal of Computational and Theoretical Nanoscience. 2016. 13(7): 4151–4157. DOI: https://doi.org/10.1166/jctn.2016.5263
7. Torczon V., Trosset M. From evolutionary operation to parallel direct search: Pattern search algorithms for numerical optimization. Computing Sci. Statistics. 1998. Vol. 29. P. 396–401.
8. Birgin E.G., Lobato R.D., Martіnez J.M. Packing ellipsoids by nonlinear optimization. Journal of Global Optimization. 2016. 65: 709–743. DOI: https://doi.org/10.1007/s10898-015-0395-z
9. Joung Y.-K., Noh D.S. Intelligent 3D packing using a grouping algorithm for automotive container engineering. Journal of Computational Design and Engineering. 2014. 1(2): 140–151. DOI: https://doi.org/10.7315/JCDE.2014.014
10. Fasano G.A. Global optimization point of view to handle non-standard object packing problems. Journal of Global Optimization. 2013. 55(2): 279–299. DOI: https://doi.org/10.1007/s10898-012-9865-8
11. Egeblad J., Nielsen B.K., Brazil M. Translational packing of arbitrary polytopes. Computational Geometry. 2009. 42(4): 269–288. DOI: https://doi.org/10.1007/s10898-012-9865-8
12. Stoyan Y., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization. 2016. 65 (2): 283–307. DOI: https://doi.org/10.1007/s10898-015-0331-2
13. Stoyan Y.G., Chugay A.M. Packing different cuboids with rotations and spheres into a cuboid. Advances in Decision Sciences. 2014. DOI: https://doi.org/10.1155/2014/571743
14. Stoyan Y.G., Semkin V.V., Chugay A.M. Modeling Close Packing of 3D Objects. Cybernetics and Systems Analysis. 2016. 52(2): 296–304. DOI: https://doi.org/10.1007/s10559-016-9826-1
15. Pankratov O., Romanova T., Stoyan Y., Chuhai A. Optimization of packing polyhedra in spherical and cylindrical containers. Eastern-European Journal of Enterprise Technologies. 2016. 1(4): 39–47. DOI: https://doi.org/10.15587/1729-4061.2016.60847
16. Stoyan Y.G., Chugay A.M. Mathematical modeling of the interaction of non-oriented convex polytopes. Cybernetic Systems Analysis. 2012. 48: 837–845. DOI: https://doi.org/10.1007/s10559-012-9463-2
17. Stoian Y.E., Chugay A.M., Pankratov A.V., Romanova T.E. Two Approaches to Modeling and Solving the Packing Problem for Convex Polytopes. Cybernetic Systems Analysis. 2018. 54: 585–593. DOI: https://doi.org/10.1007/s10559-018-0059-3
18. Liu X., Liu J., Cao A., Yao Z. HAPE3D — a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Technology & Electronic Engineering. 2015. 16(5): 380–390. DOI: https://doi.org/10.1631/FITEE.1400421