A BIOINSPIRED APPROACH TO SOLVING THE PROBLEM OF 3D PACKAGING
DOI:
https://doi.org/10.18522/2311-3103-2026-1-%25pKeywords:
Three-dimensional packing, optimization algorithms, evolutionary algorithms, multi-level search algorithm, local search methodsAbstract
This article examines one of the most important combinatorial optimization problems – three-dimensional packaging. Optimizing three-dimensional packaging reduces costs and improves logistics efficiency, making it relevant for industry. This paper analyzes classical approaches such as greedy algorithms and dynamic programming, as well as widely used methods, including evolutionary algorithms and local search. An analysis of existing methods, including greedy search, dynamic programming, evolutionary algorithms, and local search, revealed their key characteristics and identified suitable areas of application. In the context of this analysis, an overview of the key methods that dominated during certain historical periods is presented. The analysis includes consideration of the application conditions of various methods, their effectiveness for specific types of problems, as well as their advantages and limitations.
A multi-level search algorithm is presented that combines the advantages of traditional and modern optimization methods. This multi-level algorithm improves the accuracy of the packaging problem solution through dynamic parameter adjustment. A software package for solving the three-dimensional packaging optimization problem using bioinspired algorithms has been developed. A computational experiment was conducted on test examples (benchmarks). The packing quality obtained using the developed combined bioinspired algorithm is, on average, 7% higher than the packing results obtained using known algorithms, while the solution time is 7% to 25% shorter, demonstrating the effectiveness of the proposed approach. A series of tests and experiments allowed us to refine theoretical estimates of the time complexity of packing algorithms. In the best case, the time complexity of the algorithms is O(n²), and in the worst case, O(n³).
References
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.
