Methodology to Solve Optimal Placement Problems for 3D Objects

Authors

Keywords:

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

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.

Author Biographies

Andrii M. Chuhai, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharskyi St., Kharkiv, 61046, Ukraine)

D. Sc. (Engineering)

Yurii H. Stoian, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharskyi St., Kharkiv, 61046, Ukraine)

D. Sc. (Engineering), Associate Member of NASU

References

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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).

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.

Downloads

Published

2020-06-29

Issue

Vol. 23 No. 2 (2020)

Section

Applied mathematics

License

Copyright (c) 2020 Andrii M. Chuhai, Yurii H. Stoian

Creative Commons License

This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

All authors agree with the following conditions:

  • The authors reserve the right to claim authorship of their work and transfer to the journal the right of first publication of the work under the license agreement (the agreement).
  • Authors have a right to conclude independently additional agreement on non-exclusive spreading the work in the form in which it was published by the jpurnal (for example, to place the work in institution repository or to publish as a part of a monograph), providing a link to the first publication of the work in this journal.
  • Journal policy allows authors to place the manuscript in the Internet (for example, in the institution repository or on a personal web sites) both before its submission to the editorial board and during its editorial processing, as this ensures the productive scientific discussion and impact positively on the efficiency and dynamics of citation of published work (see The Effect of Open Access).