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

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

doi:10.24144/2616-7700.2025.47(2).303-311

Автор(и)

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

DOI:

https://doi.org/10.24144/2616-7700.2025.47(2).303-311

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

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

Анотація

Квадратична задача про призначення (QAP) є однiєю з найбiльш вивчених комбiнаторних задач оптимiзацiї з рiзними практичними застосуваннями. У цiй статтi ми представляємо наближений гiбридний алгоритм (HBMA) для розв’язання QAP. HBMA дослiджує простiр пошуку шляхом використання вiдомих алгоритмiв 2-OPT, BLS та BMA на окремих етапах розв’язання задачi. Експериментальнi оцiнки на множинi еталонних задач з QAPLIB показують, що запропонований пiдхiд здатний досягти найвiдомiших на даний момент результатiв для всiх екземплярiв, крiм окремих задач типу taia, iз середнiм часом обчислення менше 1 години. Також надаються порiвняння, щоб показати конкурентоспроможнiсть запропонованого пiдходу вiдносно алгоритмiв BLS та BMA для QAP.

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

С. В. Чупов, ДВНЗ «Ужгородський нац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. Springer. Berlin: Heidelberg, 192. 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: VII International Scientific and Practical Conference “Mathematics. Information Technologies. Education.” Abstracts of reports. Lutsk: Lesya Ukrainka Eastern European National University. Lutsk: Svityaz, 121–122 [in Ukrainian].