# A Hybrid Method Integrating a Discrete Differential Evolution Algorithm with Tabu Search Algorithm for the Quadratic Assignment Problem: A New Approach for Locating Hospital Departments

Authors: Asaad Shakir Hameed; Modhi Lafta Mutar; Haiffa Muhsan B. Alrikabi; Zakir Hussain Ahmed; Abeer A. Abdul–Razaq; Huda Karem Nasser
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The facility layout problem (FLP) is a very important class of NP-hard problems in operations research that deals with the optimal assignment of facilities to minimize transportation costs. The quadratic assignment problem (QAP) can model the FLP effectively. One of the FLPs is the hospital facility layout problem that aims to place comprehensive clinics, laboratories, and radiology units within predefined boundaries in a way that minimizes the cost of movement of patients and healthcare personnel. We are going to develop a hybrid method based on discrete differential evolution (DDE) algorithm for solving the QAP. In the existing DDE algorithms, certain issues such as premature convergence, stagnation, and exploitation mechanism have not been properly addressed. In this study, we first aim to discover the issues that make the current problem worse and to identify the best solution to the problem, and then we propose to develop a hybrid algorithm (HDDETS) by combining the DDE and tabu search (TS) algorithms to enhance the exploitation mechanism in the DDE algorithm. Then, the performance of the proposed HDDETS algorithm is evaluated by implementing on the benchmark instances from the QAPLIB website and by comparing with DDE and TS algorithms on the benchmark instances. It is found that the HDDETS algorithm has better performance than both the DDE and TS algorithms where the HDDETS has obtained 42 optimal and best-known solutions from 56 instances, while the DDE and TS algorithms have obtained 15 and 18 optimal and best-known solutions out of 56 instances, respectively. Finally, we propose to apply the proposed algorithm to find the optimal distributions of the advisory clinics inside the Azadi Hospital in Iraq that minimizes the total travel distance for patients when they move among these clinics. Our application shows that the proposed algorithm could find the best distribution of the hospital’s rooms, which are modeled as a QAP, with reduced total distance traveled by the patients.


---

## Body

## 1. Introduction

The demand for public facilities has been on increase due to the ever-growing population. These facilities include hospitals, schools, universities, train stations, and airports. As such, it has become pertinent to urgently find the best way to design and manage these facilities, as a lack of design leads to financial losses alongside unnecessary waste of time. The facility layout problem (FLP) is an important class of operations research problems that have been studied for several decades [1]. Most facility layout variants are NP-hard; therefore, global optimal solutions are difficult or impossible to compute in a reasonable time [2]. The FLPs include ensuring that the departments are not given similar assignments and that customization and material handling costs are reduced to a minimum. Over the years, few studies have focused on hospital layout problems, except for those involving different facilities.One of the NP-hard problems is the hospital facility layout problem, which aims to place comprehensive clinics, laboratories, and radiology units within predefined boundaries in a way that minimizes the cost of movement of patients and healthcare personnel [3]. Several models have been proposed to design and facilitate the best layout for the distribution of the facilities. Recent studies proved that the use of the quadratic assignment problem (QAP) to model the FLP leads to identifying the best facilities for the sites in order to minimize the cost. The QAP has been successfully applied in fields such as economics, engineering, and computing because it uses the best distribution of several facilities to same number of locations to minimize computational cost.The QAP, which is a combinatorial optimization problem (COP), was first introduced in [4] as a mathematical model related to economic activities which can be defined as follows: there are n facilities and n locations. Let fij be an information flow between facilities i and j (for example, the number of materials transported between the facility pairs) and dkl be the distance between locations k and l. Also, let π=π1,π2,…,πn be an assignment (or permutation or one-to-one mapping between all facilities to locations), where π(i) represents the location of the facility i. The aim of the problem is to fix the facilities to different locations such that the sum of the distances multiplied by the corresponding flows is minimized. That is, it aims to minimize the total assignment cost (Zπ), where(1)Zπ=∑i=1n∑j=1nfijdπiπj.In this problem,n facilities and n locations define the problem size; the distance matrix (D) consists of the distances between every location pairs; the flow matrix (F) is the amount of traffic between every facility pairs; and a solution (π) is an assignment of facilities to locations and an objective function defined by total cost of a solution (Zπ). Based on the above, we can summarize the QAP model steps in Figure 1.Figure 1
QAP model steps.Different viewpoints have attracted researchers’ attention to study the QAP. From the theoretical viewpoint, the QAP is an NP-hard problem that cannot be solved in polynomial time when the problem size increases [5, 6]. From the practical viewpoint, many real-life applications can be modeled by the QAP, such as backboard wiring problem in the design of computer and other electronic equipment, hospital, and campus layouts [7]. From the application domain viewpoint, the cost of building hospitals and universities is very high, so renovating them is a better option because it is cheaper [8]. In addition, poorly designed layouts lead to financial losses and unnecessary waste of time [9]. From the technique viewpoint, open and active research is recommended for the enhancement of the QAP optimization techniques [10, 11].Two classes of approaches have been presented to solve the QAP: the exact approaches and the heuristic approaches. The approaches that deliver the exact solution to the problem are called exact approaches. Many exact approaches have been suggested in many studies, but they cannot find the optimal solution for large sized problem instances within a reasonable computational time [12, 13]. Therefore, an effective heuristic approach that can find the best solutions of the QAP within an acceptable computational time for large sized problem instances is needed. Unlike the exact approaches, heuristic approaches seek good solutions (i.e., near-optimal solutions) within a reasonable computational time without giving guarantee to the optimality of the solutions. Metaheuristics are the most recent heuristic approaches which are applied to various combinatorial optimization problems (COPs) as well as the QAP [14, 15].Some well-known metaheuristic approaches applied to the QAP are discrete bat algorithm (DBA) [16], genetic algorithm (GA) [17], simulated annealing (SA) [18], tabu search [19], ant colony optimization [20], memetic algorithm (MA) [21], migrating birds optimization (MBO) algorithm [22], differential evolution [23], etc. Out of the metaheuristic approaches, differential evolution (DE) algorithms have been proven to be very efficient in finding solutions that are optimal or nearly optimal within a reasonable computational time for large sized problem instances. However, they are characterized by the slow exploitation of solutions [24]. To solve COPs, a few studies, such as [23, 25], have suggested discrete differential evolution (DDE) algorithms.In this study, we first aim to discover the issues that make the current problem worse and to identify the best solution to the problem, and then we propose to develop a hybrid algorithm (HDDETS) by combining the DDE and tabu search (TS) algorithms to enhance the exploitation mechanism in the DDE algorithm. Then, the performance of the proposed HDDETS algorithm is evaluated by implementing on the benchmark instances from QAPLIB website and by comparing with DDE and TS algorithms on the benchmark instances. Our experimental investigation shows that the proposed HDDETS algorithm is the best algorithm that could find very good quality solutions to the benchmark instances. Finally, we propose to apply the proposed algorithm to find the optimal distributions of the advisory clinics inside the Azadi Hospital in Iraq that minimizes the total travel distance for patients when they move among these clinics. Our application shows that the proposed algorithm could find the best distribution of the hospital’s rooms, which are modeled as a QAP, with reduced total distance traveled by the patients when they move among these clinics.The rest of the paper is organized as follows:Section 2 introduces the research problems; Section 3 includes related works; Section 4 lays out the research methodology; computational results are introduced in Section 5; Section 6 discusses theoretical analysis and limitation of the proposed algorithm; and Section 7 presents the conclusions.


## 2. Research Problems

Recently, metaheuristic algorithms have been proven successful in several fields such as technology, engineering, and science. However, most of the existing research could not achieve all the aims and objectives due to certain gaps that needed to be filled, especially for large-scale complex optimization problems. Another open area of research in these algorithms is the balance between exploration and exploitation mechanisms, premature convergence and stagnation issues, etc. [11].The evolutionary algorithms (EAs) are one of the most important types of metaheuristics algorithms, which are very useful in solving complex optimization problems [26, 27]. It has a global exploration search, but sufferings from slow exploitation search [28]. Premature convergence and stagnation issues that occur in the iterative operation are current problems faced by all EAs [29]. In the same context, the DE algorithm is a robust EA. It has a good convergence feature, which makes it necessary to solve global optimization problems, in addition to its high efficiency that has proven to be successful in various real-world applications [29, 30]. The DE algorithm was used in [23, 25] to solve problems related to discrete values such as the QAP. DDE is a modified version of the DE algorithm. Finding solutions of the QAP is very difficult within a polynomial time as the size of the problem increases. Besides, there is no guarantee that a near-optimal solution would be found within polynomial time. This can be regarded as the problem associated with allocating a set of facilities to a set of locations and considering the distance between any two locations as well as the flows between any two facilities to minimize the cost [16].The QAP is as an NP-hard problem [5]. An NP-hard problem is very complex, and it requires a method that can be used to simplify it. Regarding the applications of the QAP in the real world, the increasing interest of governments in the service sectors (such as hospitals) and educational institutions (such as universities) has led to an increase in the number of these buildings. These buildings are considered suitable for the application of the QAP model, which in turn has led to an increase in the number of these buildings. In the same context, the cost of building hospitals and universities is quite high, so renovating them is often a better option as it is less expensive [8].In conclusion, there are two main problems worth to be highlighted in this proposed study.(i)
In the view of the fundamental technique, the EAs have a global exploration advantage; however, these kinds of algorithms have various well-known limitations. Suffering from the mechanism of exploitation is among these limitations [30]. Based on a critical reading of the literature, we found that this issue has not been studied in the DDE algorithm. As such, for a DDE algorithm to achieve good performance in terms of solving complex optimization problems, the QAP is considered. The use of local research can enhance the exploitation mechanism by increasing the speed of convergence to optimal solutions [29, 31]. Therefore, there is a need to integrate the DDE algorithm with another algorithm that uses the local search feature.(ii)
In the view of application domain of the QAP, the lack of layout of the clinics’ locations inside the hospital causes considerable distance for patients [32]. Therefore, it is important for clinics within a hospital to be meticulously organized because disorganization can result in too much movement for patients, thereby leading to waste of time.


## 3. Related Works

We have mentioned that there are two classes of approaches presented to solve the QAP. Since we are going to use metaheuristic, we are presenting a brief review of the metaheuristic approaches for the QAP. We carried out studies to identify better algorithms to find optimal solutions for the QAP. Some of these studies suggest that some algorithms may be improved using parallel approaches [33–36], while other studies suggest some algorithms based on the hybrid approaches [37–39], which have proven its superiority over other types of algorithms because it has addressed the issues found in other algorithms by using their advantages.The study [40] has been presented a hybrid algorithm between the memetic algorithm (MA) and tabu search (TS) algorithm that was used to improve the local improvement strategy. The MA uses the concept of regular “restarts” of a population. A restart mechanism is employed in times when population diversity is low; in this case, the TS algorithm is applied. The results have shown the performance of the proposed algorithm competitively with some of the state-of-the-art algorithms for the QAP from the literature. The usage of TS algorithm has increased the accuracy of the solutions obtained for QAP problems.Another study [41] proposed hybrid algorithm between biogeography-based optimization (BBO) algorithm and tabu search (TS) algorithm to overcome the weakness of the classical BBO algorithm in the mutation stage by replacing a mutation operator with a tabu search procedure. The ability to find the best solutions for 36 instances out of a total of 37 instances from QAP data was demonstrated by the hybrid proposed.Recently, in the study [8] an algorithm is proposed by integrating the whale algorithm (WA) with the tabu search (TS) algorithm to solve the QAP. Since the WA suffers from a slow exploitation mechanism, so this integration is proposed to deal with this issue. According to the results, the proposed algorithm has obtained near-optimal results in an acceptable time, is well-suited for QAP, and outperforms the current algorithms in the literature when solving QAP. Furthermore, this study also aimed to collect hospital departments that have been modeled as a QAP model to reduce the average distance traveled by patients when moving between these departments. The results show that the performance of WAITS is better than the other algorithms that have a comparison with it, the reason is due to the improved local search using TS.In the paper written by [42], discrete particle swarm optimization (DPSO) algorithm was modified to enable it to solve the QAP. The PSO is an efficient tool for solving combinatorial optimization problems. In the proposed algorithm, the authors made efforts to solve five sets of QAPs, and the results show slight deviations from the best-known solutions.On the other hand, many studies recommend a comprehensive survey of metaheuristic algorithms; though these algorithms have been used successfully in various fields, some lacunae still exist in some of these algorithms, and further research is needed to resolve this [9]. For this purpose, this study aims to address some issues that are the DDE algorithm suffers from it which modified to solve QAP by the studies [23, 25]. The following two subsections have presented the critical analysis of relevant literature studies to identify the main weaknesses of these studies and the research's conceptual framework to identify the direction of this work.


### 3.1. Critical Analysis of Relevant Literature Studies [23, 25]

The main aim of constructive criticism is to analyze previous studies. This activity involves analyzing the strengths and weaknesses of a given study using a wide range of available frameworks and methods. Such frameworks and methods have been proposed to identify research materials (including theses and articles), the subject of the research, and the purpose of the study. The literature reviewed in this study has been constructively criticized. Table1 shows the critical analysis of relevant literature studies.Table 1
Critical analysis of relevant literature studies.
ReferenceAlgorithmCritical analysis[23]Discrete differential evolution algorithm(1) This study focused on solving discrete optimization problems using a modified differential evolution algorithm.(2) In this study, a restart strategy was recommended by the authors as a technique for generating solutions, rather than using crossover operators which have been used in many studies reviewed in the literature. However, the authors did not compare the result produced by the strategy with that of other techniques in which crossover operators were used.(3) In the study, the authors only used the tabu list which is just a component of the tabu search algorithm, which in previous studies, have demonstrated the ability to enhance the exploitation mechanism in the evolutionary algorithms.(4) Only QAPs of small size were focused on in this study.(5) Results showed that the proposed algorithm did not perform better than the max-min ant system combined with random selection and local search.(6) As for a direction for future work, the authors suggested the integration of the proposed method with another method such as a local search algorithm so that the efficiency of the proposed method can be improved.(7) This search did not take into account the effect of parameters tuning.[25]Discrete differential evolution algorithm(1) The focus of this study was on the modification of the differential evolution algorithm which was modified to discrete DE (DEE) algorithm.(2) In this research, the mutation stage was improved through the inclusion of the proposed swap that uses a local search.(3) The method proposed in this study was applied to just a small portion of the QAP dataset.(4) The authors did not identify the kind of crossover which was used in the crossover stage although there is a wide range of crossover operators that have been recommended to be used together with algorithms for the purpose of solving QAP.(5) In this study, consideration was not given to the problems of premature convergence and stagnation.(6) Despite the numerous studies that have been carried out on the DDE algorithm, there are still inadequate exploitation mechanisms for it, although it has global exploration. This issue was not addressed in the study.(7) No method of parameter testing was used in the study.


### 3.2. Research Conceptual Framework

The metaheuristics approach has been divided into two groups: single-based metaheuristic and population-based metaheuristic algorithms. The advantage of the single-based metaheuristic is its local exploitation, whereas the population-based metaheuristic has global exploration and local exploitation. Our conceptual research framework has been presented in Figure2.Figure 2
Our research conceptual framework.On the other hand, this study has been selected by the DDE algorithm that belongs to the category of EAs from a population-based metaheuristic algorithm and the TS algorithm that belongs to the category of single-based metaheuristic algorithms and has been proved successful in integrating with other algorithm processes [39, 41]. The hybrid algorithm by combining the DDE that has global exploration and the TS algorithm that has local exploitation has been proposed to balance between the exploration mechanism and the exploitation mechanism.


## 3.1. Critical Analysis of Relevant Literature Studies [23, 25]

The main aim of constructive criticism is to analyze previous studies. This activity involves analyzing the strengths and weaknesses of a given study using a wide range of available frameworks and methods. Such frameworks and methods have been proposed to identify research materials (including theses and articles), the subject of the research, and the purpose of the study. The literature reviewed in this study has been constructively criticized. Table1 shows the critical analysis of relevant literature studies.Table 1
Critical analysis of relevant literature studies.
ReferenceAlgorithmCritical analysis[23]Discrete differential evolution algorithm(1) This study focused on solving discrete optimization problems using a modified differential evolution algorithm.(2) In this study, a restart strategy was recommended by the authors as a technique for generating solutions, rather than using crossover operators which have been used in many studies reviewed in the literature. However, the authors did not compare the result produced by the strategy with that of other techniques in which crossover operators were used.(3) In the study, the authors only used the tabu list which is just a component of the tabu search algorithm, which in previous studies, have demonstrated the ability to enhance the exploitation mechanism in the evolutionary algorithms.(4) Only QAPs of small size were focused on in this study.(5) Results showed that the proposed algorithm did not perform better than the max-min ant system combined with random selection and local search.(6) As for a direction for future work, the authors suggested the integration of the proposed method with another method such as a local search algorithm so that the efficiency of the proposed method can be improved.(7) This search did not take into account the effect of parameters tuning.[25]Discrete differential evolution algorithm(1) The focus of this study was on the modification of the differential evolution algorithm which was modified to discrete DE (DEE) algorithm.(2) In this research, the mutation stage was improved through the inclusion of the proposed swap that uses a local search.(3) The method proposed in this study was applied to just a small portion of the QAP dataset.(4) The authors did not identify the kind of crossover which was used in the crossover stage although there is a wide range of crossover operators that have been recommended to be used together with algorithms for the purpose of solving QAP.(5) In this study, consideration was not given to the problems of premature convergence and stagnation.(6) Despite the numerous studies that have been carried out on the DDE algorithm, there are still inadequate exploitation mechanisms for it, although it has global exploration. This issue was not addressed in the study.(7) No method of parameter testing was used in the study.


## 3.2. Research Conceptual Framework

The metaheuristics approach has been divided into two groups: single-based metaheuristic and population-based metaheuristic algorithms. The advantage of the single-based metaheuristic is its local exploitation, whereas the population-based metaheuristic has global exploration and local exploitation. Our conceptual research framework has been presented in Figure2.Figure 2
Our research conceptual framework.On the other hand, this study has been selected by the DDE algorithm that belongs to the category of EAs from a population-based metaheuristic algorithm and the TS algorithm that belongs to the category of single-based metaheuristic algorithms and has been proved successful in integrating with other algorithm processes [39, 41]. The hybrid algorithm by combining the DDE that has global exploration and the TS algorithm that has local exploitation has been proposed to balance between the exploration mechanism and the exploitation mechanism.


## 4. Research Methodology

The research methodology in this study has been covered by five scenarios. Figure3 shows these scenarios.Figure 3
Research methodology flow.


### 4.1. Proposed Hybrid Algorithm

This section proposes a hybrid algorithm, named HDDETS, by combining the DDE and TS algorithms. The basic steps of the HDDETS are as follows:(a)
Initialization: initialize population matrixπ=π1,π2,π3,…,πPS randomly whose size is Ps × Nd, where Ps is the size of population and Nd is the dimension of problem size. All population individuals should be unique. Initialize the set of solution and check the solutions stagnation W = array of Ps with zeros and maximum wait and ht (iteration of tabu search).(b)
Evaluate fitness: evaluate solutions to find the best solutionπbestt−1 from the population π by using equation (1).(c)
Mutation stage: the following equation shows this stage:(2)vit=insertπbt−1,ifr<Pm,swapπbt−1,otherwise.(d)
Crossover stage: the type of crossover operator that was used in this stage called uniform-like crossover (ULX) was proposed by [43]. It works as follows: beginning, the similar locations in both parents are checked and then copied to the child (new solution). The second step involves selecting an item randomly and uniformly from both parents that have not yet been selected for the child after checking the unassigned locations from left to right. Finally, the rest of the items are randomly assigned to the locations. This stage is represented by the following equation:(3)uit=CR,ifr<Pc,vit,otherwise.(e)
Apply the TS for a hybrid algorithm:(i)
Initial solution: the solution from crossover stage is the initial solution in TS.(ii)
Great tabu list: the task of the tabu list is to avoid the swap move between the ith and jth elements in the current solution π that visited in the past to generate the neighborhood.(iii)
Generation neighborhood: the neighborhood has been obtained fromπ (solution) by applying the swap to move between the ith and jth elements in the current solution π. The new solutions πn∗ are obtained by generating the neighborhoods based on the swap movement made on the current solution π. Figure 4 shows the process of generated neighborhoods.(iv)
Evaluate neighborhood: the objective function in (1) is used to evaluate neighborhood permutation (exchanging two facilities).(v)
Selection of best neighborhood: after evaluating the neighborhood permutations, the lowest value among them is the best permutation.(vi)
Best candidate solution: best solution in neighborhoods and not existing in tabu list or better than best solution.(vii)
Update tabu list: push the best candidate solution to the tabu list.(f)
Selection stage: the selection of the solutions depends on their values on the objective function. This stage is shown by the following equation:(4)πit=uit,iffuit≤fπit−1,πit−1,otherwise.(g)
Checking the solutions stagnation: sometimes, the algorithm is not able to generate a new solution, which is the stagnation issue. To handle this issue, the termW is suggested as a wait for improvement of the solution within a certain number of times. If there is any improvement, the solution is deleted and regenerated randomly. The following equation shows this stage:(5)Wi=0,πit=uit,Wi+1πit=πit−1.Figure 4
Process of generated neighborhoods [44].The pseudocode of this hybrid algorithm is presented in Algorithm1:Algorithm 1: Hybrid algorithm by combining DDE and TS algorithms.
t_max: maximum number of iterationsht_max: maximum number of tabu search iterationsw_max: maximum number of wait for improvement of the solutionNP: number of solutions S in populationInitial PopulationFort = 1 tot_maxFind the best solutionπbestt−1For each solution in the populationMutation stageCrossover stageApply the TS for a hybridInitial solutionForht = 1 to ht_maxCreate tabu listCreate neighborhoodSelect the best neighbor and is not in the tabu listUpdate tabu listEnd forSelection stageCheck solution stagnationWIf keep same the solutionw = w + 1Elsew= 0End IfIfw> w_maxRegeneratedw= 0End IfEnd ForEnd ForThe flowchart of the proposed hybrid approach HDDETS is presented in Figure5.Figure 5
Flowchart of HDDETS algorithm.


### 4.2. Parameters Tuning

The quality of the solutions obtained by using the proposed HDDETS algorithm can be influenced by the set of parameters. To identify the most suitable set of parameters that produce desirable results, the grid search technique is applied. The grid search technique is a simple optimization technique based on an exhaustive search through a manually defined set of classification technique parameter space. The advantage of grid search technique is the systematic creation of the candidate parameter settings; therefore, the same candidate parameter settings will be used to test each dataset [45]. Grid search is described as follows:(i)
Consistently generate candidate parameter settings supported by a given budget threshold. For instance, a budget threshold of 5 can limit the number of candidate settings for every parameter to 5. Thus, for an absolute classifier with three parameters and a budget threshold of five, the grid search technique generates 5 × 5 × 5 = 125 mixtures of parameter settings.(ii)
Evaluate every candidate parameter setting.(iii)
Establish the optimal parameter settings.The parameters that have been found by using grid search technique are shown in Table2.Table 2
Parameters tuning.
ParameterValueSize of population,Ps200Maximum iterations300Probability of mutation,Pm0.7Probability of crossover,Pc0.8Maximum waiting for solutions updates10Tabu list length7Maximum iterations in TS50Number of runs10


## 4.1. Proposed Hybrid Algorithm

This section proposes a hybrid algorithm, named HDDETS, by combining the DDE and TS algorithms. The basic steps of the HDDETS are as follows:(a)
Initialization: initialize population matrixπ=π1,π2,π3,…,πPS randomly whose size is Ps × Nd, where Ps is the size of population and Nd is the dimension of problem size. All population individuals should be unique. Initialize the set of solution and check the solutions stagnation W = array of Ps with zeros and maximum wait and ht (iteration of tabu search).(b)
Evaluate fitness: evaluate solutions to find the best solutionπbestt−1 from the population π by using equation (1).(c)
Mutation stage: the following equation shows this stage:(2)vit=insertπbt−1,ifr<Pm,swapπbt−1,otherwise.(d)
Crossover stage: the type of crossover operator that was used in this stage called uniform-like crossover (ULX) was proposed by [43]. It works as follows: beginning, the similar locations in both parents are checked and then copied to the child (new solution). The second step involves selecting an item randomly and uniformly from both parents that have not yet been selected for the child after checking the unassigned locations from left to right. Finally, the rest of the items are randomly assigned to the locations. This stage is represented by the following equation:(3)uit=CR,ifr<Pc,vit,otherwise.(e)
Apply the TS for a hybrid algorithm:(i)
Initial solution: the solution from crossover stage is the initial solution in TS.(ii)
Great tabu list: the task of the tabu list is to avoid the swap move between the ith and jth elements in the current solution π that visited in the past to generate the neighborhood.(iii)
Generation neighborhood: the neighborhood has been obtained fromπ (solution) by applying the swap to move between the ith and jth elements in the current solution π. The new solutions πn∗ are obtained by generating the neighborhoods based on the swap movement made on the current solution π. Figure 4 shows the process of generated neighborhoods.(iv)
Evaluate neighborhood: the objective function in (1) is used to evaluate neighborhood permutation (exchanging two facilities).(v)
Selection of best neighborhood: after evaluating the neighborhood permutations, the lowest value among them is the best permutation.(vi)
Best candidate solution: best solution in neighborhoods and not existing in tabu list or better than best solution.(vii)
Update tabu list: push the best candidate solution to the tabu list.(f)
Selection stage: the selection of the solutions depends on their values on the objective function. This stage is shown by the following equation:(4)πit=uit,iffuit≤fπit−1,πit−1,otherwise.(g)
Checking the solutions stagnation: sometimes, the algorithm is not able to generate a new solution, which is the stagnation issue. To handle this issue, the termW is suggested as a wait for improvement of the solution within a certain number of times. If there is any improvement, the solution is deleted and regenerated randomly. The following equation shows this stage:(5)Wi=0,πit=uit,Wi+1πit=πit−1.Figure 4
Process of generated neighborhoods [44].The pseudocode of this hybrid algorithm is presented in Algorithm1:Algorithm 1: Hybrid algorithm by combining DDE and TS algorithms.
t_max: maximum number of iterationsht_max: maximum number of tabu search iterationsw_max: maximum number of wait for improvement of the solutionNP: number of solutions S in populationInitial PopulationFort = 1 tot_maxFind the best solutionπbestt−1For each solution in the populationMutation stageCrossover stageApply the TS for a hybridInitial solutionForht = 1 to ht_maxCreate tabu listCreate neighborhoodSelect the best neighbor and is not in the tabu listUpdate tabu listEnd forSelection stageCheck solution stagnationWIf keep same the solutionw = w + 1Elsew= 0End IfIfw> w_maxRegeneratedw= 0End IfEnd ForEnd ForThe flowchart of the proposed hybrid approach HDDETS is presented in Figure5.Figure 5
Flowchart of HDDETS algorithm.


## 4.2. Parameters Tuning

The quality of the solutions obtained by using the proposed HDDETS algorithm can be influenced by the set of parameters. To identify the most suitable set of parameters that produce desirable results, the grid search technique is applied. The grid search technique is a simple optimization technique based on an exhaustive search through a manually defined set of classification technique parameter space. The advantage of grid search technique is the systematic creation of the candidate parameter settings; therefore, the same candidate parameter settings will be used to test each dataset [45]. Grid search is described as follows:(i)
Consistently generate candidate parameter settings supported by a given budget threshold. For instance, a budget threshold of 5 can limit the number of candidate settings for every parameter to 5. Thus, for an absolute classifier with three parameters and a budget threshold of five, the grid search technique generates 5 × 5 × 5 = 125 mixtures of parameter settings.(ii)
Evaluate every candidate parameter setting.(iii)
Establish the optimal parameter settings.The parameters that have been found by using grid search technique are shown in Table2.Table 2
Parameters tuning.
ParameterValueSize of population,Ps200Maximum iterations300Probability of mutation,Pm0.7Probability of crossover,Pc0.8Maximum waiting for solutions updates10Tabu list length7Maximum iterations in TS50Number of runs10


## 5. Results and Discussion

This section elucidates the efficiency of the proposed HDDETS algorithm. In order to encode the proposed algorithm, MATLAB was employed and run on a PC with Intel(R) Core(TM) i7-3770 CPU @ 3.40 GHz. Additionally, the PC was used which ran under MS Windows 10 with 8 GB RAM. This section comprises two parts: the first part highlights the parameters used for the proposed algorithm, whereas the second part discusses the results of the study.


### 5.1. Implementations of HDDETS Algorithm on QAP Instances

This section reports and discusses the results by the proposed HDDETS algorithm on three types of benchmark QAP instances from QAPLIB website, namely, “Esc,” “Sko,” and “Tai.” These results include some statistical metrics such as the best-known solution (BKS) reported in QAPLIB website, best solution (BS), worst solution (WS), average solution (AS), best gap (BG), worst gap (WG), average gap (AG), standard deviation (SD), and average time (AT) over 10 runs. The following equation is used to find the percentage of gap (G):(6)G=100×BS−BKSBKS.Table3 reports the results of 18 “Esc” type instances obtained by the proposed hybrid HDDETS algorithm. It is found from the table that the algorithm has ability to provide optimal solutions for all 18 instances in all 10 runs within a reasonable computational time. Table 4 reports the results of 13 “Sko” type instances by the HDDETS algorithm. These instances are considered as a challenge to all algorithms because no heuristic algorithm could find the best-known solutions (supposed to be optimal solutions) for all instances within reasonable computational time. It is found from Table 4 that the proposed algorithm could find the optimal solutions for 7 instances at least once in 10 runs. Also, the results of the remaining 6 instances are very close to optimal solutions, within a gap of less than 1% within a reasonable time.Table 3
Results by HDDETS algorithm on “Esc” type instances.
No.InstanceBKSHDDETS algorithmBSWSASBGWGAGSDAT1Esc16a6868686800000.5332Esc16b29229229229200000.6343Esc16c16016016016000000.5774Esc16d1616161600000.5325Esc16e2828282800006.4966Esc16g6868686800006.5787Esc16h2626262600000.4728Esc16i99699699699600000.4739Esc16j1414141400000.62910Esc32a888800000.73711Esc32b13013013013000007.95312Esc32c16816816816800001.92413Esc32d64264264264200002.27614Esc32e20020020020000002.18415Esc32g666600001.83516Esc32h43843843843800001.90717Esc64a11611611611600001.89618Esc128a6464646400009.927The boldface denote that the best solutions (BS) of these instances have been obtained through the lowest value obtained by the objective function of the QAP model during the process of repetition using our HDDETS algorithm. Moreover, these solutions have achieved the best-known solution (BKS) reported in the QAPLIB dataset. Thus, obtained the values of the best gaps (BG) of the solutions of these instances are 0% according to equation (6).Table 4
Results by HDDETS algorithm on “Sko” type instances.
No.InstanceBKSHDDETS algorithmBSWSASBGWGAGSDAT1Sko42158121581215812158120000146.9592Sko492338623386234022339400.0680.0320.06327.0013Sko563445834458344723446100.0400.00790.132623.894Sko644849848498486044852400.2180.0520.241858.9755Sko726625666256664226632800.2500.1080.136368.8416Sko81909989100891156910420.0680.5780.3460.181624.4247Sko901155341155781158981157660.1920.8340.4430.1971727.968Sko100a1520021522521533661526460.1640.8970.4230.3822969.7769Sko100b15389015389015427615412800.2500.1540.1891490.75810Sko100c1478621478681479201478940.0040.0390.0210.3252930.16711Sko100d1495761496661500921498620.0600.3440.1900.151472.92312Sko100e14915014915014974214938200.3960.1550.3416488.73813Sko100f1490361490701494701492910.0220.2910.1710.1441265.821The boldface denote that the best solutions (BS) of these instances have been obtained through the lowest value obtained by the objective function of the QAP model during the process of repetition using our HDDETS algorithm. Moreover, these solutions have achieved the best-known solution (BKS) reported in the QAPLIB dataset. Thus, obtained the values of the best gaps (BG) of the solutions of these instances are 0% according to equation (6).Table5 reports the results of 25 “Tai” type instances by our proposed algorithm. It is found that the algorithm could find the optimal solution for 16 instances at least once in 10 runs. Looking at the average solutions, the algorithm could find the optimal solution in all 10 runs for 10 instances, namely, Tai12a, Tai12b, Tai15a, Tai15b, Tai20a, Tai20b, Tai25a, Tai25b, Tai30b, and Tai64c, while for the rest of 15 instances, percentage of average gap is found to be very small, within 1.30%.Table 5
Results by HDDETS algorithm on “Tai” type instances.
No.InstanceBKSHDDETS algorithmBSWSASBGWGAGSDAT1Tai12a22441622441622441622441600000.5082Tai12b3946492539464925394649253946492500000.6843Tai15a38821438821438821438821400000.8474Tai15b5176526851765268517652685176526800000.815Tai20a70348270348270348270348200005.6536Tai20b12245531912245531912245531912245531900000.5117Tai25a116725611672561167256116725600007.8488Tai25b344355646344355646344355646344355646000013.469Tai30a1818146181814618181461818146000057.410Tai30b637117113637117113637117113637117113000029.79411Tai35a242200224220022435108242827500.5410.2590.06629.58912Tai35b283315445283315445283315445283315445000057.413Tai40a31393703141431315172731480600.0650.3930.2760.087138.35714Tai40b6372509486372509486372509486372509480000416.44515Tai50a49387964965748499178249812180.5451.0720.8581.297768.21416Tai50b458821517458821517458821517458821517000048.47917Tai60a72059627259430732121272967550.7421.5991.260.294921.08918Tai60b6082150546082150546082150546082150540000123.70219Tai64c185592818559281855928185592800008.30820Tai80a134991841361688013678302136543880.8711.3261.1490.2151195.73621Tai80b81841504381841504381841504381841504300001399.88322Tai100a210447522125660621318876213048050.6210.9160.7680.2022740.75523Tai100b11859961371187179912121218293111916320070.0992.2080.4750.6241553.48124Tai150b4988966435018924355081733325052610570.6001.8591.2750.4429402.76025Tai256c447592944478641844838798448132760.0600.1200.1200.04141014.570The boldface denote that the best solutions (BS) of these instances have been obtained through the lowest value obtained by the objective function of the QAP model during the process of repetition using our HDDETS algorithm. Moreover, these solutions have achieved the best-known solution (BKS) reported in the QAPLIB dataset. Thus, obtained the values of the best gaps (BG) of the solutions of these instances are 0% according to equation (6).Further, the results of the proposed HDDETS algorithm on all three types of instances are discussed and analyzed statistically by using the SPSS software. Table6 reports the results of statistical analysis of the proposed algorithm on 56 instances. The results showed that the best value is achieved for 42 of 56 instances (75%) with a 0% gap, while for the remaining 14 instances, results are very close to optimal solutions, within a gap of less than 1%.Table 6
Best gap by HDDETS algorithm on “Esc,” “Sko,” and “Tai” instances.
Best gap (%)FrequencyPercentageCumulative percentage0.0004275.075.00.00411.876.80.02211.878.60.06023.682.10.06511.883.90.06811.885.70.09911.887.50.16411.889.30.19211.891.10.54511.892.90.60011.894.60.62111.896.40.74211.898.20.87111.8100.0Total56100.0A graphical representation of the best gap from Table6 has been presented in Figure 6.Figure 6
A graphical representation of the best gap in Table6.Figure7 shows the average of the best gap and the average of the worst gap of the solutions of "Esc," "Sko," and "Tai" instances using our proposed HDDETS algorithm.Figure 7
Comparison between an average best gap and average worst gap obtained by HDDETS algorithm on “Esc,” “Sko,” and “Tai” instances.Statistical analysis presented in Table7 proved that the performance of the proposed algorithm is efficient and effective, as the mean of gaps is 0.073 for all the 56 instances and the maximum value of the gaps was observed to be 0.871. The variance of the gap is found to be 0.039, which indicates that the solutions obtained are to some extent identical to the solutions when compared with the standard QAP.


### 5.2. Comparisons between DDE, TS, and HDDETS Algorithms

This section has been covered by two scenarios. The first relates to the comparisons between the DDE, TS, and HDDETS algorithms, while the second presents and discusses the results statistically. The results of the comparisons between the DDE, TS, and HDDETS algorithms are given in Tables8–10 on the instances belonging to the three types (“Esc,” “Sko,” and “Tai”) of the QAP instances.Table 7
Statistical analysis on best gap by HDDETS algorithm on “Esc,” “Sko,” and “Tai” instances.
DescriptionValueNo. of instances56Mean0.073Std. deviation0.197Variance0.039Range0.871Minimum0.000Maximum0.871Table 8
Comparisons on “Esc” type instances.
No.InstanceBest gap (DDE)Best gap (TS)Best gap (HDDETS)1Esc16a0002Esc16b0003Esc16c0004Esc16d0005Esc16e0006Esc16g0007Esc16h0008Esc16i015.38409Esc16j014.285010Esc32a20.0000011Esc32b19.0470012Esc32c00013Esc32d00014Esc32e00.913015Esc32g00016Esc32h0.9130017Esc64a00018Esc128a34.37500Table 9
Comparisons on “Sko” instances.
No.InstanceBest gap (DDE)Best gap (TS)Best gap (HDDETS)1Sko422.5672.20302Sko491.5991.94103Sko562.7041.96704Sko643.3652.58105Sko723.5953.4200.0906Sko813.3562.9600.0687Sko903.6613.3680.1928Sko100a3.3263.0180.2069Sko100b3.1843.0820.1810Sko100c3.9073.8720.19311Sko100d3.8663.4030.12412Sko100e3.8863.2970.24413Sko100f3.6163.0160.454There are 18 “Esc” type instances in the QAPLIB website that have optimal solutions. The results in Table8 show that the DDE and TS algorithms have optimal solutions for 14 and 15 instances, respectively, while the HDDETS algorithm obtained optimal solutions for all the 18 instances. Figures 8–10 show graphical representations of the best gap from Table 8.Figure 8
Best gap by DDE algorithm on “Esc” instances.Figure 9
Best gap by TS algorithm on “Esc” instances.Figure 10
Best gap by HDDETS algorithm on “Esc” instances.Table11 reports statistical measures for DDE, TS, and HDDETS algorithms on “Esc” type instances. According to the results reported in this table, the means of the gaps are 4.129, 1.699, and 0 by the DDE, TS, and HDDETS algorithms, respectively. Variances of gaps obtained by the DEE, TS, and HDDETS algorithms are 96.369, 22.918, and 0, respectively. Additionally, the maximum gaps obtained are 34.375, 15.384, and 0 using DEE, TS, and HDDETS algorithms, respectively. In conclusion, performance evaluation for the proposed hybrid algorithm, HDDETS, indicates that it outperforms both DDE and TS on the “Esc” type instances.Table 10
Comparisons on “Tai” instances.
No.InstanceBest gap (DDE)Best gap (TS)Best gap (HDDETS)1Tai12a0002Tai12b2.849003Tai15a2.0430.1704Tai15b0.339005Tai20a2.9831.4006Tai20b4.5922.4607Tai25a1.743008Tai25b4.2162.8109Tai30a2.0391.93010Tai30b4.5484.47011Tai35a3.5022.70012Tai35b4.7772.70013Tai40a2.1572.56014Tai40b4.7485.850.06515Tai50a0.0763.18016Tai50b5.2462.930.01917Tai60a3.3883.51018Tai60b4.6094.200.04719Tai64c0.4170.09020Tai80a5.6653.761.05921Tai80b7.4864.35022Tai100a5.74310.851.14623Tai100b7.1165.200.09924Tai150b8.6076.220.625Tai256c1.5640.300.06Another comparison was made among DDE, TS, and HDDETS algorithms on 13 “Sko” type instances. Neither DDE nor TS could reach any best-known solution out of 13 instances, while the proposed algorithm managed to obtain the best-known solution of 4 instances. Table9 reports these results.Graphical representations of the best gaps reported in Table9 are presented in Figures 11–13. Further, the results are discussed according to the statistical measures that are presented in Table 12.Table 11
Statistical measures for DDE, TS, and HDDETS algorithms on “Esc” instances.
DescriptionDDE algorithmTS algorithmHDDETS algorithmNo. of instances181818Mean4.1291.6990Std. deviation9.8164.7870Variance96.36922.9180Range34.37515.3840Minimum000Maximum34.37515.3840The means of the gaps are obtained as 3.279, 2.932, and 0.039 by DDE, TS, and HDDETS algorithms, respectively. Variances among the gaps are converging, and they are 0.655, 0596, and 0.066 by DDE, TS, and HDDETS algorithms, respectively. In addition, the recorded maximum gaps are 3.907, 3.872, and 0.192 derived by DDE, TS, and HDDETS algorithms, respectively. Based on the abovementioned study, one can say that the performance of the proposed algorithm, HDDETS, is found to be better than the performance of DDE and TS algorithms on the “Sko” type instances. Further, 25 “Tai” type instances have been used for comparison among the proposed hybrid algorithm (HDDETS) and DDE and TS algorithms. Table10 shows the results of this comparison.Figure 11
Best gap by DDE algorithm on “Sko” instances.Figure 12
Best gap by TS algorithm on “Sko” instances.Figure 13
Best gap by HDDETS algorithm on “Sko” instances.From Table10, it is found that the DDE algorithm hits the optimal solution for only one instance at least once in 10 runs, whereas TS algorithm obtained four optimal solutions. The proposed algorithm, HDDETS, could hit the optimal solutions for 17 instances at least once in 10 runs. For the remaining 8 instances, the gap is very small, within less than 1.15%. Figures 14–16 show graphical representations of the best gaps reported in Table 10.Figure 14
Best gap by DDE algorithm on “Tai” instances.Figure 15
Best gap by TS algorithm on “Tai” instances.Figure 16
Best gap by HDDETS algorithm on “Tai” instances.Table13 shows the statistical measures that are used to compare these algorithms for “Tai” type instances.Table 12
Statistical measures for DDE, TS, and HDDETS algorithms on “Sko” instances.
DescriptionDDE algorithmTS algorithmHDDETS algorithmInstance131313Mean3.2792.9320.039Std. deviation0.6550.5960.066Variance0.4290.3560.004Range2.3081.9310.192Minimum1.5991.9410.00Maximum3.9073.8720.192Table 13
Statistical measures for DDE, TS, and HDDETS algorithms on ‘Tai' instances.
DescriptionDDE algorithmTS algorithmHDDETS algorithmInstance252525Mean3.6182.8640.144Std. deviation2.3431.7910.277Variance5.4903.2090.077Range8.6110.850.87Minimum0.000.000.00Maximum8.6110.850.87The means of the gaps by DDE and TS algorithms are 3.618 and 2.864, respectively. By the proposed algorithm, the mean of the best gaps is 0.144. It is worth noting that the variance among the gaps is 2.343 by the DDE algorithm, while the variance by the TS algorithm is 3.209. In the same context, the HDDETS algorithm has got the best variance among the gaps (0.077). Moreover, the maximum relative gap value was 8.61%, 10.85%, and 0.87% obtained by the DDE, TS, and HDDETS algorithms, respectively.


### 5.3. Real-World Application

There are many studies that have proven the successful use of the QAP in real applications, because of its ability to find the best allocation of locations for the available facilities. The artificial bee colony algorithm was used in [32] which aimed at solving a QAP within the context of Azadi Hospital so that a better distribution of advisory services can be found within the hospital building. This way, the efforts required when moving patients from one advisory service to another are minimized, which in turn also reduces the total distance required for transmitting the patients. As an evaluation of the efficiency of the performance of the proposed algorithm in this research, it was applied to the data of this case study.


#### 5.3.1. Data Description of the Azadi Hospital Layout Problem

The hospital layout problem aims for the distribution of departments inside the hospitals to minimize the total travel distance by patients. Azadi Hospital, which was used for this study, was founded in 1985. Recent study [32] dealt with this problem and has discussed the description of the data as follows.The hospital offers a variety of quality healthcare services and is operated by the most specialized doctors with sufficient experience in the field of medicine. The hospital, which houses approximately 398 beds, is made up of 7 floors and is well-equipped with state-of-the-art facilities and equipment. In addition, the hospital is also equipped with operation theatres for minor and major procedures, an emergency room, and a variety of laboratories in which different kinds of ailments can be diagnosed. Despite the fact that the hospital is made up of different floors, sections, and units, this study only focused on 30 facilities located on the ground floor, because this floor witnesses the influx of patients on a daily basis, and for this reason, this specific floor is used for the study.The problem was divided into three categories, the first category includes fixed consulting services, which must be installed for the lack of other similar places such as entry, laboratory, pharmacy, rays, computerized axial tomography, magnetic resonance imaging, electrocardiography, and physical therapy. The second category represents consulting departments such as a dental department, ENT department, and ophthalmology department, while the third category represents consulting rooms such as echo, straining the heart, neurological, lung functions, ultrasound, urologist, pediatric, vaccine, general surgery, trauma room, gynecology, the internists1, the internists2, minor operations, interactions skin, dermatologic, and hematological.In order to obtain the flow matrix entries, the flow between each pair of clinics was averaged. The paths which were taken by patients during their movement from one location to another were traced by measuring the distances between locations. Based on observation, patients are required to go and mark off their cards in the pharmacy after they had visited several clinics. It was noticed that a patient, after being through a sequence of visits to more than one clinic, must go to the pharmacy to mark off his card. Table14 shows the distribution of clinics to rooms by using the study [32].Table 14
Distribution of the advisory clinics by [32].
LocationFacility (advisory clinic)1Entry2Pharmacy3Laboratory4Rays5Computerized axial6Magnetic resonance imaging7Electrocardiography8Physical therapy9Dentistry10Ear nose and throat11Ophthalmologic12Allergy and asthma13Lung functions14Endoscopy15Straining the heart16Neurological17Echo18Gynecology19Urologist20Dermatologic21Pediatric22Ultrasound23Interactions skin24The internists125Hematological26Trauma room27The internists228Minor operations29General surgery30Vaccine


#### 5.3.2. Justifications of the Case Study

Given the applications domain of the QAP, the lack of proper layout of the clinic’s locations inside the hospital requires patients to cover a lot of distance [32]; therefore, the clinics within a hospital need to be meticulously organized, as disorganization can result in too much movement for patients, thereby leading to wastage of time. In the hospital, the layout can be formulated as a QAP for locating the clinics within the hospital which can substantially reduce the total distance that patients travel as they move from one clinic to another in the hospital building. On the other hand, modelling the hospital’s departments on QAP minimizes the travel distance for patients [8]. This helps to(i)
Reduce the traveling efforts of patients between departments, thus saving their time.(ii)
Improve the service efficiency of the hospital, and(iii)
The hospital would be capable to serve a greater number of patients daily.


#### 5.3.3. Location of the Study

This study was conducted at the Azadi Hospital in Kirkuk Governorate, Iraq. It involved the distribution of thirty advisory clinics inside the hospital, based on the QAP model, and found the minimized cost through solving the QAP model by using the proposed algorithm. Figure17 shows the locations of the case study in this study.Figure 17
Locations of the study area, Azadi Hospital in Kirkuk Governorate, Iraq.


#### 5.3.4. Applying the Proposed Algorithm HDDETS on Azadi Hospital Layout Problem

The proposed hybrid algorithm HDDETS has given a clear picture of the effective performance of the algorithm in addition to obtaining optimal solutions for some instances of QAP data with reasonable computational time, unlike exact algorithms. Moreover, the results have proven the ability of the HDDETS algorithm to find the optimal solution if the size of the problem is more than 30 (locations/facilities), such as Tai30b, Esc32a, Esc32b, Esc32c, Esc32d, Esc32e, Esc32g, Esc32h, Esc64a, and Esc128a.Modelling the hospital’s departments on QAP will optimize the distribution of the departments within the hospital which helps to obtain a minimum total cost. On one hand, the cost of transferring patients when they move from one advisory clinic to another was 8, 974, 071 meters per month. This cost has been reduced to 8, 312, 830 meters per month by using the study [32] based on the distribution of the advisory clinics in Table 14. The minimum cost value of the QAP problem is obtained when the optimal distribution for those facilities’ locations is found. Table 15 presents the permutation of the optimal distribution of the advisory clinics inside Azadi Hospital by using the HDDETS algorithm.Table 15
New distribution of the advisory clinics.
LocationFacilities (advisory clinics)1Entry2Pharmacy3Laboratory4Rays5Computerized axial6Magnetic resonance imaging7Electrocardiography8Physical therapy9Dentistry10Trauma room11Echo12Neurological13Allergy and asthma14Hematological15Lung functions16Straining the heart17Interactions skin18Minor operations19Endoscopy20The internists 121The internists 222General surgery23Vaccine24Gynecology25Urologist26Ultrasound27Ear nose and throat28Dermatologic29Pediatric30OphthalmologicThe Azadi Hospital layout problem consists of 30 advisory clinics and the best cost result of transferring patients inside the hospital was 8, 312, 830 meters per month obtained by the study [32] which has been optimizing this value to 4, 559, 262 meters per month when using the proposed HDDETS algorithm.


## 5.1. Implementations of HDDETS Algorithm on QAP Instances

This section reports and discusses the results by the proposed HDDETS algorithm on three types of benchmark QAP instances from QAPLIB website, namely, “Esc,” “Sko,” and “Tai.” These results include some statistical metrics such as the best-known solution (BKS) reported in QAPLIB website, best solution (BS), worst solution (WS), average solution (AS), best gap (BG), worst gap (WG), average gap (AG), standard deviation (SD), and average time (AT) over 10 runs. The following equation is used to find the percentage of gap (G):(6)G=100×BS−BKSBKS.Table3 reports the results of 18 “Esc” type instances obtained by the proposed hybrid HDDETS algorithm. It is found from the table that the algorithm has ability to provide optimal solutions for all 18 instances in all 10 runs within a reasonable computational time. Table 4 reports the results of 13 “Sko” type instances by the HDDETS algorithm. These instances are considered as a challenge to all algorithms because no heuristic algorithm could find the best-known solutions (supposed to be optimal solutions) for all instances within reasonable computational time. It is found from Table 4 that the proposed algorithm could find the optimal solutions for 7 instances at least once in 10 runs. Also, the results of the remaining 6 instances are very close to optimal solutions, within a gap of less than 1% within a reasonable time.Table 3
Results by HDDETS algorithm on “Esc” type instances.
No.InstanceBKSHDDETS algorithmBSWSASBGWGAGSDAT1Esc16a6868686800000.5332Esc16b29229229229200000.6343Esc16c16016016016000000.5774Esc16d1616161600000.5325Esc16e2828282800006.4966Esc16g6868686800006.5787Esc16h2626262600000.4728Esc16i99699699699600000.4739Esc16j1414141400000.62910Esc32a888800000.73711Esc32b13013013013000007.95312Esc32c16816816816800001.92413Esc32d64264264264200002.27614Esc32e20020020020000002.18415Esc32g666600001.83516Esc32h43843843843800001.90717Esc64a11611611611600001.89618Esc128a6464646400009.927The boldface denote that the best solutions (BS) of these instances have been obtained through the lowest value obtained by the objective function of the QAP model during the process of repetition using our HDDETS algorithm. Moreover, these solutions have achieved the best-known solution (BKS) reported in the QAPLIB dataset. Thus, obtained the values of the best gaps (BG) of the solutions of these instances are 0% according to equation (6).Table 4
Results by HDDETS algorithm on “Sko” type instances.
No.InstanceBKSHDDETS algorithmBSWSASBGWGAGSDAT1Sko42158121581215812158120000146.9592Sko492338623386234022339400.0680.0320.06327.0013Sko563445834458344723446100.0400.00790.132623.894Sko644849848498486044852400.2180.0520.241858.9755Sko726625666256664226632800.2500.1080.136368.8416Sko81909989100891156910420.0680.5780.3460.181624.4247Sko901155341155781158981157660.1920.8340.4430.1971727.968Sko100a1520021522521533661526460.1640.8970.4230.3822969.7769Sko100b15389015389015427615412800.2500.1540.1891490.75810Sko100c1478621478681479201478940.0040.0390.0210.3252930.16711Sko100d1495761496661500921498620.0600.3440.1900.151472.92312Sko100e14915014915014974214938200.3960.1550.3416488.73813Sko100f1490361490701494701492910.0220.2910.1710.1441265.821The boldface denote that the best solutions (BS) of these instances have been obtained through the lowest value obtained by the objective function of the QAP model during the process of repetition using our HDDETS algorithm. Moreover, these solutions have achieved the best-known solution (BKS) reported in the QAPLIB dataset. Thus, obtained the values of the best gaps (BG) of the solutions of these instances are 0% according to equation (6).Table5 reports the results of 25 “Tai” type instances by our proposed algorithm. It is found that the algorithm could find the optimal solution for 16 instances at least once in 10 runs. Looking at the average solutions, the algorithm could find the optimal solution in all 10 runs for 10 instances, namely, Tai12a, Tai12b, Tai15a, Tai15b, Tai20a, Tai20b, Tai25a, Tai25b, Tai30b, and Tai64c, while for the rest of 15 instances, percentage of average gap is found to be very small, within 1.30%.Table 5
Results by HDDETS algorithm on “Tai” type instances.
No.InstanceBKSHDDETS algorithmBSWSASBGWGAGSDAT1Tai12a22441622441622441622441600000.5082Tai12b3946492539464925394649253946492500000.6843Tai15a38821438821438821438821400000.8474Tai15b5176526851765268517652685176526800000.815Tai20a70348270348270348270348200005.6536Tai20b12245531912245531912245531912245531900000.5117Tai25a116725611672561167256116725600007.8488Tai25b344355646344355646344355646344355646000013.469Tai30a1818146181814618181461818146000057.410Tai30b637117113637117113637117113637117113000029.79411Tai35a242200224220022435108242827500.5410.2590.06629.58912Tai35b283315445283315445283315445283315445000057.413Tai40a31393703141431315172731480600.0650.3930.2760.087138.35714Tai40b6372509486372509486372509486372509480000416.44515Tai50a49387964965748499178249812180.5451.0720.8581.297768.21416Tai50b458821517458821517458821517458821517000048.47917Tai60a72059627259430732121272967550.7421.5991.260.294921.08918Tai60b6082150546082150546082150546082150540000123.70219Tai64c185592818559281855928185592800008.30820Tai80a134991841361688013678302136543880.8711.3261.1490.2151195.73621Tai80b81841504381841504381841504381841504300001399.88322Tai100a210447522125660621318876213048050.6210.9160.7680.2022740.75523Tai100b11859961371187179912121218293111916320070.0992.2080.4750.6241553.48124Tai150b4988966435018924355081733325052610570.6001.8591.2750.4429402.76025Tai256c447592944478641844838798448132760.0600.1200.1200.04141014.570The boldface denote that the best solutions (BS) of these instances have been obtained through the lowest value obtained by the objective function of the QAP model during the process of repetition using our HDDETS algorithm. Moreover, these solutions have achieved the best-known solution (BKS) reported in the QAPLIB dataset. Thus, obtained the values of the best gaps (BG) of the solutions of these instances are 0% according to equation (6).Further, the results of the proposed HDDETS algorithm on all three types of instances are discussed and analyzed statistically by using the SPSS software. Table6 reports the results of statistical analysis of the proposed algorithm on 56 instances. The results showed that the best value is achieved for 42 of 56 instances (75%) with a 0% gap, while for the remaining 14 instances, results are very close to optimal solutions, within a gap of less than 1%.Table 6
Best gap by HDDETS algorithm on “Esc,” “Sko,” and “Tai” instances.
Best gap (%)FrequencyPercentageCumulative percentage0.0004275.075.00.00411.876.80.02211.878.60.06023.682.10.06511.883.90.06811.885.70.09911.887.50.16411.889.30.19211.891.10.54511.892.90.60011.894.60.62111.896.40.74211.898.20.87111.8100.0Total56100.0A graphical representation of the best gap from Table6 has been presented in Figure 6.Figure 6
A graphical representation of the best gap in Table6.Figure7 shows the average of the best gap and the average of the worst gap of the solutions of "Esc," "Sko," and "Tai" instances using our proposed HDDETS algorithm.Figure 7
Comparison between an average best gap and average worst gap obtained by HDDETS algorithm on “Esc,” “Sko,” and “Tai” instances.Statistical analysis presented in Table7 proved that the performance of the proposed algorithm is efficient and effective, as the mean of gaps is 0.073 for all the 56 instances and the maximum value of the gaps was observed to be 0.871. The variance of the gap is found to be 0.039, which indicates that the solutions obtained are to some extent identical to the solutions when compared with the standard QAP.


## 5.2. Comparisons between DDE, TS, and HDDETS Algorithms

This section has been covered by two scenarios. The first relates to the comparisons between the DDE, TS, and HDDETS algorithms, while the second presents and discusses the results statistically. The results of the comparisons between the DDE, TS, and HDDETS algorithms are given in Tables8–10 on the instances belonging to the three types (“Esc,” “Sko,” and “Tai”) of the QAP instances.Table 7
Statistical analysis on best gap by HDDETS algorithm on “Esc,” “Sko,” and “Tai” instances.
DescriptionValueNo. of instances56Mean0.073Std. deviation0.197Variance0.039Range0.871Minimum0.000Maximum0.871Table 8
Comparisons on “Esc” type instances.
No.InstanceBest gap (DDE)Best gap (TS)Best gap (HDDETS)1Esc16a0002Esc16b0003Esc16c0004Esc16d0005Esc16e0006Esc16g0007Esc16h0008Esc16i015.38409Esc16j014.285010Esc32a20.0000011Esc32b19.0470012Esc32c00013Esc32d00014Esc32e00.913015Esc32g00016Esc32h0.9130017Esc64a00018Esc128a34.37500Table 9
Comparisons on “Sko” instances.
No.InstanceBest gap (DDE)Best gap (TS)Best gap (HDDETS)1Sko422.5672.20302Sko491.5991.94103Sko562.7041.96704Sko643.3652.58105Sko723.5953.4200.0906Sko813.3562.9600.0687Sko903.6613.3680.1928Sko100a3.3263.0180.2069Sko100b3.1843.0820.1810Sko100c3.9073.8720.19311Sko100d3.8663.4030.12412Sko100e3.8863.2970.24413Sko100f3.6163.0160.454There are 18 “Esc” type instances in the QAPLIB website that have optimal solutions. The results in Table8 show that the DDE and TS algorithms have optimal solutions for 14 and 15 instances, respectively, while the HDDETS algorithm obtained optimal solutions for all the 18 instances. Figures 8–10 show graphical representations of the best gap from Table 8.Figure 8
Best gap by DDE algorithm on “Esc” instances.Figure 9
Best gap by TS algorithm on “Esc” instances.Figure 10
Best gap by HDDETS algorithm on “Esc” instances.Table11 reports statistical measures for DDE, TS, and HDDETS algorithms on “Esc” type instances. According to the results reported in this table, the means of the gaps are 4.129, 1.699, and 0 by the DDE, TS, and HDDETS algorithms, respectively. Variances of gaps obtained by the DEE, TS, and HDDETS algorithms are 96.369, 22.918, and 0, respectively. Additionally, the maximum gaps obtained are 34.375, 15.384, and 0 using DEE, TS, and HDDETS algorithms, respectively. In conclusion, performance evaluation for the proposed hybrid algorithm, HDDETS, indicates that it outperforms both DDE and TS on the “Esc” type instances.Table 10
Comparisons on “Tai” instances.
No.InstanceBest gap (DDE)Best gap (TS)Best gap (HDDETS)1Tai12a0002Tai12b2.849003Tai15a2.0430.1704Tai15b0.339005Tai20a2.9831.4006Tai20b4.5922.4607Tai25a1.743008Tai25b4.2162.8109Tai30a2.0391.93010Tai30b4.5484.47011Tai35a3.5022.70012Tai35b4.7772.70013Tai40a2.1572.56014Tai40b4.7485.850.06515Tai50a0.0763.18016Tai50b5.2462.930.01917Tai60a3.3883.51018Tai60b4.6094.200.04719Tai64c0.4170.09020Tai80a5.6653.761.05921Tai80b7.4864.35022Tai100a5.74310.851.14623Tai100b7.1165.200.09924Tai150b8.6076.220.625Tai256c1.5640.300.06Another comparison was made among DDE, TS, and HDDETS algorithms on 13 “Sko” type instances. Neither DDE nor TS could reach any best-known solution out of 13 instances, while the proposed algorithm managed to obtain the best-known solution of 4 instances. Table9 reports these results.Graphical representations of the best gaps reported in Table9 are presented in Figures 11–13. Further, the results are discussed according to the statistical measures that are presented in Table 12.Table 11
Statistical measures for DDE, TS, and HDDETS algorithms on “Esc” instances.
DescriptionDDE algorithmTS algorithmHDDETS algorithmNo. of instances181818Mean4.1291.6990Std. deviation9.8164.7870Variance96.36922.9180Range34.37515.3840Minimum000Maximum34.37515.3840The means of the gaps are obtained as 3.279, 2.932, and 0.039 by DDE, TS, and HDDETS algorithms, respectively. Variances among the gaps are converging, and they are 0.655, 0596, and 0.066 by DDE, TS, and HDDETS algorithms, respectively. In addition, the recorded maximum gaps are 3.907, 3.872, and 0.192 derived by DDE, TS, and HDDETS algorithms, respectively. Based on the abovementioned study, one can say that the performance of the proposed algorithm, HDDETS, is found to be better than the performance of DDE and TS algorithms on the “Sko” type instances. Further, 25 “Tai” type instances have been used for comparison among the proposed hybrid algorithm (HDDETS) and DDE and TS algorithms. Table10 shows the results of this comparison.Figure 11
Best gap by DDE algorithm on “Sko” instances.Figure 12
Best gap by TS algorithm on “Sko” instances.Figure 13
Best gap by HDDETS algorithm on “Sko” instances.From Table10, it is found that the DDE algorithm hits the optimal solution for only one instance at least once in 10 runs, whereas TS algorithm obtained four optimal solutions. The proposed algorithm, HDDETS, could hit the optimal solutions for 17 instances at least once in 10 runs. For the remaining 8 instances, the gap is very small, within less than 1.15%. Figures 14–16 show graphical representations of the best gaps reported in Table 10.Figure 14
Best gap by DDE algorithm on “Tai” instances.Figure 15
Best gap by TS algorithm on “Tai” instances.Figure 16
Best gap by HDDETS algorithm on “Tai” instances.Table13 shows the statistical measures that are used to compare these algorithms for “Tai” type instances.Table 12
Statistical measures for DDE, TS, and HDDETS algorithms on “Sko” instances.
DescriptionDDE algorithmTS algorithmHDDETS algorithmInstance131313Mean3.2792.9320.039Std. deviation0.6550.5960.066Variance0.4290.3560.004Range2.3081.9310.192Minimum1.5991.9410.00Maximum3.9073.8720.192Table 13
Statistical measures for DDE, TS, and HDDETS algorithms on ‘Tai' instances.
DescriptionDDE algorithmTS algorithmHDDETS algorithmInstance252525Mean3.6182.8640.144Std. deviation2.3431.7910.277Variance5.4903.2090.077Range8.6110.850.87Minimum0.000.000.00Maximum8.6110.850.87The means of the gaps by DDE and TS algorithms are 3.618 and 2.864, respectively. By the proposed algorithm, the mean of the best gaps is 0.144. It is worth noting that the variance among the gaps is 2.343 by the DDE algorithm, while the variance by the TS algorithm is 3.209. In the same context, the HDDETS algorithm has got the best variance among the gaps (0.077). Moreover, the maximum relative gap value was 8.61%, 10.85%, and 0.87% obtained by the DDE, TS, and HDDETS algorithms, respectively.


## 5.3. Real-World Application

There are many studies that have proven the successful use of the QAP in real applications, because of its ability to find the best allocation of locations for the available facilities. The artificial bee colony algorithm was used in [32] which aimed at solving a QAP within the context of Azadi Hospital so that a better distribution of advisory services can be found within the hospital building. This way, the efforts required when moving patients from one advisory service to another are minimized, which in turn also reduces the total distance required for transmitting the patients. As an evaluation of the efficiency of the performance of the proposed algorithm in this research, it was applied to the data of this case study.


### 5.3.1. Data Description of the Azadi Hospital Layout Problem

The hospital layout problem aims for the distribution of departments inside the hospitals to minimize the total travel distance by patients. Azadi Hospital, which was used for this study, was founded in 1985. Recent study [32] dealt with this problem and has discussed the description of the data as follows.The hospital offers a variety of quality healthcare services and is operated by the most specialized doctors with sufficient experience in the field of medicine. The hospital, which houses approximately 398 beds, is made up of 7 floors and is well-equipped with state-of-the-art facilities and equipment. In addition, the hospital is also equipped with operation theatres for minor and major procedures, an emergency room, and a variety of laboratories in which different kinds of ailments can be diagnosed. Despite the fact that the hospital is made up of different floors, sections, and units, this study only focused on 30 facilities located on the ground floor, because this floor witnesses the influx of patients on a daily basis, and for this reason, this specific floor is used for the study.The problem was divided into three categories, the first category includes fixed consulting services, which must be installed for the lack of other similar places such as entry, laboratory, pharmacy, rays, computerized axial tomography, magnetic resonance imaging, electrocardiography, and physical therapy. The second category represents consulting departments such as a dental department, ENT department, and ophthalmology department, while the third category represents consulting rooms such as echo, straining the heart, neurological, lung functions, ultrasound, urologist, pediatric, vaccine, general surgery, trauma room, gynecology, the internists1, the internists2, minor operations, interactions skin, dermatologic, and hematological.In order to obtain the flow matrix entries, the flow between each pair of clinics was averaged. The paths which were taken by patients during their movement from one location to another were traced by measuring the distances between locations. Based on observation, patients are required to go and mark off their cards in the pharmacy after they had visited several clinics. It was noticed that a patient, after being through a sequence of visits to more than one clinic, must go to the pharmacy to mark off his card. Table14 shows the distribution of clinics to rooms by using the study [32].Table 14
Distribution of the advisory clinics by [32].
LocationFacility (advisory clinic)1Entry2Pharmacy3Laboratory4Rays5Computerized axial6Magnetic resonance imaging7Electrocardiography8Physical therapy9Dentistry10Ear nose and throat11Ophthalmologic12Allergy and asthma13Lung functions14Endoscopy15Straining the heart16Neurological17Echo18Gynecology19Urologist20Dermatologic21Pediatric22Ultrasound23Interactions skin24The internists125Hematological26Trauma room27The internists228Minor operations29General surgery30Vaccine


### 5.3.2. Justifications of the Case Study

Given the applications domain of the QAP, the lack of proper layout of the clinic’s locations inside the hospital requires patients to cover a lot of distance [32]; therefore, the clinics within a hospital need to be meticulously organized, as disorganization can result in too much movement for patients, thereby leading to wastage of time. In the hospital, the layout can be formulated as a QAP for locating the clinics within the hospital which can substantially reduce the total distance that patients travel as they move from one clinic to another in the hospital building. On the other hand, modelling the hospital’s departments on QAP minimizes the travel distance for patients [8]. This helps to(i)
Reduce the traveling efforts of patients between departments, thus saving their time.(ii)
Improve the service efficiency of the hospital, and(iii)
The hospital would be capable to serve a greater number of patients daily.


### 5.3.3. Location of the Study

This study was conducted at the Azadi Hospital in Kirkuk Governorate, Iraq. It involved the distribution of thirty advisory clinics inside the hospital, based on the QAP model, and found the minimized cost through solving the QAP model by using the proposed algorithm. Figure17 shows the locations of the case study in this study.Figure 17
Locations of the study area, Azadi Hospital in Kirkuk Governorate, Iraq.


### 5.3.4. Applying the Proposed Algorithm HDDETS on Azadi Hospital Layout Problem

The proposed hybrid algorithm HDDETS has given a clear picture of the effective performance of the algorithm in addition to obtaining optimal solutions for some instances of QAP data with reasonable computational time, unlike exact algorithms. Moreover, the results have proven the ability of the HDDETS algorithm to find the optimal solution if the size of the problem is more than 30 (locations/facilities), such as Tai30b, Esc32a, Esc32b, Esc32c, Esc32d, Esc32e, Esc32g, Esc32h, Esc64a, and Esc128a.Modelling the hospital’s departments on QAP will optimize the distribution of the departments within the hospital which helps to obtain a minimum total cost. On one hand, the cost of transferring patients when they move from one advisory clinic to another was 8, 974, 071 meters per month. This cost has been reduced to 8, 312, 830 meters per month by using the study [32] based on the distribution of the advisory clinics in Table 14. The minimum cost value of the QAP problem is obtained when the optimal distribution for those facilities’ locations is found. Table 15 presents the permutation of the optimal distribution of the advisory clinics inside Azadi Hospital by using the HDDETS algorithm.Table 15
New distribution of the advisory clinics.
LocationFacilities (advisory clinics)1Entry2Pharmacy3Laboratory4Rays5Computerized axial6Magnetic resonance imaging7Electrocardiography8Physical therapy9Dentistry10Trauma room11Echo12Neurological13Allergy and asthma14Hematological15Lung functions16Straining the heart17Interactions skin18Minor operations19Endoscopy20The internists 121The internists 222General surgery23Vaccine24Gynecology25Urologist26Ultrasound27Ear nose and throat28Dermatologic29Pediatric30OphthalmologicThe Azadi Hospital layout problem consists of 30 advisory clinics and the best cost result of transferring patients inside the hospital was 8, 312, 830 meters per month obtained by the study [32] which has been optimizing this value to 4, 559, 262 meters per month when using the proposed HDDETS algorithm.


## 5.3.1. Data Description of the Azadi Hospital Layout Problem

The hospital layout problem aims for the distribution of departments inside the hospitals to minimize the total travel distance by patients. Azadi Hospital, which was used for this study, was founded in 1985. Recent study [32] dealt with this problem and has discussed the description of the data as follows.The hospital offers a variety of quality healthcare services and is operated by the most specialized doctors with sufficient experience in the field of medicine. The hospital, which houses approximately 398 beds, is made up of 7 floors and is well-equipped with state-of-the-art facilities and equipment. In addition, the hospital is also equipped with operation theatres for minor and major procedures, an emergency room, and a variety of laboratories in which different kinds of ailments can be diagnosed. Despite the fact that the hospital is made up of different floors, sections, and units, this study only focused on 30 facilities located on the ground floor, because this floor witnesses the influx of patients on a daily basis, and for this reason, this specific floor is used for the study.The problem was divided into three categories, the first category includes fixed consulting services, which must be installed for the lack of other similar places such as entry, laboratory, pharmacy, rays, computerized axial tomography, magnetic resonance imaging, electrocardiography, and physical therapy. The second category represents consulting departments such as a dental department, ENT department, and ophthalmology department, while the third category represents consulting rooms such as echo, straining the heart, neurological, lung functions, ultrasound, urologist, pediatric, vaccine, general surgery, trauma room, gynecology, the internists1, the internists2, minor operations, interactions skin, dermatologic, and hematological.In order to obtain the flow matrix entries, the flow between each pair of clinics was averaged. The paths which were taken by patients during their movement from one location to another were traced by measuring the distances between locations. Based on observation, patients are required to go and mark off their cards in the pharmacy after they had visited several clinics. It was noticed that a patient, after being through a sequence of visits to more than one clinic, must go to the pharmacy to mark off his card. Table14 shows the distribution of clinics to rooms by using the study [32].Table 14
Distribution of the advisory clinics by [32].
LocationFacility (advisory clinic)1Entry2Pharmacy3Laboratory4Rays5Computerized axial6Magnetic resonance imaging7Electrocardiography8Physical therapy9Dentistry10Ear nose and throat11Ophthalmologic12Allergy and asthma13Lung functions14Endoscopy15Straining the heart16Neurological17Echo18Gynecology19Urologist20Dermatologic21Pediatric22Ultrasound23Interactions skin24The internists125Hematological26Trauma room27The internists228Minor operations29General surgery30Vaccine


## 5.3.2. Justifications of the Case Study

Given the applications domain of the QAP, the lack of proper layout of the clinic’s locations inside the hospital requires patients to cover a lot of distance [32]; therefore, the clinics within a hospital need to be meticulously organized, as disorganization can result in too much movement for patients, thereby leading to wastage of time. In the hospital, the layout can be formulated as a QAP for locating the clinics within the hospital which can substantially reduce the total distance that patients travel as they move from one clinic to another in the hospital building. On the other hand, modelling the hospital’s departments on QAP minimizes the travel distance for patients [8]. This helps to(i)
Reduce the traveling efforts of patients between departments, thus saving their time.(ii)
Improve the service efficiency of the hospital, and(iii)
The hospital would be capable to serve a greater number of patients daily.


## 5.3.3. Location of the Study

This study was conducted at the Azadi Hospital in Kirkuk Governorate, Iraq. It involved the distribution of thirty advisory clinics inside the hospital, based on the QAP model, and found the minimized cost through solving the QAP model by using the proposed algorithm. Figure17 shows the locations of the case study in this study.Figure 17
Locations of the study area, Azadi Hospital in Kirkuk Governorate, Iraq.


## 5.3.4. Applying the Proposed Algorithm HDDETS on Azadi Hospital Layout Problem

The proposed hybrid algorithm HDDETS has given a clear picture of the effective performance of the algorithm in addition to obtaining optimal solutions for some instances of QAP data with reasonable computational time, unlike exact algorithms. Moreover, the results have proven the ability of the HDDETS algorithm to find the optimal solution if the size of the problem is more than 30 (locations/facilities), such as Tai30b, Esc32a, Esc32b, Esc32c, Esc32d, Esc32e, Esc32g, Esc32h, Esc64a, and Esc128a.Modelling the hospital’s departments on QAP will optimize the distribution of the departments within the hospital which helps to obtain a minimum total cost. On one hand, the cost of transferring patients when they move from one advisory clinic to another was 8, 974, 071 meters per month. This cost has been reduced to 8, 312, 830 meters per month by using the study [32] based on the distribution of the advisory clinics in Table 14. The minimum cost value of the QAP problem is obtained when the optimal distribution for those facilities’ locations is found. Table 15 presents the permutation of the optimal distribution of the advisory clinics inside Azadi Hospital by using the HDDETS algorithm.Table 15
New distribution of the advisory clinics.
LocationFacilities (advisory clinics)1Entry2Pharmacy3Laboratory4Rays5Computerized axial6Magnetic resonance imaging7Electrocardiography8Physical therapy9Dentistry10Trauma room11Echo12Neurological13Allergy and asthma14Hematological15Lung functions16Straining the heart17Interactions skin18Minor operations19Endoscopy20The internists 121The internists 222General surgery23Vaccine24Gynecology25Urologist26Ultrasound27Ear nose and throat28Dermatologic29Pediatric30OphthalmologicThe Azadi Hospital layout problem consists of 30 advisory clinics and the best cost result of transferring patients inside the hospital was 8, 312, 830 meters per month obtained by the study [32] which has been optimizing this value to 4, 559, 262 meters per month when using the proposed HDDETS algorithm.


## 6. Theoretical Analysis and Limitations of the Proposed Hybrid Algorithm HDDETS

The DDE and TS algorithms used in this study are metaheuristic algorithms. The literature studies have proven that the metaheuristic algorithms are one of the best techniques for handling NP-hard problems. According to the no free lunch (NFL) theorem [46], there is no algorithm that has better performance for all problems, but in some cases, it is poor. So, we aim to develop an algorithm that has good performance for a specific problem only, but not a comprehensive solution to all problems. Therefore, proposing a hybrid algorithm will increase the performance and thus increase the probability of obtaining the best results [47].Our study addresses some of the issues that meta-algorithms face, in particular, evolutionary algorithms that are not covered in the DDE algorithm, such as the stagnations, lack of the exploitation mechanism, and parameter tuning.Sometimes, the algorithm is not able to generate a new solution through the evolutionary process, which means it has lost its capability to improve the solutions. This issue is called stagnation, and Equation (5) has suggested for avoiding this issue, while the issue of the lack of the mechanism of exploitation in the DDE algorithm is addressed by hybridizing the algorithm with a TS algorithm that is characterized by having the feature of local exploitation based on searching in the neighborhoods of the solution in addition to the tabu list that is used to prevent visiting solutions that have been visited in the past. In this way, it prevents falling into local optimal. On the other hand, a grid search technique has been applied for parameter tuning, which is another issue in the optimization algorithms because of its prominent role in improving the performance of the algorithm.The results obtained by the HDDETS algorithm proved that the performance of the hybrid algorithm is better than the performance of both DDE and TS algorithms. The explanation of this outstanding and efficient performance has been discussed as follows: issues of stagnation and parameters tuning in addition to the lack of the mechanism of exploitation in the DDE algorithm have a negative and highly evident impact on the performance of this algorithm, as indicated in Figure18.Figure 18
Percent of cost enhancement of best solutions by DDE, TS, and HDDETS algorithms.The first task of the HDDETS algorithm is to generate a random population and then determine the best existing solution, thus calculating the cost of this solution by applying all stages of the algorithm. After that, we investigate the percentage of cost improvement of this solution in order to find the reasons for the difference in cost. This difference was made for three reasons. The first was related to the improvement of the solution found through the DDE algorithm part. The second reason was the improvement achieved using the TS algorithm part. The final reason of this improvement is the use of the entire HDDETS algorithm.It is noted that the percent of cost enhancement of the best solutions of the DDE algorithm part is small (4.27%) because it suffers from the abovementioned issues. The TS algorithm part is characterized by using local exploitation, by searching in the areas of the solution. This algorithm resulted in an improved cost enhancement of the best solutions (26.12%). Finally, we proposed the hybrid algorithm HDDETS, using global exploration and local exploitation mechanisms that produce a more balanced algorithm. This balance is positively reflected by the increase in cost enhancement percent of best solutions (69.61%) using the entire HDDETS algorithm within a reasonable time.In general, the proposed hybrid algorithm HDDETS has proven to be efficient in solving problems that have a large-scale implication which is considered a challenge for all algorithms. However, there are still some limitations that must be addressed. This study had applied crossover operators in the stage of crossover in the DDE algorithm called uniform-like crossover (ULX) although there are other types of crossover operators such as multiple parent crossover operator (MPX) and cycle crossover (CX) that have been suggested for the QAP with other algorithms. It is difficult for one study to cover all the operators that have been proposed in the literature with other algorithms.The time for metaheuristic algorithms to find the solutions is a reasonable time, in contrast to exact algorithms. In general, hybridization takes a longer time for some instances; for these instances, initially the solution accuracy was low, but it was increased when the iteration was increasing; there is a trade-off between the quality of solutions and their computational times. In other words, this study focused to solve single objectives related to optimization solutions of QAP within a reasonable computing time.


## 7. Conclusion and Discussion

The quadratic assignment problem (QAP) has attracted researchers’ attention, and they continue to be interested in developing methods and techniques to find a solution for the problem. Their interest is due to the QAP’s practical importance, which can be used in many real-world applications that can be modeled as a QAP. These include the layouts of hospital facilities and campuses. This study focused on proposing a hybrid algorithm based on algorithms after having critical analysis of studies and the conceptual framework.The purpose of this process is to balance the two main components in metaheuristic approaches: exploitation and exploration. On the other hand, certain issues, such as premature convergence, stagnation, and exploitation mechanism, have not been studied in the discrete differential evolution (DDE) algorithm to solve the QAP. Therefore, we introduced an enhanced algorithm that addressed existing issues. So, we developed a new hybrid algorithm, HDDETS, by combining the DDE and tabu search (TS) algorithms.From a computational perspective, our algorithm has proven its efficiency by finding the optimal solution within a reasonable computational time. It is found that the HDDETS algorithm is better than both the DDE and TS algorithms where the HDDETS has obtained 42 optimal and best-known solutions from 56, while the DDE and TS algorithms have obtained 15 and 18 optimal and best-known solutions out of 56, respectively. In the application domain of the QAP, the proposed HDDETS algorithm is used in Azadi Hospital in Iraq to find the best distribution of the hospital’s rooms. The rooms are modeled as a QAP to reduce the total distance traveled by patients. During this study, several directions emerged that can be considered good seeds for future research. According to this study, the following research directions are promising:(i)
Applying our hybrid metaheuristic algorithm, HDDETS, to multiobjective quadratic assignment problems(ii)
Hybridizing other local search algorithms with the DDE algorithm, such as the simulated annealing algorithm(iii)
Solving other combinatorial optimization problems, such as the scheduling problem and the vehicle routing problem by using our hybrid metaheuristic algorithm, HDDETS



---

*Source: 6653056-2021-03-17.xml*