Покращений гібридний алгоритм для квадратичної задачі про призначення

С. В. Чупов; А. В. Федорiшко

doi:10.24144/2616-7700.2026.48(1).243-253

Автор(и)

С. В. Чупов ДВНЗ «Ужгородський нацiональний унiверситет», Україна https://orcid.org/0000-0002-7715-3924
А. В. Федорiшко ДВНЗ «Ужгородський нацiональний унiверситет», Україна https://orcid.org/0009-0002-8921-0882

DOI:

https://doi.org/10.24144/2616-7700.2026.48(1).243-253

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

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

Анотація

Квадратична задача про призначення (QAP) є однiєю з найбiльш вивчених комбiнаторних задач оптимiзацiї з рiзними практичними застосуваннями. У цiй статтi ми представляємо покращений гiбридний алгоритм (IHBMA) для розв’язання QAP. IHBMA дослiджує простiр пошуку шляхом використання модифiкованого алгоритму 2-OPT, та схеми алгоритму BMA на окремих етапах розв’язання задачi. Експериментальнi оцiнки на множинi тестових задач типу “Taie” розмiрностi 125 та 175 показують, що запропонований пiдхiд здатний досягти та перевершувати найвiдомiшi на даний момент результати для всiх екземплярiв iз середнiм часом обчислення менше 2 години. Також надаються порiвняння, щоб показати конкурентоспроможнiсть запропонованого пiдходу вiдносно алгоритму HH-QAP для QAP.

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

Досл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ї

Посилання

Battiti, R., & Tecchiolli, G. (1994). The Reactive Tabu Search. ORSA J. on Computing, 6, 126–140.
Benlic, U., & Hao, J. K. (2013). Breakout local search for the quadratic assignment problem. Applied Mathematics and Computation, 219(9), 4800–4815.
Benlic, U., & Hao, J. K. (2015). Memetic search for the quadratic assignment problem. Expert Systems with Applications, 42(1), 584–595.
Burkard, R. E. (1984). Quadratic assignment problems. European J. of Oper. Res. 15, 283–289.
Burkard, R. E., Karisch, S. E., & Rendl, F. (1997). Qaplib – a quadratic assignment problem library. Journal of Global optimization, 10, 391–403.
Drezner, Z., Hahn, P. M., & Taillard, E. D. (2005). Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for metaheuristic methods. Annals of Operations research, 139, 65–94.
Glover, F. (1989). Tabu Search – Part I, ORSA J. on Computing, 1(3), 190–206.
Glover, F. (1990). Tabu Search – Part II, ORSA J. on Computing, 2(1), 4–32.
Koopmans, T. C., & Beckmann, M. J. (1957). Assignment problems and the location of economic activities. Econometrica, 25, 53–76.
Laurent, M., & Seminaroti, M. (2015). The quadratic assignment problem is easy for robinsonian matrices with toeplitz structure. Operations Research Letters, 43(1), 103–109.
Misevicius, A. (2004). An improved hybrid genetic algorithm: New results for the quadratic assignment problem. Knowledge Based Systems, 17(2–4), 65–73.
Misevicius, A. (2012). An implementation of the iterated tabu search algorithm for the quadratic assignment problem. OR Spectrum, 34(3), 665–690.
Sahni, S., & Gonzalez, T. (1976). P-complete approximation problems. J. of the ACM, 23, 555–565.
Stutzle, T., & Fernandes, S. (2004). New benchmark instances for the qap and the experimental analysis of algorithms. In European Conference on Evolutionary Computation in Combinatorial Optimization. Springer, 199–209.
Taillard, E. (1991). Robust taboo search for the quadratic assignment problem. Parallel Computing, 17, 443–455.
Taillard, E. D. (1995). Comparison of iterative searches for the quadratic assignment problem. Location science, 3(2), 87–105.
Zhang, Q., Sun, J., Tsang, E., & Ford, J. (2006). Estimation of Distribution Algorithm with 2-opt Local Search for the Quadratic Assignment Problem. In: Lozano, J. A., Larranaga, P., Inza, I., Bengoetxea, E. (eds). Towards a New Evolutionary Computation. Studies in Fuzziness and Soft Computing, (Vol. 192). Springer: Berlin, Heidelberg. https://doi.org/10.1007/3-540-32494-1_12
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 [in Ukrainian].
Shylo, V. P., Chupov, S. V., Boyarchuk, D. O., & Shylo, P. V. (June 3–5, 2018) New approaches to solving the quadratic assignment problem. In the book: VII International Scientific and Practical Conference “Mathematics. Information Technologies. Education.” : Abstracts of reports. Lutsk – Svityaz. Lutsk: Lesya Ukrainka Eastern European National University, 121–122 [in Ukrainian].
Wang, H., & Alidaee, B. (2023). A New Hybrid-heuristic for Large-scale Combinatorial Optimization: A Case of Quadratic Assignment Problem, Computers & Industrial Engineering, 179(1), 109220.
Misevicius, A., & Kilda, B. (2005). Comparison of crossover operators for the quadratic assignment problem, Information Technology And Control, 34(2), 109–119.
Chupov, S. V., & Fedorishko, A. V. (2025). Hybrid algorithm for solving the quadratic assignment problem. Scientific Bulletin of Uzhgorod University. Series "Mathematics and Computer Science". 47(2), 303–311. https://doi.org/10.24144/2616-7700.2025.47(2).303-311