Abstract
The quadratic assignment problem is among the harder combinatorial optimization problems in that even small instances might be difficult to solve and for different algorithms different instances pose challenges to solve. Research on the quadratic assignment problem has thus focused on developing methods that defy the problem’s variety and that can solve a vast number of instances effectively. The topic of this work is to compare the performance of well-known “standard” metaheuristics with specialized and adapted metaheuristics and analyze their behavior. Empirical validation of the results is performed on a highly diverse set of instances that are collected and published in form of the quadratic assignment problem library. The data in these instances come from real-world applications on the one hand and from randomly generated sources on the other hand.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Affenzeller, M., Wagner, S.: Offspring selection: A new self-adaptive selection scheme for genetic algorithms. In: Ribeiro, B., Albrecht, R.F., Dobnikar, A., Pearson, D.W., Steele, N.C. (eds.) Adaptive and Natural Computing Algorithms. Springer Computer Series, pp. 218–221. Springer (2005)
Affenzeller, M., Winkler, S., Wagner, S., Beham, A.: Genetic Algorithms and Genetic Programming - Modern Concepts and Practical Applications. Numerical Insights. CRC Press (2009)
Angel, E., Zissimopoulos, V.: On the landscape ruggedness of the quadratic assignment problem. Theoretical Computer Science 263(1-2), 159–172 (2001)
Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB - A quadratic assignment problem library. Journal of Global Optimization 10(4), 391–403 (1997)
Chicano, F., Luque, G., Alba, E.: Autocorrelation measures for the quadratic assignment problem. Applied Mathematics Letters 25, 698–705 (2012)
Czech, Z.J.: Statistical measures of a fitness landscape for the vehicle routing problem. In: Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2008 (2008)
de Carvalho Jr., S.A., Rahmann, S.: Microarray layout as quadratic assignment problem. In: Proceedings of the German Conference on Bioinformatics (GCB). Lecture Notes in Informatics, vol. P-83 (2006)
Drezner, Z.: Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem. Computers & Operations Research 35, 717–736 (2008)
Drezner, Z., Hahn, P.M., Taillard, E.D.: Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult to solve for meta-heuristic methods. Annals of Operations Research 139, 65–94 (2005)
Elshafei, A.N.: Hospital layout as a quadratic assignment problem. Operational Research Quarterly 28(1), 167–179 (1977)
Fogel, D.: An evolutionary approach to the traveling salesman problem. Biological Cybernetics 60, 139–144 (1988)
Glover, F.: Tabu search – part I. ORSA Journal on Computing 1(3), 190–206 (1989)
Hahn, P.M., Krarup, J.: A hospital facility layout problem finally solved. Journal of Intelligent Manufacturing 12, 487–496 (2001)
James, T., Rego, C., Glover, F.: Multistart tabu search and diversification strategies for the quadratic assignment problem. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans 39(3), 579–596 (2009)
Koopmans, T.C., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica, Journal of the Econometric Society 25(1), 53–76 (1957)
Merz, P., Freisleben, B.: A genetic local search approach to the quadratic assignment problem. In: Proceedings of the Seventh International Conference on Genetic Algorithms, pp. 465–472. Citeseer (1997)
Merz, P., Freisleben, B.: Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Transactions on Evolutionary Computation 4(4), 337–352 (2000)
Pitzer, E., Affenzeller, M., Beham, A.: A closer look down the basins of attraction. In: UK Conference on Computational Intelligence (2010) (in press)
Stutzle, T.: Iterated local search for the quadratic assignment problem. European Journal of Operational Research 174, 1519–1539 (2006)
Taillard, E.D.: Robust taboo search for the quadratic assignment problem. Parallel Computing 17, 443–455 (1991)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Beham, A., Affenzeller, M., Pitzer, E. (2015). Metaheuristic Algorithms for the Quadratic Assignment Problem: Performance and Comparison. In: Klempous, R., Nikodem, J. (eds) Innovative Technologies in Management and Science. Topics in Intelligent Engineering and Informatics, vol 10. Springer, Cham. https://doi.org/10.1007/978-3-319-12652-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-12652-4_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12651-7
Online ISBN: 978-3-319-12652-4
eBook Packages: EngineeringEngineering (R0)