МНОГОУРОВНЕВЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ДВУМЕРНОЙ УПАКОВКИ ГЕОМЕТРИЧЕСКИХ ФИГУР СЛОЖНЫХ ФОРМ
Аннотация
Рассмотрена одна из важных комбинаторных задач оптимизации – задача двумер-
ной упаковки геометрических фигур сложных форм. Она относится к классу NP- сложных
и трудных оптимизационных задач. В работе приведена и описана постановка задачи дву-
мерной упаковки, введена комбинированная целевая функция, учитывающая все ограниче-
ния. В связи со сложностью данной задачи предлагается многоуровневый подход, заклю-
чающийся в разделение задачи двумерной упаковки на 4 подзадачb и решения каждой под-
задачи последовательно в строгом порядке. При этом для каждой из подзадач определен
уникальный набор объектов, не повторяющихся в остальных подзадачах. Для реализации
многоуровневого подхода авторами разработан комбинированный биоинспирированный
алгоритм, основанный методах генетического поиска и биоинспирированной оптимизации.
Такой подход позволяет значительно сократить время получения результата, частично
решить проблему предварительной сходимости алгоритмов и получить наборы квазиоти-
мальных решений за полиномиальное время. Разработан программный комплекс и реализо-
ваны на ЭВМ алгоритмы автоматизированной двухмерной упаковки на основе комбиниро-
ванного биоинспирированного алгоритма. Проведен вычислительный эксперимент на тес-
товых примерах (бенчмарках). Качество упаковки, полученное, на основе разработанного
комбинированного биоинспирированного алгоритма, в среднем на 2 % превосходит резуль-
таты упаковки, полученные с использованием известных алгоритмов при сопоставимом
времени решения, что говорит об эффективности предложенного подхода. Проведенные
серии тестов и экспериментов позволили уточнить теоретические оценки временной
сложности алгоритмов упаковки. В лучшем случае временная сложность алгоритмов
O(n2), в худшем случае - O(n3).
Литература
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.
