COMBINED SEARCH FOR SOLVING THE PROBLEM OF TWO-DIMENSIONAL PACKING OF GEOMETRIC FIGURES OF COMPLEX FORMS
Abstract
The article considers the problem of two-dimensional packing of geometric shapes of complex
shapes. The problems of this class are classified as NP-hard problems of combinatorial optimization.
In addition, the packaging of shapes of complex geometric shapes is one of the most difficult subtypes of
the two-dimensional packaging problem. In this regard, it is necessary to develop effective heuristic approaches
to solving this problem. The article presents the formulation of the problem, describes its main
features, and presents the limitations and conditions characteristic of this subtype of the two-dimensional
packaging problem. The criterion for calculating the effectiveness of the solution is described. To solve
this problem, the article proposes a combined search architecture consisting of two metaheuristic computational
algorithms. In this architecture, a modified genetic and swarm multi-agent bioinspired algorithm
based on the behavior of a bee colony was implemented as optimization methods. These algorithms allow
us to obtain sets of quasi-optimal solutions in polynomial time. The advantages of using the proposed
approach are given. To test the effectiveness of the proposed approach, a software product was developed
that uses the proposed architecture and metaheuristic computational algorithms to solve the problem.
The software product was developed in the C++ programming language and written in the Microsoft
Visual Studio Code development environment. A computational experiment was conducted on a set of
benchmark test cases. Based on the results of experimental studies, it is concluded that the proposed combined
search is effective in solving the problem of two-dimensional packing of geometric shapes of complex
shapes in comparison with solutions based on classical algorithms.
References
design: textbook]. Moscow: Izd-vo MGTU imeni N.E. Baumana, 2006, 336 p.
2. Kormen, T. Leyzerson I., Rivest R. Algoritmy. Postroenie i analiz [Algorithms. Construction and analysis].
Moscow: MTSMO, 2000.
3. Kureichik V.V., Kureichik V.M. Genetic Search-Based Control, Automation and Remote Control, 2001,
Vol. 62, 10, pp. 1698-1710.
4. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy:
ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired by nature: textbook.
Allowance]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014.
5. Rodzin S.I., Kureychik V.V. Teoreticheskie voprosy i sovremennye problemy razvitiya kognitivnykh
bioinspirirovannykh algoritmov optimizatsii (obzor) [Theoretical issues and modern problems in the development
of cognitive bioinspired optimization algorithms (review)], Kibernetika i programmirovanie
[Cybernetics and Programming], 2017, No. 3, pp. 51-79.
6. Abraham A., Ramos V., Grosan G. Swarm Intelligence in Data Mining. Berlin. Heidelberg: Springer
Verlag, 2007, 267 p.
7. Hassanien E. Emary E. Swarm Intelligence: Principles Advances, and Applications. CRC Press,
2015, 228 p.
8. Mourelle M., Nedjah L. De Swarm intelligent systems. Berlin: Heidelberg: Springer Verlag, 2006, 217 p.
9. Mukhacheva E.A., Verkhoturov M.A, Martynov V.V. Modeli i metody rascheta raskroya – upakovki
geometricheskikh ob"ektov [Models and methods for calculating cutting - packaging of geometric objects].
Ufa: UGATU, 1998, 216 p.
10. Levin M.Sh. Upakovka v konteynery (perspektivnye modeli, primery) [Packaging in containers (promising
models, examples)], Informatsionnye protsessy [Information processes], 2017, No. 1, pp. 43-60.
11. Kuliev E.V., Gerasimenko E.M., Khalenkov A.Yu, Semenova M.M., Ignat'eva S.V. Razrabotka
bioinspirirovannogo algoritma resheniya zadachi dvumernoy upakovki [Development of a bioinspired
algorithm for solving the two-dimensional packaging problem], Informatizatsiya i svyaz'
[Informatization and Communication], 2021, No. 3, pp. 78-85.
12. Vanidovskiy V.A., Lebedev O.B., Pantelyuk E.A., Kulieva N.V. Dvumernaya upakovka v
poluogranichennuyu polosu na osnove modelirovaniya adaptivnogo povedeniya murav'inoy kolonii
[Two-dimensional packing in a semi-limited strip based on modeling the adaptive behavior of an ant
colony], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 9,
pp. 21-27.
13. Orlov A.N., Kureychik V.V., Glushchenko A.E. Kombinirovannyy geneticheskiy algoritm resheniya
zadachi raskroya [Combined genetic algorithm for solving the cutting problem], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, No. 6 (179), pp. 5-13.
14. Kureychik V.V., Bova V.V., Kureychik V.V. Kombinirovannyy poisk pri proektirovanii [Combined
search in design], Obrazovatel'nye resursy i tekhnologii [Educational resources and technologies],
2014, No. 2 (5), pp. 90-94.
15. Lawrence Davis. Handbook of Genetic Algorithms, Ed. by Lawrence Davis. USA: Van Nostrand
Reinhold, New York, 1991, 100 p.
16. Holland John H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application
to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975, 183 p.
17. Goldberg David E. Genetic Algorithm in Search, Optimization and Machine Learning. USA: Addison-
Wesley Publishing Company. Ind., 1989, 196 p.
18. Karaboga D. An idea based on honey bee swarm for numerical optimization. Erciyes University, Engineering
Faculty, Computer Engineering Department, 2005, 110 p.
19. Xiuqin P, Yun W, Yong L, Na S. Improved artificial bee colony algorithm based on two-dimensional
queue structure for complex optimization problems, Alexandria Engineering Journal, 2024, Vol. 86,
pp. 669-679.
20. Kureychik V.V., Polupanova E.E. Evolyutsionnaya optimizatsiya na osnove algoritma kolonii pchel
[Evolutionary optimization based on the bee colony algorithm], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2009, No. 12 (101), pp. 41-46.
21. Pham D.T., Castellani M. The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous
Optimization Problems, Proc. ImechE, Part C, 2009, 223 (12), pp. 2919-2938.
22. Weiss M.A. Data Structures and Algorithm Analysis in C++. Boston: Pearson Education, 2014, 656 p.
