articles

The article deals with the cutting and packing problems of irregular shape objects, which consist in finding the most compact way to place a given set of objects of arbitrary geometry inside a certain limited space. These problems belong to the class of ­NP-hard discrete optimization problems for which there are no methods of polynomial complexity to obtain exact solutions, so in practice they are most often solved approximately using heuristic and metaheuristic optimization methods. When placing objects of irregular shape, it is additionally necessary to take into account the geometry of objects to determine the correctness of their placement relative to each other. Existing methods of analyzing the geometry of objects and the formed placement scheme, based on the use of phi-functions and the construction of a hodograph of a vector function of dense placement, theoretically provide the possibility of obtaining an accurate solution, but require the use of time-consuming methods of nonlinear optimization. Therefore, in order to increase the speed of packing a large number of irregular-shaped objects, their shape is transformed by voxelization, followed by combining the resulting set of voxels into orthogonal polyhedra. To improve the quality of the solutions obtained, the paper proposes a greedy heuristic for the placement of orthogonal polyhedra, which implements the choice of the best orientation option for the object being placed, in which the formed packing will be the densest in comparison with other available orientation options for this object. The analysis of the effectiveness of this greedy heuristic on the problems of irregular cutting and packing of three-dimensional objects is carried out. Computational experiments have shown that the proposed greedy heuristic provides very fast high-quality solutions. Additionally, the results of testing the greedy placement heuristics using a genetic algorithm to optimize solutions to the packing problem are presented.