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).