MULTILEVEL APPROACH FOR HIGH DIMENSIONAL 3D PACKING PROBLEM

Abstract

The article considers one of the important combinatorial optimization problems, the problem
of 3D packing of different elements in a fixed volume. It belongs to the class of NP-complex and difficult
optimization problems. The paper presents and describes the formulation of the 3D packing
problem, introduces a combined objective function that takes into account all the restrictions. Due to
the complexity of this task, a multilevel approach is proposed. It is consisting in dividing the 3D packing
problem into 3 subtasks and solving each subtask in a strict order. Moreover, for each of the
subtasks a unique set of objects is defined that are not repeated in the remaining subtasks. To implement
a multi-level approach, the authors developed a combined bio-inspired algorithm based onevolutionary and genetic search. This approach can significantly reduce the time to obtain the result,
partially solve the problem of preliminary convergence of the algorithms and obtain sets of quasioptimal
solutions in polynomial time. A software package was developed and computer-based algorithms
for automated 3D packaging based on a combined bio-inspired search were implemented.
A computational experiment was conducted on test examples (benchmarks). The packaging quality
obtained on the basis of the developed combined bio-inspired algorithm is on average 5 % higher
than the packaging results obtained using known algorithms, and the solution time is less than 5 % to
20 %, which indicates the effectiveness of the proposed approach. The series of tests and experiments
carried out made it possible to refine the theoretical estimates of the time complexity of the packaging
algorithms. In the best case the time complexity of the O (n2) algorithms; in the worst, O (n3).