a comprehensive review of quadratic assignment problem variants hybrids and applications

A comprehensive review of quadratic assignment problem: variants, hybrids and applications

Search citation statements

Paper Sections

Citation Types

Year Published

Publication Types

Relationship

Cited by 39 publication s

References 176 publication s, exact extended formulation of the linear assignment problem (lap) polytope for solving the traveling salesman and quadratic assignment problems.

We present an O(n 6 ) linear programming model for the traveling salesman (TSP) and quadratic assignment (QAP) problems. The basic model is developed within the framework of the TSP. It does not involve the city-to-city variables-based, traditional TSP polytope referred to in the literature as "the TSP polytope." We do not model explicit Hamiltonian cycles of the cities. Instead, we use a time-dependent abstraction of TSP tours and develop a direct extended formulation of the linear assignment problem (LAP) polytope. The model is exact in the sense that it has integral extreme points which are in one-to-one correspondence with TSP tours. It can be solved optimally using any linear programming (LP) solver, hence offering a new (incidental) proof of the equality of the computational complexity classes "P " and "N P ." The extensions of the model to the time-dependent traveling salesman problem (TDTSP) as well as the quadratic assignment problem (QAP) are straightforward. The reasons for the non-applicability of existing negative extended formulations results for "the TSP polytope" to the model in this paper as well as our software implementation and the computational experimentation we conducted are briefly discussed.

A Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem

In this paper, we present a hybrid genetic-hierarchical algorithm for the solution of the quadratic assignment problem. The main distinguishing aspect of the proposed algorithm is that this is an innovative hybrid genetic algorithm with the original, hierarchical architecture. In particular, the genetic algorithm is combined with the so-called hierarchical (self-similar) iterated tabu search algorithm, which serves as a powerful local optimizer (local improvement algorithm) of the offspring solutions produced by the crossover operator of the genetic algorithm. The results of the conducted computational experiments demonstrate the promising performance and competitiveness of the proposed algorithm.

A new hybrid approach based on discrete differential evolution algorithm to enhancement solutions of quadratic assignment problem

The Combinatorial Optimization Problem (COPs) is one of the branches of applied mathematics and computer sciences, which is accompanied by many problems such as Facility Layout Problem (FLP), Vehicle Routing Problem (VRP), etc. Even though the use of several mathematical formulations is employed for FLP, Quadratic Assignment Problem (QAP) is one of the most commonly used. One of the major problems of Combinatorial NP-hard Optimization Problem is QAP mathematical model. Consequently, many approaches have been introduced to solve this problem, and these approaches are classified as Approximate and Exact methods. With QAP, each facility is allocated to just one location, thereby reducing cost in terms of aggregate distances weighted by flow values. The primary aim of this study is to propose a hybrid approach which combines Discrete Differential Evolution (DDE) algorithm and Tabu Search (TS) algorithm to enhance solutions of QAP model, to reduce the distances between the locations by finding the best distribution of N facilities to N locations, and to implement hybrid approach based on discrete differential evolution (HDDETS) on many instances of QAP from the benchmark. The performance of the proposed approach has been tested on several sets of instances from the data set of QAP and the results obtained have shown the effective performance of the proposed algorithm in improving several solutions of QAP in reasonable time. Afterwards, the proposed approach is compared with other recent methods in the literature review. Based on the computation results, the proposed hybrid approach outperforms the other methods.

scite is a Brooklyn-based organization that helps researchers better discover and understand research articles through Smart Citations–citations that display the context of the citation and describe whether the article provides supporting or contrasting evidence. scite is used by students and researchers from around the world and is funded in part by the National Science Foundation and the National Institute on Drug Abuse of the National Institutes of Health.

Contact Info

[email protected]

10624 S. Eastern Ave., Ste. A-614

Henderson, NV 89052, USA

Blog Terms and Conditions API Terms Privacy Policy Contact Cookie Preferences Do Not Sell or Share My Personal Information

Copyright © 2024 scite LLC. All rights reserved.

Made with 💙 for researchers

Part of the Research Solutions Family.

• Sociocultural Anthropology
• Cultural Evolution
• Anthropology
• Cultural Anthropology

Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search

• November 2020
• European Journal of Operational Research 292(3):1066-1084
• 292(3):1066-1084

• Université Laval

Discover the world's research

• 25+ million members
• 160+ million publication pages
• 2.3+ billion citations

No full-text available

To read the full-text of this research, you can request a copy directly from the authors.

• BUILD ENVIRON

• COMPUT ELECTR ENG

• Hadi Shahriar Shahhoseini
• Frederick L. Jatzkowski
• Antonia Schmidt
• Robert Mank

• Sébastien Verel
• Sarah L. Thomson

• ENG APPL ARTIF INTEL

• Mohammed Aljuaid
• Karuna Panwar

• Dominic Schuhmacher
• Leoni Carla Wirth

• Quang Anh Pham
• Hoong Chuin Lau
• Minh Hoàng Hà

• Abolfazl Ghanbari

• Yameng Wang
• Xiumei Wang

• Mahdis Bayani

• Yossiri Adulyasak

• Said Mohsine
• Mohammed Essaid Riffi
• Daniel Soto
• Wilson Soto
• COMPUT IND ENG

• Seungmo Kim
• Yeonho Jeong
• Jae-Won Nam
• NEURAL COMPUT APPL

• APPL SOFT COMPUT
• Oylum Şeker

• EUR J OPER RES

• Gunasekaran Manogaran
• Heba Rashad

• Abhilash Chaparala
• EXPERT SYST APPL

• Michele Monaci

• Maciej Drwal

• APPL MATH COMPUT

• Mohamed Abdel-Baset
• M. Gunsekaran

• Krešimir Mihić
• R.E. Burkard
• Yagmur Aksan

• Gerhard J. Woeginger
• Matthew Harris

• M.A. Pollatschek
• N. Gershoni
• Y.T. Radday

• Bronislovas Kilda

• Warren P. Adams
• Nav Res Logist Q
• Harold Greenberg
• Yusuf Ziya Ünal

• J PARALLEL DISTR COM
• Michał Czapiński

• Alwalid N. Elshafei

• James Curry

• J OPER RES SOC
• H. A. Eiselt
• Gilbert Laporte
• Wolfgang Domschke
• Peter Forst

• Eugene Woolsey
• Leon Steinberg
• Transport Res
• J. W. Dickey
• J. W. Hopkins
• OPER RES LETT

• Alain Sutter

• James V. Crouse

• Michael C. Fu
• Bharat K. Kaku
• Eugene L. Lawler
• Recruit researchers
• Join for free
• Login Email Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google Welcome back! Please log in. Email · Hint Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google No account? Sign up

A comprehensive review of quadratic assignment problem: variants, hybrids and applications

Research output : Contribution to journal › Article › peer-review

The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields. QAP is NP-hard problem that is impossible to be solved in polynomial time when the problem size increases, hence heuristic and metaheuristic approaches are utilized for solving the problem instead of exact approaches, because these approaches achieve quality in the solution in short computation time. The objectives of this paper are to describe QAP in details showing its types, nature of the problem, complexity of the problem, importance, and simple example. QAP formulations, problems related with QAP, solution techniques, QAP benchmark instances, applications of QAP, survey of QAP researches are also illustrated.

Access to Document

• 10.1007/s12652-018-0917-x

Other files and links

• Link to publication in Scopus

Fingerprint

• Combinatorial optimization Engineering & Materials Science 100%
• NP-hard Engineering & Materials Science 88%
• Polynomials Engineering & Materials Science 70%
• Scheduling Engineering & Materials Science 62%
• Communication Engineering & Materials Science 45%

T1 - A comprehensive review of quadratic assignment problem

T2 - variants, hybrids and applications

AU - Abdel-Basset, Mohamed

AU - Manogaran, Gunasekaran

AU - Rashad, Heba

AU - Zaied, Abdel Nasser H.

N1 - Publisher Copyright: © 2018 Springer-Verlag GmbH Germany, part of Springer Nature

PY - 2018/6/20

Y1 - 2018/6/20

N2 - The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields. QAP is NP-hard problem that is impossible to be solved in polynomial time when the problem size increases, hence heuristic and metaheuristic approaches are utilized for solving the problem instead of exact approaches, because these approaches achieve quality in the solution in short computation time. The objectives of this paper are to describe QAP in details showing its types, nature of the problem, complexity of the problem, importance, and simple example. QAP formulations, problems related with QAP, solution techniques, QAP benchmark instances, applications of QAP, survey of QAP researches are also illustrated.

AB - The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields. QAP is NP-hard problem that is impossible to be solved in polynomial time when the problem size increases, hence heuristic and metaheuristic approaches are utilized for solving the problem instead of exact approaches, because these approaches achieve quality in the solution in short computation time. The objectives of this paper are to describe QAP in details showing its types, nature of the problem, complexity of the problem, importance, and simple example. QAP formulations, problems related with QAP, solution techniques, QAP benchmark instances, applications of QAP, survey of QAP researches are also illustrated.

KW - Complexity

KW - Exact approaches

KW - Formulations

KW - Heuristics approaches

KW - Metaheuristic approaches

KW - NP-hard

KW - Quadratic assignment problem

UR - http://www.scopus.com/inward/record.url?scp=85049559984&partnerID=8YFLogxK

U2 - 10.1007/s12652-018-0917-x

DO - 10.1007/s12652-018-0917-x

M3 - Article

AN - SCOPUS:85049559984

SN - 1868-5137

JO - Journal of Ambient Intelligence and Humanized Computing

JF - Journal of Ambient Intelligence and Humanized Computing

• Advanced Search

Selection hyper-heuristics for the multi and many-objective quadratic assignment problem

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options, graphical abstract.

• Irawan C Salhi S Jones D Dai J Liu M (2024) A dry port hub-and-spoke network design Computers and Operations Research 10.1016/j.cor.2024.106646 167 :C Online publication date: 1-Jul-2024 https://dl.acm.org/doi/10.1016/j.cor.2024.106646
• Torres F Júnior V Costa D Cardoso D Oliveira R (2023) Radio resource allocation in a 6G D-OMA network with imperfect SIC Engineering Applications of Artificial Intelligence 10.1016/j.engappai.2023.105830 119 :C Online publication date: 1-Mar-2023 https://dl.acm.org/doi/10.1016/j.engappai.2023.105830
• Bouaziz H Bardou D Berghida M Chouali S Lemouari A (2023) A novel hybrid multi-objective algorithm to solve the generalized cubic cell formation problem Computers and Operations Research 10.1016/j.cor.2022.106069 150 :C Online publication date: 1-Feb-2023 https://dl.acm.org/doi/10.1016/j.cor.2022.106069
• Show More Cited By

Index Terms

Computing methodologies

Artificial intelligence

Search methodologies

Heuristic function construction

Mathematics of computing

Mathematical analysis

Mathematical optimization

Theory of computation

Design and analysis of algorithms

Recommendations

Hyper-heuristic based nsga-iii for the many-objective quadratic assignment problem.

The Quadratic Assignment Problem (QAP) can be subdivided into different versions, being present in several real-world applications. In this work, it is used a version that considers many objectives. QAP is an NP-hard problem, so approximate ...

Evolutionary many-objective optimization based on linear assignment problem transformations

The selection mechanisms that are most commonly adopted by multi-objective evolutionary algorithms (MOEAs) are based on Pareto optimality. However, recent studies have provided theoretical and experimental evidence regarding the unsuitability of Pareto-...

Transgenetic Algorithms for the Multi-objective Quadratic Assignment Problem

The multi-objective Quadratic Assignment Problem (mQAP) is a hard optimization problem with many real-world applications, such as in hospital layouts. The main purposes of this paper are: (1) the investigation of hybrid algorithms combining Transgenetic ...

Information

Published in.

Elsevier Science Ltd.

United Kingdom

Publication History

Author tags.

• Multi-objective optimization
• Many-objective optimization hyper-heuristics
• Research-article

Contributors

Other metrics, bibliometrics, article metrics.

• 4 Total Citations View Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0
• Wang H Alidaee B (2023) A new hybrid-heuristic for large-scale combinatorial optimization Computers and Industrial Engineering 10.1016/j.cie.2023.109220 179 :C Online publication date: 1-May-2023 https://dl.acm.org/doi/10.1016/j.cie.2023.109220

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.

A Hybrid Optimization GNA Algorithm for the Quadratic Assignment Problem Solving

• Conference paper
• First Online: 06 February 2019
• Cite this conference paper

• Kefaya Qaddoum 6 &
• Azmi Al Azzam 6  

Part of the book series: Lecture Notes on Data Engineering and Communications Technologies ((LNDECT,volume 29))

Included in the following conference series:

• International Conference on Emerging Internetworking, Data & Web Technologies

730 Accesses

1 Citations

The quadratic assignment problem (QAP) was considered one of the most significant combinatorial optimization problems due to its variant and substantial applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields. QAP is an NP-hard problem that is impossible to be solved in polynomial time when the problem size increases, hence heuristic and metaheuristic approaches are utilized for solving the problem instead of exact methods. Optimization plays a significant role in easing this problem. In this paper, we will provide a solution to optimize QAP. In the QAP problem, there is a total of facilities (departments, company’s,…etc.) that must be located to minimize the flow (amount of material to be exchanged). Thus, the objective function is composed by multiplying both distances between the locations and the flow among these facilities. Global Neighborhood (GNA) Algorithm will be used to optimize the QAP problem, and the solution will also be compared to the well-known Genetic Algorithm (GA).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Metaheuristics with Local Search Miscellany Applied to the Quadratic Assignment Problem for Large-Scale Instances

A Comparative Analysis of Genetic Algorithms and QAP Formulation for Facility Layout Problem: An Application in a Real Context

A comprehensive review of quadratic assignment problem: variants, hybrids and applications.

Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1 , 67–82 (1997)

Article   Google Scholar  

Glover, F.: The future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13 (5), 533–549 (1986)

Article   MathSciNet   Google Scholar  

Reeves, C.R.: Modern Heuristic Techniques for Combinatorial Optimization Problems. Blackwell Scientific, Oxford (1993)

Google Scholar  

Lee, K.S., Geem, Z.W.: A new structural optimization method based on the harmony search algorithm. Comput. Struct. 82 , 781–798 (2004)

Lee, K.S., Geem, Z.W.: A new meta-heuristic algorithm for continuous engineering optimization. Comput. Methods Appl. Mech. Eng. 194 (2005), 3902–3933 (2005)

Omran, M.G., Mahdavi, M.: Global-best harmony search. Appl. Math. Comput. 198 , 643–656 (2008)

MathSciNet   MATH   Google Scholar  

Rechenberg, I.: Cybernetic solution path of an experimental problem, Royal Aircraft Establishment, Library Translation no. 1122 (1965)

Fogel, L.J., Owens, A.J., Walsh, M.J.: Artificial Intelligence Through Simulated Evolution. Wiley, Chichester (1996)

MATH   Google Scholar  

De Jong, K.: Analysis of the behavior of a class adaptive systems, Ph.D. Thesis. University of Michigan, Ann Arbor, MI (1975)

Koza, J.R.: Genetic programming: a paradigm for genetically breeding populations of computer programs to solve problems, Report No. STAN-CS-90- 1314. Stanford University, Stanford, CA (1990)

Goldberg, D.E.: Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley, Boston (1989)

Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)

Glover, F.: Heuristic for integer programming using surrogate constraints. Decis. Sci. 8 (1), 156–166 (1977)

Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybernet. 26 (1), 29–41 (1996)

Kennedy, J., Eberhart, R.: Particle swarm optimization. In: IEEE International Conference on Neural Networks Perth, Australia, pp. 1942–1948 (1995)

Geem, Z.W., Kim, J.H., Loganathan, G.: A new heuristic optimization algorithm: harmony search. Simulation 76 (2), 60 (2001)

Nakrani, S., Tovey, C.: On honey bees and dynamic server allocation in internet hosting centers. Adapt. Behav. 12 (3–4), 223 (2004)

Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by simulated annealing. Science 220 (4598), 671–680 (1983)

Rashedi, E., Nezamabadi, H., Saryazdi, S.: GSA: a gravitational search algorithm. Inform. Sci. 179 (13), 2232–2248 (2009)

Engelbrecht, A.P.: Fundamentals of Computational Swarm Intelligence. Wiley, Hoboken (2006)

Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1 (1), 53–66 (1997)

Eberhart, R., Kennedy, J.: A new optimizer using particle swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science MHS 1995, pp. 39–43. IEEE (1995)

Alazzam, A., Lewis III, H.: A new optimization algorithm for combinatorial problems. (IJARAI) Int. J. Adv. Res. Artif. Intell. 2 (5) (2013)

Nugent, C.E., Vollman, T.E., Ruml, J.: An experimental comparison of techniques for the assignment of facilities to locations. Operations (1968)

Download references

Author information

Authors and affiliations.

Higher Colleges of Technology, Abu Dhabi, UAE

Kefaya Qaddoum & Azmi Al Azzam

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Kefaya Qaddoum .

Editor information

Editors and affiliations.

Department of Information and Communication Engineering, Faculty of Information Engineering, Fukuoka Institute of Technology, Fukuoka, Japan

Leonard Barolli

Technical University of Catalonia, Barcelona, Spain

Fatos Xhafa

Computer Information Science (CIS), Higher Colleges of Technology, Fujairah Campus, Fujairah, United Arab Emirates

Zahoor Ali Khan

Faculty of Computer Information Science, Higher Colleges of Technology, Dubai Campus, Dubai, United Arab Emirates

Hamad Odhabi

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Cite this paper.

Qaddoum, K., Azzam, A.A. (2019). A Hybrid Optimization GNA Algorithm for the Quadratic Assignment Problem Solving. In: Barolli, L., Xhafa, F., Khan, Z., Odhabi, H. (eds) Advances in Internet, Data and Web Technologies. EIDWT 2019. Lecture Notes on Data Engineering and Communications Technologies, vol 29. Springer, Cham. https://doi.org/10.1007/978-3-030-12839-5_42

Download citation

DOI : https://doi.org/10.1007/978-3-030-12839-5_42

Published : 06 February 2019

Publisher Name : Springer, Cham

Print ISBN : 978-3-030-12838-8

Online ISBN : 978-3-030-12839-5

eBook Packages : Intelligent Technologies and Robotics Intelligent Technologies and Robotics (R0)

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

• DOI: 10.5120/17693-8662
• Corpus ID: 61123582

A Survey of Quadratic Assignment Problems

• A. H. Zaied , Laila A. Shawky
• Published 18 September 2014
• Computer Science, Mathematics
• International Journal of Computer Applications

13 Citations

Solving the quadratic assignment problem with cooperative parallel extremal optimization, hybridization as cooperative parallelism for the quadratic assignment problem, solving quadratic assignment problem with fixed assignment (qapfa) using branch and bound approach, a comprehensive review of quadratic assignment problem: variants, hybrids and applications, quantum and digital annealing for the quadratic assignment problem, a variable neighbourhood search enhanced estimation of distribution algorithm for quadratic assignment problems, a new method for improving the performance of fast local search in solving qap for optimal exploration of state space, comparing qubo models for quantum annealing: integer encodings for permutation problems, a cooperative gpu-based parallel multistart simulated annealing algorithm for quadratic assignment problem, learning optimal parameters for multi-target tracking, 19 references, the quadratic assignment problem: a survey and recent developments, the quadratic assignment problem, a new lower bound for the quadratic assignment problem, applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, breakout local search for the quadratic assignment problem, hospital layout as a quadratic assignment problem, a branch-and-bound algorithm for the quadratic assignment problem based on the hungarian method, on the use of exact and heuristic cutting plane methods for the quadratic assignment problem, optimal and suboptimal algorithms for the quadratic assignment problem, a survey of meta-heuristic solution methods for the quadratic assignment problem, related papers.

Showing 1 through 3 of 0 Related Papers