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).
References
GA Search and Traditional Search, Intelligent Robots and Systems 95. 'Human Robot Interaction
and Cooperative Robots', Proceedings. IEEE, 1995, Vol. 3, pp. 510-515.
2. Mukhacheva E.A., Mukhacheva A.S. Tekhnologiya blochnykh struktur lokal'nogo poiska
optimuma v zadachakh pryamougol'noy upakovki [Technology of block structures for local
optimal search in rectangular packing problems], Informatsionnye tekhnologii [Information
technologies], 2004, No. 5. Appendix, pp. 19-31.
3. Yudakov P.V. Zadacha o trekhmernoy upakovke i metody ee resheniya. Obzor [The problem of
three-dimensional packaging and methods of its solution. Review], Inzhenernyy vestnik [Engineering
Bulletin], 2015, No. 06, pp. 552-581.
4. Lutsan M.V., Nuzhnov E.V. Reshenie zadachi trekhmernoy upakovki s paletirovaniem
konteynerov [Solving the problem of three-dimensional packaging with container
palletization], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2014, No. 7 (156), pp. 196-204.
5. Nuzhnov E.V., Barlit A.V. Trekhmernaya upakovka nesvyaznykh elementov na osnove
evristicheskikh protsedur [Three-dimensional packaging of disconnected elements based on
heuristic procedures]. Taganrog: Izd-vo TRTU, 2002, pp. 23-28.
6. Psiola B.V. O priblizhennom reshenii 3-kh mernoy zadachi ob upakovke na osnove evristik
[Approximate solution of a 3-dimensional packaging problem based on heuristics],
Intellektual'nye sistemy [Intelligent system], 2007, No. 11, Issue 1-4, pp. 83-101.
7. Bortfeldt A., Wascher G. Constraints in container loading: a state-of-the-art review, European
Journal of Operational Research, 2013, Vol. 229, Issue 1, pp. 1-20.
8. Gladkov L.A., Gladkova N.V., Skubrieva E.S. Reshenie zadachi trekhmernoy upakovki
raznogabaritnykh ob"ektov s ispol'zovaniem bionicheskikh metodov [Solving the problem of threedimensional
packaging of multi-dimensional objects using bionic methods], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (144), pp. 35-41.
9. Timofeeva O.P., Sokolova E.S., Milov K.V. Geneticheskiy algoritm v optimizatsii upakovki
konteynerov [Genetic algorithm for optimizing container packaging], Tr. NGTU im. R.E. Alekseeva
[Proceedings of the NSTU named after R. E. Alekseev], 2012, No. 4 (101), pp. 167-172.
10. Gehring H., Bortfeldt A. A genetic algorithm for solving the container loading problem, International
Transactions in Operational Research, 1997, Vol. 4, Issue 5-6, pp. 401-418.
11. Kureychik V.V., Zaruba D.V., Zaporozhets D.Yu. Primenenie geneticheskogo algoritma
resheniya zadachi trekhmernoy upakovki [Application of a genetic algorithm for solving the
problem of three-dimensional packaging], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya
SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 8-14.
12. Kureychik V.V., Glushchenko A.E., Orlov A.N. Gibridnyy podkhod dlya resheniya zadachi
3-kh mernoy upakovki [Hybrid approach for solving the problem of 3-dimensional packaging],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, No. 6
(179), pp. 45-53.
13. Kureychik V.M., Kureychik L.V. Kompleksnyy metod upakovki blokov [Complex method of
packing blocks], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie [Computer
science, computer engineering and engineering education], 2015, No. 1 (21), pp. 17-26.
14. Chauny F.A. Bloc Heuristic for the Container Loading Problem, Grouped'étudeset de recherche
en analyse des decisions, Montréal, 2005, pp. 1-18.
15. Bazilevich R.P. Dekompozitsionnye i topologicheskie metody avtomatizirovannogo
konstruirovaniya elektronnykh ustroystv: monografiya [Decomposition and topological methods
of automated design of electronic devices: monograph]. L'vov: Vishchashkola, 1981, 81 p.
16. Bazilevich R.P. Metod optimal'nogo svertyvaniya skhemy – effektivnyy podkhod dlya
kachestvennogo resheniya nepolinomial'nykh kombinatornykh zadach bol'shoy i sverkhbol'shoy
razmernosti v avtomatizirovannom konstruirovanii REA [The method of optimal circuit
folding is an effective approach for the qualitative solution of non-polynomial combinatorial
problems of large and super-large dimensions in the automated design of REA], Sb.
nauchnykh trudov «Problemy razrabotki perspektivnykh mikroelektronnykh sistem» [Collection
of scientific papers "Problems of development of perspective microelectronic systems"].
Moscow: IPPM RAN, 2005, pp. 94-100.
17. Chan F.T.S., Kumar N., Wong T.C. Three-Dimensional Air-Cargo Loading Problem: An Evolutionary
Algorithm Based Approach, Proceedings of the 7th Asia Pacific Industrial Engineering
and Management Systems Conference, 2006, pp. 758-765.
18. Kureychik V.V., Glushchenko A.E. Kombinirovannyy podkhod dlya resheniya zadachi 3-kh
mernoy upakovki raznogabaritnykh elementov [Combined approach for solving the problem of
3-dimensional packaging of different-sized elements], XII Vserossiyskaya nauchnaya
konferentsiya molodykh uchenykh, aspirantov i studentov, informatsionnye tekhnologii,
sistemnyy analiz i upravlenie (ITSA i U-2015) [XII all-Russian scientific conference of young
scientists, postgraduates and students, information technologies, system analysis and management
(ITSA and U-2015)]. Rostov-on-Don: Izd-vo YuFU, 2015, pp. 75-79.
19. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithm].
Moscow: Fizmatlit, 2010.
20. Kureychik V.V., Glushchenko A.E., Kureychik L.V. Programmnyy kompleks kombinirovannogo
poiska dlya resheniya zadachi trekhmernoy upakovki [Combined search software package for solving
the problem of three-dimensional packaging] Tr. II Vserossiyskoy nauchno-tekhnicheskoy
konferentsii Fundamental'nye i prikladnye aspekty komp'yuternykh tekhnologiy i
informatsionnoy bezopasnosti [Proceedings of the II all-Russian scientific and technical conference
Fundamental and applied aspects of computer technologies and information security].
Taganrog: Izd-vo YuFU, 2016, pp. 216-220.
21. Zhukov L.A., Korchevskaya O.V. Metod ploskostey: chislennyy eksperiment dlya zadach
dvukh i trekhmernoy ortogonal'noy upakovki [Method of planes: numerical experiment for
two-and three-dimensional orthogonal packing problems], Informatsionnye tekhnologii [Information
technologies], 2008, No. 11, pp. 41-45.
