MULTILEVEL APPROACH TO TWO-DIMENSIONAL PACKING PROBLEM FOR GEOMETRIC FIGURES OF COMPLEX SHAPES
Abstract
The paper considers one of the important combinatorial optimization problems, namely the two-dimensional packing problem for geometric figures of complex shapes. It belongs to the class of NP-complex and difficult optimization problems. In this paper, the formulation of the twodimensional packing problem is given and described, and a combinatorial objective function that takes into account all constraints is introduced. Due to the complexity of this problem, a multilevel approach is proposed, which consists in dividing the two-dimensional packing problem into 4 subproblems and solving each subproblem sequentially in a strict order. At the same time, for each of the subtasks a unique set of objects that are not repeated in the other subtasks is defined. To implement the multilevel approach, the authors developed a combined bioinspired algorithm based on the methods of genetic search and bioinspired optimization. This approach allows to significantly reduce the time of obtaining the result, partially solve the problem of preliminary convergence of algorithms and obtain sets of quasi-optimal solutions in polynomial time. A software package has been developed and algorithms for automated two-dimensional packing based on the combined bioinspired algorithm have been implemented. A computational experiment on test cases (benchmarks) has been carried out. The packing quality obtained on the basis of the developed combined bioinspired algorithm, on average, by 2% exceeds the packing results obtained using known algorithms at comparable solution time, which indicates the effectiveness of the proposed approach. The conducted series of tests and experiments allowed us to refine the theoretical estimates of the time complexity of the packing algorithms. In the best case the time complexity of the algorithms is O(n2), in the worst case - O(n3).
References
of automated design and engineering, Studies in Computational Intelligence, 2009,
Vol. 212, pp. 1-22.
2. Kormen T., Leyzerson I., Rivest R. Algoritmy. Postroenie i analiz [Algorithms. Construction
and analysis]. Moscow: MTSMO, 2000.
3. Gladkov L.A., Zinchenko L.A., Kureychik V.V., Kureychik V.M., Lebedev B.K., Nuzhnov E.V.,
Sorokin S.N. Metody geneticheskogo poiska [Genetic search methods]. Taganrog, 2002.
4. Kureychik V.V., Rodzin S.I. Vychislitel'nye modeli evolyutsionnykh i roevykh bioevristik
(Obzor) [Computational models of evolutionary and swarm bioheuristics (Review)],
Informatsionnye tekhnologii [Information technologies], 2021, Vol. 27, No. 10, pp. 507-520.
5. Timofeeva O.P., Sokolova E.S., Milov K.V. Geneticheskiy algoritm v optimizatsii upakovki
konteynerov [Genetic algorithm in optimization of container packaging], Tr. NGTU im.
R.E. Alekseeva [.Proceedings of NSTU im. R.E. Alekseeva], 2012, No. 4 (101), pp. 167-172.
6. Gehring H., Bortfeldt A. A genetic algorithm for solving the container loading problem, International
Transactions in Operational Research, 1997, Vol. 4, Iss. 5-6, pp. 401-418.
7. Kureichik V., Kureichik L., Zaruba D. Bioinspired algorithm for 2D packing problem, Advances
in Intelligent Systems and Computing, 2019, Vol. 764, pp. 39-46.
8. Li M., Song C., Zhou Z. Hybrid particle swarm optimization for two-dimensional irregular
parts packing, Journal of Sichuan University (Engineering Science Edition), 2005, Vol. 37,
Iss. 4, pp. 134-138.
9. Shin Y., Kita E. Solving two-dimensional packing problem using particle swarm optimization,
Computer Assisted Mechanics and Engineering Science, 2012, Vol. 19, Iss. 3, pp. 241-255.
10. Zhang D., Dong R., Si Y. Hybrid swarm algorithm based on ABC and AIS for 2L-HFCVRP,
Q.a View Correspondence, 2017, Vol. 61, pp. 726.
11. 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.
12. Soukaina Laabadi, Naimi M., Amri H.E., Achchab B. A Binary Crow Search Algorithm for
Solving Two-dimensional Bin Packing Problem with Fixed Orientation, Procedia Computer
Science, 2020, Vol. 167, pp. 809-818.
13. Valeeva A.F. Primenenie konstruktivnykh evristik v zadachakh raskroya-upakovki [Application
of constructive heuristics in cutting-packing problems], Informatsionnye tekhnologii
[Information technologies], 2006, No. S11, pp. 1-24.
14. Mukhacheva E.A., Verkhoturov M.A, Martynov V.V. Modeli i metody rascheta raskroya –
upakovki geometricheskikh ob"ektov [Models and methods for calculating cutting and packaging
of geometric objects]. Ufa: UGATU, 1998, 216 p.
15. Frolovskiy V.D. Optimal'noe gruppirovanie geometricheskikh ob"ektov pri proektirovanii kart
raskroya materialov [Optimal grouping of geometric objects when designing cutting charts for materials],
Programmnye produkty i sistemy [Software products and systems], 2000, No. 3, pp. 47-48.
16. Bazilevich R.P. Dekompozitsionnye i topologicheskie metody avtomatizirovannogo
konstruirovaniya elektronnykh ustroystv: monografiya [Decomposition and topological methods
for automated design of electronic devices: monograph]. L'vov: Vishchashkola, 1981, 81 p.
17. 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], Novye tekhnologii. Informatsionnye
tekhnologii. Prilozhenie [New technologies. Information Technology. Application], 2004,
No. 5, pp. 19-31.
18. Fadel G. Sinha G., McKee A. Packing optimization using a rubberband analogy, Design Engineering
Technical Conference and Computers and Information in Engineering Conference,
Pittsburgh, PA (ASME), 2001, Vol. 2, pp. 409-415.
19. Bova V.V., Kureychik V.V., Lezhebokov A.A. Problemno orientirovannyy geneticheskiy algoritm
upakovki raznogabaritnykh elementov [Problem-oriented genetic algorithm for packing multisized
elements], Vestnik Rostovskogo gosudarstvennogo universiteta putey soobshcheniya [Bulletin
of the Rostov State Transport University], 2014, No. 3 (55), pp. 52-59.
20. 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.
