Call for Paper - January 2023 Edition
IJCA solicits original research papers for the January 2023 Edition. Last date of manuscript submission is December 20, 2022. Read More

Quadratic Assignment Problem and its Relevance to the Real World: A Survey

Print
PDF
International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 96 - Number 9
Year of Publication: 2014
Authors:
Ravi Kumar Bhati
Akhtar Rasool
10.5120/16825-6584

Ravi Kumar Bhati and Akhtar Rasool. Article: Quadratic Assignment Problem and its Relevance to the Real World: A Survey. International Journal of Computer Applications 96(9):42-47, June 2014. Full text available. BibTeX

@article{key:article,
	author = {Ravi Kumar Bhati and Akhtar Rasool},
	title = {Article: Quadratic Assignment Problem and its Relevance to the Real World: A Survey},
	journal = {International Journal of Computer Applications},
	year = {2014},
	volume = {96},
	number = {9},
	pages = {42-47},
	month = {June},
	note = {Full text available}
}

Abstract

The Quadratic Assignment Problem (QAP) is the well known and significant combinatorial optimization problem. For several decades, it has been of keen interest for researchers and its improvement is still in progress. QAP is very important because it plays an important role in various complex real world problems. In this survey some of the prominent applications of QAP are illustrated which have been optimally applied to real world problems in diverse areas. Here inherent descriptions of various applications are summarized by highlighting the shortcomings of their applications related to QAP. This paper gives the future directions and strong conclusions on the survey of quadratic assignment problem and justify that the performance improvement of QAP is important.

References

  • Burkard RE, Cela E, Pardalos PM, Pitsoulis LS, "The quadratic assignment problem: Handbook of combinatorial optimization", vol. 3. Kluwer; pp. 241–337, 1998.
  • Clayton W. Commander, "A Survey of the Quadratic Assignment Problem, with Applications", Morehead Electronic Journal of Applicable Mathematics Issue 4-MATH-2005-01.
  • Talbi, El-Ghazali, "Metaheuristics: From Design to Implementation", Hoboken, N. J. : John Wiley & Sons, 2009.
  • Bazaraa, M. S. , Kirca, O, "A branch-and-bound based heuristic for solving the quadratic assignment problem", Naval Research Logistics Quarterly 30, 287–304,1983.
  • Christofides N. , Benavent E. , " An exact algorithm for the quadratic assignment problem", Operations Research 37 (5), 760–768,1989.
  • Bazaraa, M. S. , Sherali, H. D. , "On the use of exact and heuristic cutting plane methods for the quadratic assignment problem", Journal of the Operational Research Society 33, 991–1003,1982.
  • Padberg, M. W. , Rinaldi, G. , "A branch-and-cut algorithm for the resolution of large-scale symmetric travelling salesman problems", SIAM Review 33, 60–100,1991.
  • Nawaz, M. , Enscore Jr. , E. E. , Ham, I. , "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem", OMEGA The International Journal of Management Science 11 (1), 91–95, 1983.
  • Mahdi Bashiri and Hossein Karimi, "Effective heuristics and meta-heuristics for the quadratic assignment problem with tuned parameters and analytical comparisons", Journal of Industrial Engineering International 2012, 8:6.
  • Vittorio Maniezzo and Alberto Colorni, "The Ant System Applied to the Quadratic Assignment Problem", IEEE transactions on knowledge and data engineering, VOL. 11, NO. 5, pp. 769-778, SEPTEMBER/OCTOBER 1999.
  • Uwate, Y. , Nishio, Y. , Ushida, A. , "Markov chain modeling of intermittency chaos and its application to Hopfield NN", IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E87A (4), 774–779, 2004.
  • Zvi Drezner, "A New Genetic Algorithm for the Quadratic Assignment Problem", INFORMS Journal on Computing, Vol. 15, No. 3, pp. 320–330, Summer 2003.
  • Cung, V. -D. , Mautor, T. , Michelon, P. , Tavares, A. , "A scatter search based approach for the quadratic assignment problem", In: Proceedings of IEEE International Conference on Evolutionary Computation, pp. 165–169, 1997.
  • Wilhelm, M. R. , Ward, T. L. , "Solving quadratic assignment problems by simulated annealing", IEEE Transactions 19, 107–119,1987.
  • Glover, F. , 1989a. Tabu search—Part I. ORSA Journal on Computing 1, 190–206.
  • Glover, F. , 1989b. Tabu search—Part II. ORSA Journal on Computing 2, 4–32.
  • Oliveira, C. A. S. , Pardalos, M. P. , Resende, M. G. G. , "GRASP with path relinking for the quadratic assignment problem In: Experimental and Efficient Algorithms", Third International Workshop (WEA 2004), Brazil, LNCS 3059. Springer, pp. 356–368, 2004.
  • Ramkumar AS, Ponnambalam SG, Jawahar N, Suresh RK, "Iterated fast local search algorithm for quadratic assignment problems", Robot Comput Integr Manuf 2008. doi:10. 1016/j. rcim. 2007. 01. 004.
  • A. N. Elshafei, "Hospital layout as a quadratic assignment problem", Operations Research Quarterly 28, 167–179, 1977.
  • L. Steinberg, "The Backboard Wiring Problem: A Placement Algorith",. SIAM Review 3 37-50, 1961.
  • Dickey, J. W. , Hopkins, J. W. , "Campus building arrangement using Topaz", Transportation Research 6, 59–68, 1972.
  • Heffley, D. R. , "Decomposition of the Koopmans–Beckmann problem", Regional Science and Urban Economics 10 (4), 571–580, 1980.
  • Francis, R. L. , White, J. A. , "Facility Layout and Location: An Analytical Approach", Prentice-Hall, Englewood Cliffs, NJ, 1974.
  • Krarup, J. , Pruzan, P. M. , "Computer-aided layout design", Mathematical Programming Study 9, 75–94, 1978.
  • Hubert, L. , "Assignment methods in combinatorial data analysis", Statistics: Textbooks and Monographs Series, vol. 73. Marcel Dekker, 1987.
  • Forsberg, J. H. , Delaney, R. M. , Zhao, Q. , Harakas, G. , Chandran, R. , "Analyzing lanthanide-included shifts in the NMR spectra of lanthanide (III) complexes derived from 1,4,7,10-tetrakis (N,N-diethylacetamido)-1,4,7,10-tetraazacyclododecane", Inorganic Chemistry 34, 3705–3715, 1994.
  • Brusco, M. J. , Stahl, S. , "Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices", Journal of Classification 17 (2), 197–223, 2000.
  • H. A. Eiselt and Gilbert Laporte, "A combinatorial optimization problem arising in dartboard design", The Journal of the Operational Research Society, Vol. 42, No. 2, pp. 113-118, Feb. , 1991.
  • Hanan, M. and J. M. Kurtzberg, "A Review of the Placement and Quadratic Assignment Problems", SIAM Review 14, 324-342, 1972.
  • T. C. Koopmans and M. J. Beckmann, "Assignment problems and the location of economic activities", Econometrica 25, pp. 53–76, 1957.
  • http://www. neos-guide. org/content/qap4
  • M. Motaghi, A. Hamzenejad, L. Riyahi, M. Soheili Kashani, "Optimization of Hospital Layout through the Application of Heuristic Techniques (Diamond Algorithm) in Shafa Hospital (2009)", Int. J. Manag. Bus. Res. , 1 (3), 133-138, Summer 2011.
  • Brixius, N. W. and K. M. Anstreicher, "The Steinberg Wiring Problem", To appear in, The Sharpest Cut, M. GrÄotschel, ed. , SIAM, 2001.
  • Clayton W. Commander, "A Survey of the Quadratic Assignment Problem, with Applications", Morehead Electronic Journal of Applicable Mathematics Issue 4 --MATH-2005-01.
  • Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, Tania Querido, "A survey for the quadratic assignment problem", European Journal of Operational Research 176 (2007) 657–690