MULTILEVEL APPROACH TO TWO-DIMENSIONAL PACKING PROBLEM FOR GEOMETRIC FIGURES OF COMPLEX SHAPES

Abstract

The paper considers one of the important combinatorial optimization problems, namely the two-dimensional packing problem for geometric figures of complex shapes. It belongs to the class of NP-complex and difficult optimization problems. In this paper, the formulation of the twodimensional packing problem is given and described, and a combinatorial objective function that takes into account all constraints is introduced. Due to the complexity of this problem, a multilevel approach is proposed, which consists in dividing the two-dimensional packing problem into 4 subproblems and solving each subproblem sequentially in a strict order. At the same time, for each of the subtasks a unique set of objects that are not repeated in the other subtasks is defined. To implement the multilevel approach, the authors developed a combined bioinspired algorithm based on the methods of genetic search and bioinspired optimization. This approach allows to significantly reduce the time of obtaining the result, partially solve the problem of preliminary convergence of algorithms and obtain sets of quasi-optimal solutions in polynomial time. A software package has been developed and algorithms for automated two-dimensional packing based on the combined bioinspired algorithm have been implemented. A computational experiment on test cases (benchmarks) has been carried out. The packing quality obtained on the basis of the developed combined bioinspired algorithm, on average, by 2% exceeds the packing results obtained using known algorithms at comparable solution time, which indicates the effectiveness of the proposed approach. The conducted series of tests and experiments allowed us to refine the theoretical estimates of the time complexity of the packing algorithms. In the best case the time complexity of the algorithms is O(n2), in the worst case - O(n3).