KIAM Main page Web Library  •  Publication Searh   

Conference material: "Proceedings of the International Conference on Computer Graphics and Vision Graphicon (19-21 September 2023, Moscow)"
Authors: Chekanin V.A.
Optimized Placement of Irregular Shapes Based on the Selection of the Best Orientation Variants for the of Orthogonal Polyhedra
The article is devoted to improving the quality of solutions to NP-hard problems of optimized placement of flat and three-dimensional objects. To quickly build a layout of a large number of objects of irregular shape, the problem of packing orthogonal polyhedra obtained by voxelization of the original objects. A greedy heuristic is proposed that implements the choice of the best orientation variant for the object, in which the resulting layout will be the densest in comparison with other available orientation variants. An analysis of the effectiveness of applying the greedy heuristic on the problems of flat figured cutting and packing of three-dimensional objects of irregular shape is carried out. It is shown that the proposed greedy heuristic provides very fast high quality solutions. The results of testing the greedy placement heuristic when used as part of a genetic algorithm for optimizing solutions to the layout problem are presented.
Packing problem, voxelization, orthogonal polyhedron, greedy heuristic, genetic algorithm
Publication language: russian,  pages: 10 (p. 794-803)
Russian source text:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Chekanin Vladislav Alexandrovich, Trapeznikov Institute of Control Sciences of RAS; Moscow State University of Technology STANKIN