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.