СОВРЕМЕННЫЕ ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ 3D УПАКОВКИ
Аннотация
Статья посвящена рассмотрению современных тенденций и подходов к решению актуальной оптимизационной задачи трехмерной упаковки в контейнеры. Важность построения эффективных методов решения данной задачи обусловлена бурным ростом направления электронной коммерции, когда достижение даже инкрементных улучшений плотности заполнения контейнеров грузами может привести к значительным сокращениям затрат на перевозку и хранение грузов. В статье приведен анализ различных типов задач и предложена классификация задач упаковки по различным критериям, в том числе: оффлайн- и онлайн-упаковка, по размерности, по видам и количеству контейнеров и грузов. Приведена постановка классической оптимизационной задачи о рюкзаке и рассмотрены различные варианты ограничений, обусловленные особенностями решаемых задач. Приведен краткий обзор основных подходов к решению задачи. Выполнен анализ и обобщение характерных особенностей применения метаэвристических подходов, основанных на использовании эволюционных и биоинспирированных алгоритмов и методов машинного обучения, отмечены их достоинства и недостатки. В силу сложности рассматриваемой задачи предлагается активно использовать известные и разрабатывать новые модификации метаэвристических алгоритмов, которые позволяют находить квазиоптимальные решения за полиномиальное время. Приведен анализ известных методов машинного обучения, биоинспирированных алгоритмов, описаны принципы их работы, выделены их основные особенности, преимущества и недостатки, отмечена перспективность их разработки и применения для решения NP-полных задач комбинаторной оптимизации. Приведен обобщенный принцип работы метаэвристических алгоритмов. Сравнительный анализ применения различных методов оптимизации показал эффективность использования метаэвристических методов для решения задачи трехмерной упаковки.
Список литературы
1. Liang K., Shan M., Liu H., et al. Intelligent optimization of e-commerce order packing using deep rein-forcement learning with heuristic strategies, Applied Soft Computing, 2025, Issue 179.
2. Xiong H., Ding K., Ding W., et al. Towards reliable robot packing system based on deep reinforcement learning, Advanced Engineering Informatics, 2023, Issue 57.
3. Yang J., Liang K., Liu H., et al. Optimizing e-commerce warehousing through open dimension manage-ment in a three-dimensional bin packing system, PeerJ Computer Science, 2023, Issue 9. Available at: https://peerj.com/articles/cs-1613/.
4. Alpert Charles J., Mehta Dinesh P., Sapatnekar Sachin S. Handbook of algorithms for physical design automation. CRC Press, New York, USA, 2009.
5. Gladkov L.A., Kravchenko Yu.A., Kureychik V.V., Rodzin S.I. Intellektual'nye sistemy: modeli i metody metaevristicheskoy optimizatsii: monografiya [Intelligent systems: models and methods of metaheuristic optimization: monograph]. Cheboksary: Sreda, 2024.
6. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2025.
7. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy [Modern search engine optimization algorithms. algorithms inspired by nature]. Moscow: MGTU im. Baumana, 2014.
8. Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Bioinspirirovannye metody v optimi-zatsii [Bioinspired methods in optimization]. Moscow: Fizmatlit, 2009.
9. Liu H., Zhou L., Yang J., et al. The 3D bin packing problem for multiple boxes and irregular items based on deep Q-network, Applied Intelligence, 2023, Issue 53, pp. 23398-23425.
10. Wu H., Leung S.C.H., Si Y. Three-stage heuristic algorithm for three-dimensional irregular packing prob-lem, Applied Mathematical Modelling, 2017, Issue 41, pp. 431-444.
11. Nascimento O.X.D., de Queiroz T.A., Junqueira L., et al. Practical constraints in the container loading problem: Comprehensive formulations and exact algorithm, Computers & Operations Research, 2021, Issue 128.
12. Ocloo V.E. A new mathematical model for a 3D container packing problem. Brandenburg: Brandenburg University of Technology, 2020.
13. Chen C.S., Lee S.M., Shen Q.S. An analytical model for the container loading problem, European Jour-nal of Operational Research, 1995, Issue 80, No. 1, pp. 68-76.
14. Junqueira J., Morabito R., Yamashita D.S. Three-dimensional container loading models with cargo sta-bility and load bearing constraints, Computers & Operations Research, Issue 39, No. 1, pp. 74-85.
15. Ramos A.G., Silva E., Oliveira J.F. A new load balance methodology for container loading problem in road transportation, European Journal of Operational Research, 2018, Issue 266, No. 3, pp. 1140-1152.
16. Hasan J., Kaabi J., Harrath Y. Multi-objective 3D bin-packing problem, Proceedings of the 8th Interna-tional Conference on Modeling Simulation and Applied Optimization (ICMSAO), 2019, pp. 1-5.
17. Costa M.D.G., Captivo M.E. Weight distribution in container loading: A case study, International Transactions in Operational Research, 2016, Issue 23, pp. 239-263.
18. 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, Issue 287, No. 3, pp. 1062-1074.
19. Júnior R.R., Yanasse H.H., Morabito R., et al. A hybrid approach for a multi-compartment container loading problem, Expert Systems with Applications, 2019, Issue 137, pp. 471-492.
20. Araújo O.C.B.D., and V.A. Armentano. A multi-start random constructive heuristic for the container loading problem, Pesquisa Operacional, 2007, Issue 27, No. 2, pp. 311-331.
21. Zhu W., Lim A. A new iterative-doubling Greedy–Lookahead algorithm for the single container loading problem, European Journal of Operational Research, 2012, Issue 222, No. 3, pp. 408-417.
22. Fanslau T., Bortfeldt A. A tree search algorithm for solving the container loading problem, INFORMS Journal on Computing, 2009, Issue 22, No. 2, pp. 222-235.
23. Da Silva E.F., Leao A.A.S., Toledo F.M.B., et al. A matheuristic framework for the three-dimensional single large object placement problem with practical constraints, Computers & Operations Research, 2020, Issue 124.
24. Toffolo T.A.M., Esprit E., Wauters T. A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem, European Journal of Operational Research, 2017, Is-sue 257, No. 2, pp. 526-538.
25. Liu S., Tan W., Xu Z., et al. A tree search algorithm for the container loading problem, Computers & Industrial Engineering, 2014, Issue 75, pp. 20-30.
26. Chien C.-F., Deng J.-F. A container packing support system for determining and visualizing container packing patterns, Decision Support Systems, 2004, Issue 37, No. 1, pp. 23-24.
27. Zhao H., She Q., Zhu C. Online 3D bin packing with constrained deep reinforcement learning, Proceed-ings of AAAI Technical Track on Application Domains, Issue 35, No. 1, pp. 741-749.
28. Hu H., Zhang X., Yan X. et al. Solving a new 3D bin packing problem with deep reinforcement learning method, arXiv, 2017. arXiv:1708.05930.
29. Duan L., Hu H., Qian Y. et al. A multi-task selected learning approach for solving 3D flexible bin pack-ing problem, arXiv, 2018. arXiv:1804.06896.
30. Hu R., Xu J., Chen B. TAP-Net: Transport-and-pack using reinforcement learning, ACM Transactions on Graphics (TOG), 2020, Issue 39, No. 6, pp. 1-15.
31. Laterre A., Fu Y., Jabri M.K., et al. Ranked reward: Enabling self-play reinforcement learning for com-binatorial optimization, arXiv, 2018. arXiv:1807.01672.
32. Liu D. On solving multiobjective bin packing problems using evolutionary particle swarm optimization, European Journal of Operational Research, 2008, Issue 190, No. 2, pp. 357-382.
33. Oleynik A.S., Polupanova E.E. Reshenie zadachi trekhmernoy upakovki algoritmom posledovatel'noy gibridizatsii [Solution of the three-dimensional packing problem using the sequential hybridization algo-rithm], Prikladnaya matematika: sovremennye problemy matematiki, informatiki i modelirovaniya: Ma-ter. III vserossiyskoy nauchno-prakticheskoy konferentsii molodykh uchenykh, Krasnodar, 21–24 aprelya 2021 goda [Applied Mathematics: Modern Problems of Mathematics, Computer Science and Modeling: Proceedings of the III All-Russian Scientific and Practical Conference of Young Scientists, Krasnodar, April 21–24, 2021]. Vol. I, 2021, pp. 183-188.
34. Wu B., Lin Jg., Dong M. Artificial Bee Colony Algorithm for Three-Dimensional Loading Capacitated Vehicle Routing Problem, Proceedings of 20th International Conference on Industrial Engineering and Engineering Management, 2013, pp. 815-825.
35. Rajesh Kanna S.K., Udaiyakumar K.C. A Complete Framework For Multi-Constrained 3 D Bin Pack-ing Optimization Using Firefly Algorithm, International Journal of Pure and Applied Mathematics, 2017, Issue 114, pp. 267-282. Available at: https://www.semanticscholar.org/paper/A-Complete-Framework-For-Multi-Constrained-3-D-Bin-Kanna-Udaiyakumar/badaf2002a67581a1574a2e82e55deb65a611a6f.
36. Zhao Ch., Jliang L., Teo K. A hybrid chaos firefly algorithm for three-dimensional irregular packing problem, Journal of Industrial and Management Optimization, 2020, Issue 13, pp. 1-21. Available at: https://www.researchgate.net/publication/328761857_A_hybrid_chaos_firefly_algorithm_for_three-dimensional_irregular_packing_problem.
37. Gherboudj A. African Buffalo Optimization for One Dimensional Bin Packing Problem, International Journal of Swarm Intelligence Research, 2019, Issue 10, No. 4, pp. 38-52. Available at: https://www.igi-global.com/gateway/article/234698.
38. Layeb A., Benayad Z. A novel firefly algorithm based ant colony optimization for solving combinatorial optimization problems, International Journal of Computer Science and Applications, 2014, Issue 11, pp. 19-37. Available at: https://www.researchgate.net/publication/268215316_A_novel_firefly_ algo-rithm_based_ant_colony_optimization_for_solving_combinatorial_optimization_problems.
39. Montiel-Arrieta L.J., Barragan-Vite I., Seck-Tuoh-Mora J.C., et al. Minimizing the total waste in the one-dimensional cutting stock problem with the African buffalo optimization algorithm // PeerJ Com-puter Science. – 2023. – Вып. 9. – DOI:10.7717/peerj-cs.1728. Available at: https://pubmed.ncbi.nlm.nih.gov/38192486/.
40. Wang P., Rao Y., Luo Q. An Effective Discrete Grey Wolf Optimization Algorithm for Solving the Packing Problem, IEEE Access, 2020. DOI:10.1109/ACCESS.2020.3004380. Available at: https://www.researchgate.net/publication/342402646_An_Effective_Discrete_Grey_Wolf_Optimization_Algorithm_for_Solving_the_Packing_Problem.
41. Kang K., Moon I., Wang H. A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem, Applied Mathematics and Computation, 2012, No. 219, pp. 1287-1299.
42. Wang X., Gong L., Zhao H., Li B., Tian M. A 3D Offline Packing Algorithm considering Cargo Orien-tation and Stability, International Journal of Distributed Sensor Networks, 2023.
43. Arora J.S. Introduction to Optimum Design. 3 ed. Iowa City, 2012. Available at: https://mu.menofia.edu.eg/PrtlFiles/Staff/1045/Portal/Files/Introduction%20to%20Optimum%20Design,%203nd%20Ed(3).pdf.
44. Zhang D.-F., Chen Sh.-D., Liu Y.-J. An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem, Acta Automatica Sinica, 2007, No. 33.
45. Goncalves J.F., Resende M.G.C. A biased random key genetic algorithm for 2D and 3D bin packing problems, International Journal of Production Economics, 2013, Issue 145, No. 2, pp. 500-510.
46. Olsson J., Larsson T., Quttineh N.-H. Automating the planning of container loading for atlas copco: Coping with real-life stacking and stability constraints, European Journal of Operational Research, Is-sue 280, No. 3, pp. 1018-1034.
47. Xiang X. Yu C., Xu H., et al. Optimization of heterogeneous container loading problem with adaptive genetic algorithm, Complexity, 2018, Issue 6, pp. 1-12.
48. Ananno A.A., Ribeiro L. A Multi-Heuristic Algorithm for Multi-Container 3-D Bin Packing Problem Optimization Using Real World Constraints, IEEE Access, 2024, Issue 12, pp. 42105-42130.
49. Yang Y., Wu Z., Hao X., et al. Two-layer heuristic for the three-dimensional bin design and packing problem, Engineering Optimization, 2023. DOI: 10.1080/0305215X.2023.2269868.
50. Phongmoo S., Leksakul K., Charoenchai N., et al. Artificial Bee Colony Algorithm with Pareto-Based Approach for Multi-Objective Three-Dimensional Single Container Loading Problems, Applied Scienc-es, 2023, Issue 13, No. 11. DOI: 10.3390/app13116601. Available at: https://www.mdpi.com/ 2076-3417/13/11/6601.
51. Loh T., Nee A. A Packing Algorithm for Hexahedral Boxes, Proceedings of the Conference of Industri-al Automation, 1992, pp. 115-126.
