COMBINED SEARCH FOR SOLVING THE PROBLEM OF TWO-DIMENSIONAL PACKING OF GEOMETRIC FIGURES OF COMPLEX FORMS

Abstract

The article considers the problem of two-dimensional packing of geometric shapes of complex
shapes. The problems of this class are classified as NP-hard problems of combinatorial optimization.
In addition, the packaging of shapes of complex geometric shapes is one of the most difficult subtypes of
the two-dimensional packaging problem. In this regard, it is necessary to develop effective heuristic approaches
to solving this problem. The article presents the formulation of the problem, describes its main
features, and presents the limitations and conditions characteristic of this subtype of the two-dimensional
packaging problem. The criterion for calculating the effectiveness of the solution is described. To solve
this problem, the article proposes a combined search architecture consisting of two metaheuristic computational
algorithms. In this architecture, a modified genetic and swarm multi-agent bioinspired algorithm
based on the behavior of a bee colony was implemented as optimization methods. These algorithms allow
us to obtain sets of quasi-optimal solutions in polynomial time. The advantages of using the proposed
approach are given. To test the effectiveness of the proposed approach, a software product was developed
that uses the proposed architecture and metaheuristic computational algorithms to solve the problem.
The software product was developed in the C++ programming language and written in the Microsoft
Visual Studio Code development environment. A computational experiment was conducted on a set of
benchmark test cases. Based on the results of experimental studies, it is concluded that the proposed combined
search is effective in solving the problem of two-dimensional packing of geometric shapes of complex
shapes in comparison with solutions based on classical algorithms.