Симуляція відпалу для квадратичної задачі про призначення на основі лексикографічно впорядкованих перестановок

С. В. Чупов; О. І. Кузка; В. М. Дуран

doi:10.24144/2616-7700.2026.49(2).300-307

Автор(и)

С. В. Чупов ДВНЗ «Ужгородський нацiональний унiверситет», Україна https://orcid.org/0000-0002-7715-3924
О. І. Кузка ДВНЗ «Ужгородський нацiональний унiверситет», Україна https://orcid.org/0000-0002-7556-3057
В. М. Дуран ДВНЗ «Ужгородський нацiональний унiверситет», Україна https://orcid.org/0009-0001-6409-3061

DOI:

https://doi.org/10.24144/2616-7700.2026.49(2).300-307

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

Квадратична задача про призначення, евристичний алгоритм пошуку, метод симуляції відпалу, локальний алгоритм наближеного пошуку, позиційне представлення перестановок, ефективність алгоритмів

Анотація

Квадратична задача про призначення (QAP) є однiєю з найбiльш вивчених комбiнаторних задач оптимiзацiї з рiзними практичними застосуваннями. У цiй статтi ми представляємо адаптивний алгоритм симуляцiї вiдпалу (ASAQAP) для розв’язання QAP, що використовує спецiальний запис перестановок, названий позицiйним представленням. Це дозволяє здiйснювати арифметичнi операцiї над перестановками поданими у позицiйному видi. ASAQAP дослiджує простiр пошуку шляхом використання адаптивної симуляцiї вiдпалу, та локального табу пошуку на окремих етапах розв’язання задачi. Експериментальнi оцiнки на множинi тестових задач типу “Taie” розмiрностi 27, 45 та 75 показують, що запропонований пiдхiд здатний досягти вiдомi на даний момент результати для всiх екземплярiв iз придатним середнiм часом обчислення. Також надаються порiвняння, щоб показати конкурентоспроможнiсть запропонованого пiдходу вiдносно алгоритму CPTSQAP.

Спонсор дослідження

Дослiдження здiйснено в рамках кафедральної науково-дослiдної роботи «Моделi i методи системного аналiзу в мiждисциплiнарних дослiдженнях» (державний облiковий номер 0125U003246).

Біографії авторів

С. В. Чупов, ДВНЗ «Ужгородський нацiональний унiверситет»

Доцент кафедри системного аналiзу та теорiї оптимiзацiї. Кандидат фiзико-математичних наук, доцент

О. І. Кузка, ДВНЗ «Ужгородський нацiональний унiверситет»

Доцент кафедри системного аналiзу та теорiї оптимiзацiї. Кандидат фiзико-математичних наук, доцент

В. М. Дуран, ДВНЗ «Ужгородський нацiональний унiверситет»

Аспірант кафедри системного аналізу та теорії оптимізації

Посилання

Battiti, R., & Tecchiolli, G. (1994). The Reactive Tabu Search. ORSA J. on Computing, 6, 126–140. https://doi.org/10.1287/ijoc.6.2.126
Chupov S. V. (2016). Lexicographically ordered permutations. Computer mathematics, Kyiv: Institute of Cybernetics of V. M. Glushkov NAS of Ukraine, (2), 151–161.
Chupov, S. V., & Fedorishko, A. V. (2026). Improved hybrid algorithm for the quadratic assignment problem. Scientific Bulletin of Uzhhorod University. Series "Mathematics and Computer Science 48(1), 243–253. https://doi.org/10.24144/2616-7700.2026.48(1).243-253
Ingber, L. (1996). Adaptive Simulated Annealing (ASA): Lessons Learned. Control and Cybernetics, 25(1), 33–54. https://doi.org/10.48550/arXiv.cs/0001018
James, T., Rego, C., & Glover, F. (2009). A cooperative parallel tabu search algorithm for the quadratic assignment problem. European Journal of Operational Research, 195(3), 810–826. https://doi.org/10.1016/j.ejor.2007.06.061
Misevicius, A. (2012). An implementation of the iterated tabu search algorithm for the quadratic assignment problem. OR Spectrum, 34(3), 665–690. https://doi.org/10.1007/s00291-011-0274-z
Taillard, E. (1991). Robust taboo search for the quadratic assignment problem. Parallel Computing, 17, 443–455. https://doi.org/10.1016/S0167-8191(05)80147-4
Sergienko, I. V., & Shylo, V. P. (2003). Discrete optimization problems. Problems, solution methods, research. Kyiv: Naukova Dumka.
Sergienko, I. V., Shylo, V. P., Chupov, S. V., & Shylo, P. V. (2020). On solving the quadratic assignment problem. Cybernetics and Systems Analysis, (1), 64–69. https://doi.org/10.1007/s10559-020-00219-8 [in Ukrainian].