Received 29.09.2023; Revised 15.10.2023; Accepted 28.11.2023

Published 04.12.2023; First Online 05.12.2023

https://doi.org/10.34229/2707-451X.23.4.4

Previous  |  FULL TEXT (in Ukrainian)  |  Next

 

MSC 90B85

Optimization of Packing Irregular Three-Dimensional Objects

Tetyana Romanova ^{1, 2 *} ,   Andrii Chuhai ^{1, 3},   Oleksandr Pankratov ¹,   Georgiy Yaskov ¹,   Yuriy Stoyan ¹

¹ Anatolii Pidhornyi Institute of Mechanical Engineering Problems of the NAS of Ukraine, Kharkiv

² University of Leeds, UK

³ Simon Kuznets Kharkiv National University of Economics, Ukraine

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. Nowadays the irregular packing problem is becoming more important, since effective space management and optimal arrangement of objects are becoming key factors for ensuring efficiency and saving resources in a wide range of applications, e.g., additive manufacturing, space engineering, material sciences and logistics. It becomes an integral part of strategic development in the fields of production and science.

The purpose of the paper. The paper is devoted to construction of a mathematical model and development of an efficient technique for densely filling a container with the maximum number of sets of irregular three-dimensional objects.

Results. Irregular objects are approximated with a certain accuracy by non-convex polyhedra, which can be represented by the union of convex polytopes. Non-overlapping and containment constraints are described using quasi-phi-functions and phi-functions. A mathematical model of the packing problem is provided as a mixed-integer nonlinear programming considering given proportions of different types of objects. A solution strategy is proposed to search for local-optimal solutions. To find reasonable feasible packing, a fast algorithm based on a strip approximation of objects is used. A numerical example of the development of a print map of a set of industrial parts with maximum filling of the working chamber of a 3D-printer is given.

Conclusions. The results confirm the efficiency of the proposed packing strategy, which is based on an integrated approach that takes into account the geometric features of irregular objects and their completeness.

 

Keywords: packing, irregular objects, set of parts, mathematical modeling, optimization, 3D-printing.

 

Cite as: Romanova T., Chuhai A., Pankratov O., Yaskov G., Stoyan Y. Optimization of Packing Irregular Three-Dimensional Objects. Cybernetics and Computer Technologies. 2023. 4. P. 25–33. (in Ukrainian) https://doi.org/10.34229/2707-451X.23.4.4

 

References

           1.     Araújo L.J.P., Özcan E., Atkin J.A.D, Baumersumers M. Analysis of irregular three-dimentional packing problems in additive manufacturing: a new taxonomy and dataset. International of Production Research. 2019. 57 (18). P. 5920–5934. https://doi.org/10.1080/00207543.2018.1534016

           2.     Lamas-Fernandez C., Bennell J., Sykora A. Voxel Based Solution Approaches to the Three-Dimensional Irregular Packing Problem. Operations Research. 2022. 71 (4). https://doi.org/10.1287/opre.2022.2260

           3.     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). P. 380–390. https://doi.org/10.1631/FITEE.1400421

           4.     Ma Y., Chen Z., Hu W., Wang W. Packing irregular objects in 3D space via hybrid optimization. Comp. Graph. Forum (SGP). 2018. 37 (5). P. 49–59. https://doi.org/10.1111/cgf.13490

           5.     Romanova T., Bennell J., Stoyan Y., Pankratov A. Packing of concave polyhedra with continuous rotations using nonlinear optimisation. European Journal of Operational Research. 2018. 268 (1). P. 37–53. https://doi.org/10.1016/j.ejor.2018.01.025

           6.     Leao A., Toledo F., Oliveira J., Carravilla M., et al. Irregular packing problems: a review of mathematical models. Eur. J. Oper. Res. 2020. 282 (3). P. 803–822. https://doi.org/10.1016/j.ejor.2019.04.045

           7.     Сui Q., Rong V., Chen D., Matusik W. Dense, Interlocking-Free and Scalable Spectral Packing of Generic3D Objects. ACM Trans.Graph. 2023. 42 (4). P. 1–14. https://doi.org/10.1145/3592126

           8.     Stoyan Y., Romanova T., Pankratov A., Chugay A. Optimized object packings using quasi-phi-functions. Optimized packings with applications. 2015. P. 265–293. https://doi.org/10.1007/978-3-319-18899-7_13

           9.     Chernov N., Stoyan Y., Romanova T. Mathematical model and efficient algorithms for object packing problem. Comput. Geom.: Theory and Appl. 2010. 43 (9). P. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003

       10.     Stoyan Yu., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization. 2016. 65 (2). P. 283–307. https://doi.org/10.1007/s10898-015-0331-2

       11.     Grebennik I.V., Pankratov A.V., Chugay A.M., Baranov A.V. Packing n-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an n-dimensional parallelepiped. Cybernetics and Systems Analysis. 2010. 46. P. 793–802. https://doi.org/10.1007/s10559-010-9260-8

       12.     Kubach T., Bortfeldt A., Tilli T., Gehring H. Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid. Asia-Pacific Journal of Operational Research. 2011. 28 (06). P. 739–753. https://doi.org/10.1142/S0217595911003326

       13.     Vanek J., Galicia J.A.G., Benes B., Měch R., Carr N., Stava O., Miller G.S. Packmerger: A 3D print volume optimizer. In Computer Graphics Forum 2014, 33.Wiley Online Library. P. 322–332. https://doi.org/10.1111/cgf.12353

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT (in Ukrainian)  |  Next