UDC 519.854
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 incyb@incyb.kiev.ua
|
2 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
v.shylo@gmail.com
|
|
|
4 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
petershylo@gmail.com
|
SOLVING THE QUADRATIC ASSIGNMENT PROBLEM
Abstract. This paper focuses on the development and improvement of the iterated repeated tabu algorithms for solving the quadratic assignment problem using core allocation technology. The comparative analysis of the empirical computational performance is presented, comparing the modern algorithms from the literature and the algorithms proposed in this paper. The results confirm the efficiency of the modified algorithms in terms of the solution quality and time especially for large-scale problems.
Keywords: quadratic assignment problem, repeated iterated tabu search, solution core allocation technology, random perturbation of solution components, algorithm efficiency.
FULL TEXT
REFERENCES
- 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.
- Shilo P.V. Repeatable iterated taboo algorithm for solving the quadratic assignment problem. Kibernetika i sistemnyj analiz. 2017. Vol. 53, N 2. P. 163–167.
- Sergienko I.V., Shilo V.P. Kernel technology for solving discrete optimization problems. Kibernetika i sistemnyj analiz. 2017. Vol. 53, N 6. P. 73–83.
