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.
