МНОГОУРОВНЕВЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ТРЕХМЕРНОЙ УПАКОВКИ БОЛЬШОЙ РАЗМЕРНОСТИ
Аннотация
Рассмотрена одна из важных комбинаторных задач оптимизации – задача трехмер-
ной упаковки разногабаритных элементов в объеме. Она относится к классу NP- сложных
и трудных оптимизационных задач. В работе приведена и описана постановка задачи трех-
мерной упаковки в объеме, введена комбинированная целевая функция учитывающая все огра-
ничения. В связи со сложностью данной задачи предлагается многоуровневый подход заклю-
чающийся в разделение задачи трехмерной упаковки на 3-и подзадачи и решения каждой под-
задачи в строгом порядке. При этом для каждой из подзадач определен уникальный набор
объектов, не повторяющихся в остальных подзадачах. Для реализации многоуровневого под-
хода авторами разработан комбинированный биоинспирированный алгоритм, основанный на
эволюционном и генетическом поиске. Такой подход позволяет значительно сократить время
получения результата, частично решить проблему предварительной сходимости алгоритмов
и получить наборы квазиотимальных решений за полиномиальное время. Разработан про-
граммный комплекс и реализованы на ЭВМ алгоритмы автоматизированной трехмерной
упаковки на основе комбинированного биоинспирированного поиска. Проведен вычисли-
тельный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, получен-
ное, на основе разработанного комбинированного биоинспирированного алгоритма, в сред-
нем на 5 % превосходит результаты упаковки, полученные с использованием известных
алгоритмов, а время решения меньше от 5 % до 20 %, что говорит об эффективности
предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить
теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае вре-
менная сложность алгоритмов O(n2), в худшем случае – O(n3).
Литература
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.