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