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

Л. Ф. Гуляницький; А. В. Дубіна

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

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

Автор(и)

Л. Ф. Гуляницький Iнститут кiбернетики iм. В.М. Глушкова НАН України, Україна https://orcid.org/0000-0002-1379-4132
А. В. Дубіна НТУУ «Київський полiтехнiчний iнститут iменi Iгоря Сiкорського», Україна https://orcid.org/0000-0001-8069-9664

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

Завантажити посилання

Номер

Том 38 № 1 (2021)

Розділ

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

Ліцензія

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.