МНОГОУРОВНЕВЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ТРЕХМЕРНОЙ УПАКОВКИ БОЛЬШОЙ РАЗМЕРНОСТИ

  • В. В. Курейчик Южный федеральный университет
  • А. Е. Глущенко Таганрогская таможня
Ключевые слова: Трехмерная упаковка, упаковка в контейнеры, многоуровневый подход, комбинированный биоинспирированный алгоритм, генетический алгоритм, эволюционный алгоритм

Аннотация

Рассмотрена одна из важных комбинаторных задач оптимизации – задача трехмер-
ной упаковки разногабаритных элементов в объеме. Она относится к классу NP- сложных
и трудных оптимизационных задач. В работе приведена и описана постановка задачи трех-
мерной упаковки в объеме, введена комбинированная целевая функция учитывающая все огра-
ничения. В связи со сложностью данной задачи предлагается многоуровневый подход заклю-
чающийся в разделение задачи трехмерной упаковки на 3-и подзадачи и решения каждой под-
задачи в строгом порядке. При этом для каждой из подзадач определен уникальный набор
объектов, не повторяющихся в остальных подзадачах. Для реализации многоуровневого под-
хода авторами разработан комбинированный биоинспирированный алгоритм, основанный на
эволюционном и генетическом поиске. Такой подход позволяет значительно сократить время
получения результата, частично решить проблему предварительной сходимости алгоритмов
и получить наборы квазиотимальных решений за полиномиальное время. Разработан про-
граммный комплекс и реализованы на ЭВМ алгоритмы автоматизированной трехмерной
упаковки на основе комбинированного биоинспирированного поиска. Проведен вычисли-
тельный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, получен-
ное, на основе разработанного комбинированного биоинспирированного алгоритма, в сред-
нем на 5 % превосходит результаты упаковки, полученные с использованием известных
алгоритмов, а время решения меньше от 5 % до 20 %, что говорит об эффективности
предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить
теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае вре-
менная сложность алгоритмов O(n2), в худшем случае – O(n3).

Литература

1. Koide S., Suzuki S., Degawa S. A Palletize-Planning System for Multiple Kinds of Loads using
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.
Опубликован
2020-07-20
Выпуск
Раздел
РАЗДЕЛ I. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ