An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem
Operations Research (OR) analytics play a crucial role in optimizing decision-making processes for real-world problems. The assignment problem, with applications in supply chains, healthcare logistics, and production scheduling, represents a prominent optimization challenge. This paper focuses on ad...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier Ltd
2023
|
| Subjects: |
| _version_ | 1811132414840274944 |
|---|---|
| author | Fathollahi-Fard, Amir M. Wong, Kuan Yew Mohammed Aljuaid, Mohammed Aljuaid |
| author_facet | Fathollahi-Fard, Amir M. Wong, Kuan Yew Mohammed Aljuaid, Mohammed Aljuaid |
| author_sort | Fathollahi-Fard, Amir M. |
| collection | ePrints |
| description | Operations Research (OR) analytics play a crucial role in optimizing decision-making processes for real-world problems. The assignment problem, with applications in supply chains, healthcare logistics, and production scheduling, represents a prominent optimization challenge. This paper focuses on addressing the Generalized Quadratic Assignment Problem (GQAP), a well-known NP-hard combinatorial optimization problem. To tackle the GQAP, we propose an OR analytical approach that incorporates efficient relaxations, reformulations, heuristics, and a metaheuristic algorithm. Initially, we employ the Reformulation Linearization Technique (RLT) to generate various linear relaxation models, carefully selecting the most efficient ones. Building upon this foundation, we introduce a robust reformulation based on Benders Decomposition (BD), which serves as the basis for an iterative optimization algorithm applied to the GQAP. Furthermore, we develop a constructive heuristic algorithm to identify near-optimal solutions, followed by an enhancement utilizing an Adaptive Large Neighborhood Search (ALNS) metaheuristic algorithm. This ALNS algorithm is enhanced through the integration of a tabu list derived from Tabu Search (TS) and a decision rule inspired by Simulated Annealing (SA). To validate our approach and evaluate its performance, we conduct a comparative analysis against state-of-the-art algorithms documented in the literature. This comparison confirms the significant improvements achieved in terms of solution quality and computational efficiency through our proposed methodology. These advancements contribute to the state of the art in solving the GQAP and hold the potential to enhance decision-making processes in a wide range of domains. Our methodology demonstrates remarkable improvements in solution quality and computational efficiency when compared to existing approaches, as evidenced by the comparative results with state-of-the-art algorithms. The potential implications of our research extend to optimizing decision-making processes in diverse fields, rendering it highly relevant and impactful. |
| first_indexed | 2024-09-24T00:03:41Z |
| format | Article |
| id | utm.eprints-106801 |
| institution | Universiti Teknologi Malaysia - ePrints |
| last_indexed | 2024-09-24T00:03:41Z |
| publishDate | 2023 |
| publisher | Elsevier Ltd |
| record_format | dspace |
| spelling | utm.eprints-1068012024-07-30T08:04:42Z http://eprints.utm.my/106801/ An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem Fathollahi-Fard, Amir M. Wong, Kuan Yew Mohammed Aljuaid, Mohammed Aljuaid TJ Mechanical engineering and machinery Operations Research (OR) analytics play a crucial role in optimizing decision-making processes for real-world problems. The assignment problem, with applications in supply chains, healthcare logistics, and production scheduling, represents a prominent optimization challenge. This paper focuses on addressing the Generalized Quadratic Assignment Problem (GQAP), a well-known NP-hard combinatorial optimization problem. To tackle the GQAP, we propose an OR analytical approach that incorporates efficient relaxations, reformulations, heuristics, and a metaheuristic algorithm. Initially, we employ the Reformulation Linearization Technique (RLT) to generate various linear relaxation models, carefully selecting the most efficient ones. Building upon this foundation, we introduce a robust reformulation based on Benders Decomposition (BD), which serves as the basis for an iterative optimization algorithm applied to the GQAP. Furthermore, we develop a constructive heuristic algorithm to identify near-optimal solutions, followed by an enhancement utilizing an Adaptive Large Neighborhood Search (ALNS) metaheuristic algorithm. This ALNS algorithm is enhanced through the integration of a tabu list derived from Tabu Search (TS) and a decision rule inspired by Simulated Annealing (SA). To validate our approach and evaluate its performance, we conduct a comparative analysis against state-of-the-art algorithms documented in the literature. This comparison confirms the significant improvements achieved in terms of solution quality and computational efficiency through our proposed methodology. These advancements contribute to the state of the art in solving the GQAP and hold the potential to enhance decision-making processes in a wide range of domains. Our methodology demonstrates remarkable improvements in solution quality and computational efficiency when compared to existing approaches, as evidenced by the comparative results with state-of-the-art algorithms. The potential implications of our research extend to optimizing decision-making processes in diverse fields, rendering it highly relevant and impactful. Elsevier Ltd 2023 Article PeerReviewed Fathollahi-Fard, Amir M. and Wong, Kuan Yew and Mohammed Aljuaid, Mohammed Aljuaid (2023) An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem. Engineering Applications of Artificial Intelligence, 126 (NA). NA-NA. ISSN 0952-1976 http://dx.doi.org/10.1016/j.engappai.2023.106802 DOI : 10.1016/j.engappai.2023.106802 |
| spellingShingle | TJ Mechanical engineering and machinery Fathollahi-Fard, Amir M. Wong, Kuan Yew Mohammed Aljuaid, Mohammed Aljuaid An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem |
| title | An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem |
| title_full | An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem |
| title_fullStr | An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem |
| title_full_unstemmed | An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem |
| title_short | An efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem |
| title_sort | efficient adaptive large neighborhood search algorithm based on heuristics and reformulations for the generalized quadratic assignment problem |
| topic | TJ Mechanical engineering and machinery |
| work_keys_str_mv | AT fathollahifardamirm anefficientadaptivelargeneighborhoodsearchalgorithmbasedonheuristicsandreformulationsforthegeneralizedquadraticassignmentproblem AT wongkuanyew anefficientadaptivelargeneighborhoodsearchalgorithmbasedonheuristicsandreformulationsforthegeneralizedquadraticassignmentproblem AT mohammedaljuaidmohammedaljuaid anefficientadaptivelargeneighborhoodsearchalgorithmbasedonheuristicsandreformulationsforthegeneralizedquadraticassignmentproblem AT fathollahifardamirm efficientadaptivelargeneighborhoodsearchalgorithmbasedonheuristicsandreformulationsforthegeneralizedquadraticassignmentproblem AT wongkuanyew efficientadaptivelargeneighborhoodsearchalgorithmbasedonheuristicsandreformulationsforthegeneralizedquadraticassignmentproblem AT mohammedaljuaidmohammedaljuaid efficientadaptivelargeneighborhoodsearchalgorithmbasedonheuristicsandreformulationsforthegeneralizedquadraticassignmentproblem |