{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,4]],"date-time":"2026-01-04T12:46:11Z","timestamp":1767530771084,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2024,11,28]],"date-time":"2024-11-28T00:00:00Z","timestamp":1732752000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The generalized quadratic assignment problem (GQAP) involves assigning a set of facilities to a set of locations such that the sum of the assignment and transportation costs is minimized. Unlike the traditional one-to-one assignment problem, the GQAP is a many-to-one assignment problem. That is, multiple facilities can be assigned to each location without exceeding the capacity of the location. This research was motivated by the problem of assigning multiple facilities (e.g., machines or equipment) to locations at manufacturing plants. Another well-known application of the GQAP includes the assignment of facilities (i.e., containers) to locations (i.e., storage areas) in container yards. This paper presents simple but very effective approximation algorithms for solving real-world, large-size GQAP instances quickly without spending a lot of time setting the algorithm parameters, since there are few parameters to set. More specifically, a construction algorithm is used to generate an initial solution for the proposed problem, and the initial solution is improved using a simulated annealing algorithm. The performance of the proposed algorithms is tested with respect to solution quality and computation time on a set of test problems available in the literature. The results show the effectiveness of the proposed algorithms.<\/jats:p>","DOI":"10.3390\/a17120540","type":"journal-article","created":{"date-parts":[[2024,11,28]],"date-time":"2024-11-28T07:28:01Z","timestamp":1732778881000},"page":"540","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Simulated Annealing Algorithm for the Generalized Quadratic Assignment Problem"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9945-3370","authenticated-orcid":false,"given":"Alan","family":"McKendall","sequence":"first","affiliation":[{"name":"Department of Industrial & Management Systems Engineering, West Virginia University, 1306 Evansdale Drive, P.O. Box 6107, Morgantown, WV 26506, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-1002-096X","authenticated-orcid":false,"given":"Yugesh","family":"Dhungel","sequence":"additional","affiliation":[{"name":"Department of Industrial & Management Systems Engineering, West Virginia University, 1306 Evansdale Drive, P.O. Box 6107, Morgantown, WV 26506, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,11,28]]},"reference":[{"key":"ref_1","first-page":"123","article-title":"A Survey of the Generalized Assignment Problem and Its Applications","volume":"45","year":"2007","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"ref_2","unstructured":"Lee, C.G., and Ma, Z. (2004). The generalized quadratic assignment problem. Research Report, Department of Mechanical and Industrial Engineering, University of Toronto."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/j.ejor.2014.03.015","article-title":"A new mixed integer programming model for curriculum balancing: Application to a Turkish university","volume":"238","author":"Uysal","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s10479-018-3092-8","article-title":"Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0\u20131 optimization problems with linear constraints","volume":"286","author":"Guignard","year":"2020","journal-title":"Ann. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s10589-007-9093-1","article-title":"An algorithm for the generalized quadratic assignment problem","volume":"40","author":"Hahn","year":"2008","journal-title":"Comput. Optim. Appl."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.ejor.2010.02.006","article-title":"Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique","volume":"206","author":"Pessoa","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"106802","DOI":"10.1016\/j.engappai.2023.106802","article-title":"An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem","volume":"126","author":"Wong","year":"2023","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","article-title":"P-complete approximation problems","volume":"23","author":"Sahni","year":"1976","journal-title":"J. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1287\/ijoc.1040.0128","article-title":"A memetic heuristic for the generalized quadratic assignment problem","volume":"18","author":"Cordeau","year":"2006","journal-title":"INFORMS J. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1678","DOI":"10.1016\/j.jss.2010.04.070","article-title":"A novel global harmony search algorithm for task assignment problem","volume":"83","author":"Zou","year":"2010","journal-title":"J. Syst. Softw."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s10732-010-9144-0","article-title":"GRASP with path-relinking for the generalized quadratic assignment problem","volume":"17","author":"Mateus","year":"2011","journal-title":"J. Heuristics"},{"key":"ref_12","first-page":"221","article-title":"A tabu search heuristic for a generalized quadratic assignment problem","volume":"34","author":"McKendall","year":"2017","journal-title":"J. Ind. Prod. Eng."},{"key":"ref_13","unstructured":"Mostafa, R. (2020). Metaheuristics for the Generalized Quadratic Assignment Problem. [Master\u2019s Thesis, West Virginia University]. Available online: https:\/\/researchrepository.wvu.edu\/etd\/7717."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1066","DOI":"10.1016\/j.ejor.2020.11.035","article-title":"Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search","volume":"292","author":"Silva","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Greistorfer, P., Stan\u011bk, R., and Maniezzo, V. (2022). A Tabu Search Matheuristic for the Generalized Quadratic Assignment Problem. Metaheuristics International Conference, Springer International Publishing.","DOI":"10.1007\/978-3-031-26504-4_46"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirpatrick","year":"1983","journal-title":"Science"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2431","DOI":"10.1016\/j.cor.2005.02.021","article-title":"Simulated annealing heuristics for the dynamic facility layout problem","volume":"33","author":"McKendall","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Huo, L., Zhu, J., Wu, G., and Li, Z. (2020). A novel simulated annealing based strategy for balanced UAV task assignment and path planning. Sensors, 20.","DOI":"10.3390\/s20174769"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"120374","DOI":"10.1016\/j.eswa.2023.120374","article-title":"The home health care location-routing problem with a mixed fleet and battery swapping stations using a competitive simulated annealing algorithm","volume":"228","author":"Dai","year":"2023","journal-title":"Expert Syst. Appl."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"109004","DOI":"10.1016\/j.cie.2023.109004","article-title":"A simulated annealing approach for the circle bin packing problem with rectangular items","volume":"176","author":"Tole","year":"2023","journal-title":"Comput. Ind. Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"122008","DOI":"10.1016\/j.eswa.2023.122008","article-title":"Scheduling of log logistics using a metaheuristic approach","volume":"238","author":"Ghotb","year":"2024","journal-title":"Expert Syst. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"van Laarhoven, P.J.M., and Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications, D. Reidel Publishing Company. [1st ed.].","DOI":"10.1007\/978-94-015-7744-1"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Siarry, P. (2016). Simulated Annealing. Metaheuristics, Springer International Publishing.","DOI":"10.1007\/978-3-319-45403-0"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-319-91086-4_1","article-title":"Simulated Annealing: From Basics to Applications","volume":"Volume 272","author":"Gendreau","year":"2019","journal-title":"Handbook of Metaheuristics"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/12\/540\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:41:36Z","timestamp":1760114496000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/12\/540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,28]]},"references-count":24,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["a17120540"],"URL":"https:\/\/doi.org\/10.3390\/a17120540","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,11,28]]}}}