БИОИНСПИРИРОВАННЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ТРЕХМЕРНОЙ УПАКОВКИ
DOI:
https://doi.org/10.18522/2311-3103-2026-1-%25pКлючевые слова:
Трехмерная упаковка, оптимизационные алгоритмы, эволюционные алгоритмы, многоуровневый алгоритм поиска, методы локального поискаАннотация
Рассматривается одна из важных комбинаторных задач оптимизации – задача трехмерной упаковки. Оптимизация трехмерной упаковки снижает затраты и повышает эффективность логистики, что делает ее актуальной для промышленности. В работе проанализированы классические подходы, такие как жадные алгоритмы и динамическое программирование, а также широко применяемые методы, включая эволюционные алгоритмы и локальный поиск. Анализ существующих методов, включая жадный поиск, динамическое программирование, эволюционные алгоритмы и локальный поиск, позволил выявить их ключевые характеристики и определить подходящие области применения. В контексте данного анализа представлен обзор ключевых методов, доминировавших в определенные исторические периоды. Анализ включает рассмотрение условий применения различных методов, их эффективности для определенных типов задач, а также их преимуществ и ограничений. Представлен многоуровневый алгоритм поиска, который объединяет преимущества традиционных и современных методов оптимизации. Многоуровневый алгоритм позволяет улучшить точность решения задачи упаковки за счет динамической настройки параметров. Разработан программный комплекс для решения задачи оптимизации трехмерной упаковки с использованием биоинспирированных алгоритмов. Проведен вычислительный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, полученное, на основе разработанного комбинированного биоинспирированного алгоритма, в среднем на 7 % превосходит результаты упаковки, полученные с использованием известных алгоритмов, а время решения меньше от 7% до 25%, что говорит об эффективности предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае временная сложность алгоритмов 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 Coop-erative Robots', Proceedings. IEEE, 1995, Vol. 3, pp. 510-515.
2. Kureychik V.V., Balyasova Yu.V., Bova V.V. Obzor i analiz metodov trekhmernoy upakovki pri morskikh gruzoperevozkakh [Review and analysis of three-dimensional packing methods for sea freight transpor-tation], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2024, No. 6, pp. 15-29.
3. Kang Z., Guan Y., Wang J., Chen P. Research on Genetic Algorithm Optimization with Fusion Tabu Search Strategy and Its Application in Solving Three-Dimensional Packing Problems, Symmetry, 2024, Vol. 16 (4), pp. 449.
4. Kureychik V.V., Glushchenko A.E. Mnogourovnevyy podkhod dlya resheniya zadachi trekhmernoy upakovki bol'shoy razmernosti [Multilevel approach for solving the problem of large-scale three-dimensional packing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2020, No. 2 (212), pp. 6-16.
5. 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 packing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, No. 6 (179), pp. 45-53.
6. Kureychik V.V., Glushchenko A.E. Kombinirovannyy podkhod dlya resheniya zadachi 3-kh mernoy upakovki raznogabaritnykh elementov [A combined approach to solving the problem of 3-D packing 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 Technology, Sys-tems Analysis, and Management (ITSAiU-2015)]. Rostov-on-Don: Izd-vo YuFU, 2015, pp. 75-79.
7. Kureychik V.M., Kureychik L.V. Kompleksnyy metod upakovki blokov [An Integrated Block Packing Method], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie [Computer Science, Comput-er Engineering, and Engineering Education], 2015, No. 1 (21). pp. 17-26.
8. Shayliev M.B., Garyagdyev A.M. Klassifikatsiya i analiz sushchestvuyushchikh algoritmov trekhmernoy upakovki raznogabaritnykh ob"ektov v bloki [Classification and analysis of existing algorithms for three-dimensional packing of different-sized objects into blocks], Fundamental'nye i prikladnye aspekty komp'yuternykh tekhnologiy i informatsionnoy bezopasnosti [Fundamental and Applied Aspects of Computer Technology and Information Security], 2023, pp. 220-222.
9. Sridhar R., Chandrasekaran M., Page T. Multi-objective optimization of heterogeneous bin packing using adaptive genetic approach, Indian Journal of Science and Technology, 2016, Vol. 9, No. 48.
10. Yuan Y. et al. Three-dimensional atomic packing in amorphous solids with liquid-like structure, Nature materials, 2022, Vol. 21, No. 1, pp. 95-102.
11. Zolotukhin A.V., Maryashina D.N. Primenenie modifitsirovannogo geneticheskogo algoritma kak od-nogo iz evolyutsionnykh podkhodov k resheniyu zadachi trekhmernoy upakovki [Application of a modi-fied genetic algorithm as one of the evolutionary approaches to solving the three-dimensional packing problem], 2021.
12. Kravchenko D.Yu. i dr. Bioinspirirovannyy metod klassifikatsii raspredelennykh vychisli-tel'nykh resur-sov dlya dispetchirovaniya v grid-sistemakh [Bioinspired method for classification of distributed compu-ting resources for dispatching in grid systems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2021, No. 4 (221), pp. 31-41.
13. Zaruba D.V. Komponovka blokov EVA na osnove bioinspirirovannykh metodov poiska [Layout of EVA blocks based on bioinspired search methods], Sovremennye komp'yuternye tekhnologii [Modern Computer Technologies], 2020, pp. 4-9.
14. Ling X., Osotsi M.I., Zhang W., et al. Bioinspired Materials: From Distinct Dimensional Architecture to Thermal Regulation Properties, J Bionic Eng., 2023, Vol. 20, pp. 873-899.
15. Kravchenko D.Yu. i dr. Bioinspirirovannyy metod imitatsionnogo modelirovaniya dlya dispetcherizatsii potokov parallel'nykh zayavok v grid-sistemakh [Bioinspired simulation modeling method for dispatch-ing parallel request flows in grid systems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. En-gineering Sciences], 2020, No. 2 (212), pp. 79-88.
16. Kureychik V.V., Glushchenko A.E., Orlov A.N. Hybrid genetic algorithm for cutting stock and packaging problems [Hybrid genetic algorithm for cutting stock and packaging problems], Proceedings of IEEE Ea st-West Design & Test Symposium (EWDTS 2016) [Proceedings of IEEE Ea st-West Design & Test Symposium (EWDTS 2016)]. Indexed in Skopus. IEEE EWDTS 2016, Yerevan, October,
14-17, 2016, pp. 587-590.
17. Gzara F., Elhedhli S., Yildiz B.C. The pallet loading problem: Three-dimensional bin packing with prac-tical constraints, European Journal of Operational Research, 2020, Vol. 287, No. 3, pp. 1062-1074.
18. Chen Y. et al. Recent advancements on three-dimensional electrospun nanofiber scaffolds for tissue en-gineering, Advanced Fiber Materials, 2022, Vol. 4, No. 5, pp. 959-986.
19. Nguyen T.H. et al. Bio-inspired approaches for smart energy management: State of the art and challeng-es, Sustainability, 2020, Vol. 12, No. 20, pp. 8495.
20. Jiang Y., Cao Z., Zhang J. Learning to solve 3-D bin packing problem via deep reinforcement learning and constraint programming, IEEE transactions on cybernetics, 2021, Vol. 53, No. 5, pp. 2864-2875.
