УДК 519.854
ПРО РОЗВ’ЯЗАННЯ КВАДРАТИЧНОЇ ЗАДАЧІ
ПРО ПРИЗНАЧЕННЯ
Анотація. Запропоновано дві модифікації повторюваного ітерованого алгоритму табу розв’язання квадратичної задачі про призначення (з технологією виділення ядра і без неї). Проведено дослідження цих модифікацій порівняно з кращими сучасними алгоритмами розв’язання цієї задачі. Показано ефективність розроблених алгоритмів, зокрема, для задач великої розмірності, для яких з їхньою допомогою знайдено нові рекорди.
Ключові слова: квадратична задача про призначення, повторюваний ітерований табу-пошук, технологія виділення ядра розв’язку, випадкове збурення компонент розв’язку, ефективність алгоритмів.
ПОВНИЙ ТЕКСТ
Сергієнко Іван Васильович,
академік НАН України, доктор фіз.-мат. наук, професор, директор Інституту кібернетики
ім. В.М. Глушкова НАН України, Київ, 
incyb@incyb.kiev.ua
Шило Володимир Петрович,
доктор фіз.-мат. наук, професор, провідний науковий співробітник Інституту кібернетики
ім. В.М. Глушкова НАН України, Київ, v.shylo@gmail.com
Чупов Сергій Вікторович,
кандидат фіз.-мат. наук, доцент кафедри Державного вищого навчального закладу «Ужгородський національний університет»,
serhii.chupov@uzhnu.edu.ua, sergey.chupov@gmail.com
Шило Петро Володимирович,
кандидат фіз.-мат. наук, науковий співробітник Інституту кібернетики ім. В.М. Глушкова НАН України, Київ,
petershylo@gmail.com
СПИСОК ЛІТЕРАТУРИ
- Koopmans T.C., Beckmann M.J. Assignment problems and the location of economic activities. Econometrica. 1957. Vol. 25, N 1. P. 53–76.
- Steinberg L. The backboard wiring problem: a placement algorithm. SIAM Review. 1961. Vol. 3, N 1. P. 37–50.
- Nugent Ch.E., Vollmann Th.E., Ruml J. An experimental comparison of techniques for the assignment of facilities to locations. Oper. Res. 1968. Vol. 16. P. 150–173.
- Sahni S., Gonzalez T. P-complete approximation problems. J. of the ACM. 1976. Vol. 23, N 3. P. 555–565.
- Burkard R.E. Quadratic assignment problems. European J. of Oper. Res. 1984. Vol. 15, N 3. P. 283–289.
- Beasley J.E. OR-library; distributing test problems by electronic mail. J. of Oper. Res. Society. 1990. Vol. 41, N 11. P.1069–1072.
- Glover F. Tabu Search — Part I. ORSA J. on Computing. 1989. Vol. 1, N 3. P. 190–206.
- Glover F. Tabu Search — Part ІI. ORSA J. on Computing. 1990. Vol. 2, N 1. P. 4–32.
- Taillard E. Robust taboo search for the quadratic assignment problem. Parallel Computing. 1991. Vol. 17, Iss. 4-5. P. 443–455.
- Battiti R., Tecchiolli G. The reactive tabu search. ORSA J. on Computing. 1994. Vol. 6, N 2. P. 126–140.
- Misevicius A., Lenkevicius A., Rubliauskas D. Iterated tabu search: An improvement to standard tabu search. Information Technology and Control. 2006. Vol. 35, N 3. P. 187–197.
- Benlic U., Hao J.K. Breakout local search for the quadratic assignment problem. Applied Math. And Computation. 2013. Vol. 219, N 9. P. 4800–4815.
- Benlic U., Hao J.K. Memetic search for the quadratic assignment problem. Expert Systems with Applications. 2015. Vol. 42, N 1. P. 584–595.
- Misevicius A. An improved hybrid genetic algorithm: New results for the quadratic assignment problem. Knowledge Based Systems. 2004. Vol. 17, N 2–4. P. 65–73.
- Misevicius A. An implementation of the iterated tabu search algorithm for the quadratic assignment problem. OR Spectrum. 2012. Vol. 34, N 3. P. 665–690.
- Шило П.В. Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях. Кибернетика и системный анализ. 2017. Т. 53, № 2. С. 163–167.
- Сергиенко И.В., Шило В.П. Технология ядра для решения задач дискретной оптимизации. Кибернетика и системный анализ. 2017. Т. 53, № 6. С. 73–83.
