Розв'язування задачі розміщення прямокутників на напівнескінченній стрічці алгоритмами локального та табуйованого пошуку

Автор(и)

DOI:

https://doi.org/10.24144/2616-7700.2021.38(1).123-136

Ключові слова:

оптимiзацiя розмiщення, локальний пошук, табуйований пошук, комбiнаторна оптимiзацiя

Анотація

В роботі розглянуто алгоритми стандартного локального та табуйованого пошуку для розв'язування задачі розміщення прямокутників на напівнескінченній стрічці. Особливостями задачі є наявність заборонених областей (дірок), які впливають на ефективність роботи алгоритмів. Досліджувана задача має значну теоретичну цінність і важливе прикладне значення. Ця задача належить до задач NP-повних і більшість методів розв’язування є наближеними.

Експериментально досліджено ефективність запропонованих алгоритмів для задачі розміщення прямокутників. Визначено рекордні значення цільової функції, дисперсію, довірчі інтервали та час роботи алгоритмів для задач з різними параметрами.

Посилання

Fuentes, G.E.A., Gress, E.S.H., Mora, J.C.S.T., & Marin, J.M. (2018). Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic. PLoS ONE 13(8), e0201868. https://doi.org/10.1371/journal.pone.0201868.

Hoos, H.H., & St¨utzle, T. (2004). Stochastic local search: Foundations and applications. Elsevier.

Song, T., Liu, S., Tang, X., Peng, X., & Chen, M. (2018). An iterated local search algorithm for the University Course Timetabling Problem. Applied Soft Computing, 68, 597-608. https://doi.org/10.1016/j.asoc.2018.04.034.

Handbook of metaheuristics. (2019). Cham: Springer.

Sergienko, I.V., Hulianitskyi, L.F., & Malyshko, S.A. (1989). About the decision of problems of placement of one class. Economics and Mathematical Methods, XXV, 3, 560-564 [in Russian].

Hulianitskyi, L., & Dubina, A. (2020). Local search algorithms and taboo search for the task of placing rectangles. Scientific support of technological progress of the XXI century: materials of the international scientific conference (Vol. 2), May 1, 2020. Chernivtsi, Ukraine, 48-53 [in Ukrainian].

Hulianitskyi, L.F., & Mulesa, O. Y. (2016). Applied methods of combinatorial optimization. Publishing and Printing Center "Kyiv University" [in Ukrainian].

##submission.downloads##

Опубліковано

2021-05-27

Як цитувати

Гуляницький, Л. Ф., & Дубіна, А. В. (2021). Розв’язування задачі розміщення прямокутників на напівнескінченній стрічці алгоритмами локального та табуйованого пошуку. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 38(1), 123–136. https://doi.org/10.24144/2616-7700.2021.38(1).123-136

Номер

Розділ

Iнформатика, комп’ютернi науки та прикладна математика