The problem of geometric covering

Authors: Koshlakov N.V.
Published in issue: #1(18)/2018
DOI: 10.18698/2541-8009-2018-1-227
Category: Informatics, Computer Engineering and Control | Chapter: System Analysis, Control, and Information Processing, Statistics
Keywords: the problem of optimizing the geometric covering, nondeterministic polynomial time hard problem, metaheuristic algorithms
Published: 20.12.2017

The article considers the problem of geometric covering with the smallest area of overlaps and holes of the objects. It is a particular case of the optimal design problem and it belongs to the “cutting and wrapping” class of problems. The complexity of the optimal design problems considered is conditioned by their belonging to the class of nondeterministic polynomial time hard problems, which does not allow solving them by precise methods and requires constructing approximate optimization methods and algorithms. It is efficient to use metaheuristic methods. The article examines “the first appropriate”, probabilistic, extremal, genetic and ant colony optimization algorithms. Their application will allow increasing the efficiency of the systems and reducing the expenditures for their designing and realization.

References

[1] Kantorovich L.V., Zalgaller V.A. Ratsional’nyy raskroy promyshlennykh materialov [Rational cutting of industrial materials]. Novosibirsk, Nauka Publ., 2012. 300 p.

[2] Yudakov P.V. The problem of three-dimensional packaging and methods for solving it. Inzhenernyy vestnik. Jelektr. nauchno-tekh. zhurn. [Engineering Bulletin. El. Publ. (MGTU im. N.E. Baumana)], 2015, no. 6 (in Russ.). Available at: http://engbul.bmstu.ru/doc/781936.html (accessed 15.09.2017).

[3] Zabelin S.L, Frolovskiy V.D. Development and the analysis of the approached methods of the decision optimization tasks skiving stock problem. Informatsionnye tekhnologii v proektirovanii i proizvodstve [Information technology of CAD/CAM/CAE (ITDP)], 2012, no. 3 (in Russ.). Available at: https://elibrary.ru/download/elibrary_16897548_69207742.pdf (accessed 15.09.2017).

[4] Chub I.A. Modeling and solving the optimization problem of placing flammable objects based on the placement region topography. Matematichne ta kompyuterne modelyuvannya [Radio Electronics, Computer Science, Control], 2013, no. 1, pp. 88–93 (in Russ.).

[5] Kureychik V.V., Glushchenko A.E., Orlov A.N. Hybrid approach for three-dimensional packaging problem. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, no. 6 (156), pp. 45–53 (in Russ.).

[6] Dorigo M. Optimization, learning and natural algorithms. PhD thesis. Politecnico di Milano, Italie, 2012.

[7] Zabelin S.L., Frolovskiy V.D., Zhegolko K.V. Development and investigation of genetic algorithm for project procedures automation of geometrical coverage optimization. Vestnik TGTU [Transactions of TSTU], 2015, vol. 21, no. 2 (in Russ.). Available at: http://vestnik.tstu.ru/rus/t_21/pdf/21_2_005.pdf

[8] Sravnenie algoritma dvumernykh matrits i murav’inogo algoritma dlya zadachi geometricheskogo pokrytiya. Available at: http://lab18.ipu.ru/projects/conf2010/1/21.htm (accessed 17.08.2017).

[9] Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Bioinspirirovannye metody v optimiziatsii [Bioinspired optimization techniques]. Moscow, Fizmatlit Publ., 2012. 380 p.

[10] Zabelin S.L., Frolovskiy V.D. Issledovanie metaevresticheskikh algoritmov dlya zadach optimal’nogo geometricheskogo pokrytiya. Perspektivnye informatsionnye tekhnologii v nauchnykh issledovaniyakh, proektirovanii i obuchenii, 2012. Available at: http://www.ssau.ru/files/science/conferences/pit2012/pit_12_0_6_v1_36.pdf (accessed 23.08.2017).