CLUSTER PACKING OF CONCAVE NON-ORIENTED POLYHEDRA IN A CUBOID
Article Sidebar
Main Article Content
Abstract
The subject matter of the article is the solution of the problem of optimal packing of concave polyhedra in a cuboid of minimal volume. The goal is to construct a mathematical model of the problem under consideration and to develop a solution method. The task to be solved are: to develop tools for mathematical modeling of the interaction of two concave non-oriented polyhedra; to construct a mathematical model of the problem of packing concave non-oriented polyhedra in a cuboid of minimal volume; to investigate the peculiarities of the mathematical model; to develop an effective method of solution and implement its software. The methods used are: the phi-function technique, the internal point method. The following results are obtained. Using the phi-function for two convex non-oriented polyhedra, a phi-function for two concave non-oriented polyhedra is constructed. On the basis of the phi-function, an exact mathematical model of the packing problem for concave polyhedra that allow simultaneous continuous translations and rotations is constructed. The mathematical model is represented as a non-linear programming problem. The properties of the constructed mathematical model are analyzed and a multi-stage approach based on them is proposed, which makes it possible to obtain a good locally optimal solution of the problem posed. Since working with polyhedra is an important to determine the optimal clustering of two objects, one of the stages of the proposed approach is to solve the problem of pairwise clustering of polyhedra. A numerical example demonstrating the effectiveness of the proposed approach is given. Conclusions. The scientific novelty of the obtained results consists in the following: an exact mathematical model of the packing problem of concave non-oriented polyhedra is constructed in the form of a nonlinear optimization problem and a multi-stage approach is proposed that allows obtain a good locally optimal solution of the problem.
Article Details
References
Chugay, A.M., Pankratov, A.V., Romanova, Т.Е. and Stoian, Yu.E. (2017) “Optimization of the process of 3D-printing for SLS technologies of additive production”, Systems of control, navigation and communication, No. 6(46), pp. 127-130.
Wang, Y., Lin, C.L., Miller, J.D. (2016) “3D image segmentation for analysis of multisize particles in a packed particle bed”, Powder Technology. No. 301, pp. 160–168.
Stoyan, Y.G., Romanova, T., Pankratov, A. and Chugay, A. (2015) “Optimized object packings using quasi-phi-functions”, Springer Optimization and Its Applications, Vol. 105, pp. 265-293.
Liu, X., Liu, J. and Cao, A. (2015), “HAPE3D-a new constructive algorithm for the 3D irregular packing problem”, Frontiers Inf Technol Electronic Eng., No. 16., pp. 380-390.
Romanova, T., Bennell, J., Stoyan, Y. and Pankratov, A. (2018) “Packing of concave polyhedra with continuous rotations using nonlinear optimisation”, European Journal of Operational Research, No. 268 (1), pp. 37-53.
Pankratov, A.V. Romanova, T.E. and Chugay, A.M. (2015), “Optimal packing of convex polytopes using quasi-phi-functions, Problems of mechanical engineering, No. 18 (2), pp. 55-65.
Stoyan, Y.G. and Chugay, A.M. (2012), “Mathematical modeling of the interaction of non-oriented convex polytopes”, Cybernetics and Systems Analysis, No. 48 (6). pp. 837-845.
Grebennik, I.V, Pankratov, A.V., Chugay, A.M. and Baranov, A.V. (2010), “Packing n-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an n-dimensional parallelepiped”, Cybernetics and Systems Analysis, No. 46 (5). pp. 793-802.
Stoyan, Y.G. and Chugay, A.M. (2014), “Packing different cuboids with rotations and spheres into a cuboid Advances in Decision Sciences”, Advances in Decision Sciences, available at: http://dx.doi.org/10.1155/2014/571743.
Stoian, Y., Pankratov, A. and Romanova, T. (2017), “Optimal clustering of polyhedra”, Bionika intellekta, No. 2, pp. 12-22.