Search

Although statistical solutions to Quadratic Assignment Problems (QAP) have been accessible for some time, the increasing application of Evolutionary Algorithms (EAs) to similar challenges provides a mechanism for handling QAP with extremely broad scope. The primary contribution of the study is that it normalizes all the criteria into a single scale, irrespective of their measurement units and the demand of minimum or maximum, freeing up the researchers from the burden of meticulously quantifying the quality criteria. A tabu search algorithm for quadratic assignment issues is proposed (TSQAP), which combines the constraints of tabu search with a discrete assignment problem. The effectiveness of the suggested algorithm has been compared to certain well-established approaches, and its working principle is explained with a numerical example. After repeating the solution of each issue (8) once and recording the algorithm results, it showed its agreement, once from a total (375) a repetition of the experiment while the number of times the Artificial Bee Colony (ABC) arrived (2) as for the Firefly (FA) Algorithm giving (117), also Genetic (GA) and Particle Swarm (PSO) gives (120) and the Tabu Search algorithm (136). The proposed technique (TSQAP) is shown to yield a superior solution with low computing complexity. MATLAB was used to generate all of the findings (R2020b). [ABSTRACT FROM AUTHOR]

Iterated Local Search (ILS) is one of the classical metaheuristics that is frequently used for solving the Quadratic Assignment Problem (QAP), a commonly studied NP-hard combinatorial optimization problem. Despite the effectiveness shown by the ILS when solving the QAP, many possible enhancements can still be implemented, based on studies conducted on other combinatorial problems, for example vertex coloring problem, vehicle routing problem, network design optimization, and many others. Among possible approaches for improving the ILS are by implementing adaptive ILS and multi-start strategy. Adaptive ILS is implemented by dynamically changing the perturbation strength of ILS during the run, which focus on developing a robust algorithm that can solve a wide range of instances. Multi-start strategy on the other hand, focus on applying restart or diversification during ILS run to prevent early stagnation. Adaptive ILS with frequent and large perturbation strength change has shown the best overall result when it has obtained the lowest deviation to the best-known solution compared to others. Implementation of Multi-start strategy showed bad performance, except on Taillard75e instance, in which it frequently found the best-known solution compared to others. Both adaptive and multi-start strategy have shown interesting results that may be further studied for ILS improvement. [ABSTRACT FROM AUTHOR]

Quadratic Assignment Problem (QAP) is one of the famous combinatorial optimization problems in operational research field. In this problem, a set of facilities is assigned to a set of locations in form of one-to-one assignment with the goal to obtain minimum assignment cost. Since QAP is classified under NP-hard problem, a metaheuristics approach is more appropriate for finding a good solution especially when the problem size increased. Sine Cosine Algorithm (SCA) can be categorized under population-based method which shown such an excellent performance in solving various optimization problem. SCA came up with high quality solutions and performed well due to its ability in stabilizing between exploration and exploitation phases evenly during the search process for optimal solution. However, this approach is rarely used to solve discrete optimization problem such as QAP. This is because the nature of its solution search which produce continuous values for new solution based on the concept of sine cosine principle makes it challenging in solving discrete optimization problem. Hence, this study aims to modify the SCA on its acceptance criteria based on the concept of sine cosine to solve discrete optimization problem, to solve QAP and evaluate its solution performance. The instances from QAPLIB were tested. The computational results shows that the modified SCA is an effective and superior method in solving QAP when compared to the best-known solutions presented in previous studies. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem is one of the most studied combinatorial optimization problems. Although many direct and heuristics methods exist for solving this problem, it takes a huge amount of time. Metaheuristics give an approximate solution in a feasible time. Therefore, we used a highly parallel iterated local search metaheuristic on a massively parallel graphics processing unit (GPU) to reduce the execution time. We utilized GPU spatial memory-global, local, constant, texture, and shared memory properties to further reduce the execution time. In this study, we found that using efficient utilization of GPU memory properties, and mixing different memory together we obtained better results from using only global memory. [ABSTRACT FROM AUTHOR]

Some local search methods (LSMs) for solving the Quadratic Assignment Problem (QAP), which is considered an NP-hard problem, are proposed in this paper. The aim of the problem is to minimize the sum of the distances multiplied by the corresponding flows by assigning the same number of facilities to the same number of different locations. Tabu search (TS) and Bees Algorithm (BA) are two suggested LSMs for solving QAP. We compared the results of LSMs with the complete enumeration method (CEM) and some strong heuristic methods in the first part of this paper. The results studied the existence of TS and BA in resolving our problem. The second part is split into two sections. As a practical application, we solve the QAP represented by civil engineering for Al-Zahra hospital in Kut/Iraq in the second part. The discussed methods are used to find the optimal and approximation solutions for this problem. [ABSTRACT FROM AUTHOR]

The simplest model of multi-objective quadratic assignment problems, bi-objective quadratic assignment problem, is discussed in this paper. Weighted sum method is used in order to change the multi-objectives model into single-objective model. An algorithm inspired from the foraging strategy and gliding mechanism called squirrel search algorithm is proposed to solve this problem. The squirrel search algorithm parameters, such as number of iterations, number of flying squirrels and control parameter, predator presence probability, are observed by managing computational experiment to solve bi-objective quadratic assignment problem. The computational results show that general parameters, number of iteration and flying squirrels, affect the performance of the algorithm in solving this problem. Moreover, probability of predator presence which is as control parameter in this algorithm can bring better result when using smaller value of probability. [ABSTRACT FROM AUTHOR]

Various Simulated Annealing (SA) variants have been proposed that differs from each other, mainly due to differences in their temperature schedule. Implementing different temperature schedules allow SAs to focus their intensification and diversification process at different regions in the search space. We focus on studying how the different temperature schedules proposed by different authors affect the performance of SA for solving selected Quadratic Assignment Problem instances. Results are presented in terms of percentage deviation compared to the best-known solutions already published. Our experimental results show that the temperature schedule does have a significant influence on the relative performance of different SA variants. [ABSTRACT FROM AUTHOR]

Since the formal introduction of metaheuristics, a huge number Quadratic Assignment Problem (QAP) instances have been introduced. Those instances however are loosely-structured, and therefore made it difficult to perform any systematic analysis. The QAPLIB for example, is a library that contains a huge number of QAP benchmark instances that consists of instances with different size and structure, but with a very limited availability for every instance type. This prevents researchers from performing organized study on those instances, such as parameter tuning and testing. In this paper, we will discuss several hard instances that have been introduced over the years, and algorithms that have been used for solving them. [ABSTRACT FROM AUTHOR]

Quadratic Assignment Problem (QAP), like Vehicle Routing Problem, is one of those optimization problems that interests many researchers in the last decades. The Quay Management Problem is a specific problem which could be presented as a QAP which involves a double assignment of customers and products toward loading positions using lifting trucks. This study focuses on the routing problem while delivering the customers' demands. In this problem, lifting trucks will route around the storage sections to collect the products then deliver to the customers who are assigned to specific loading positions. The objective of minimizing the residence time for each customer is sought. This paper presents the problem and the proposed model. [ABSTRACT FROM AUTHOR]

A stable set of a graph is a set of mutually non-adjacent vertices. The determination of a maximum size stable set, which is called maximum stable set, and the determination of its size, which is called stability number, are central combinatorial optimization problems. However, given a nonnegative integer k, to determine if a graph G has a stable set of size k is NP-complete. In this paper we deal with graphs for which the stability number can be determined by solving a convex quadratic programming problem. Such graphs were introduced in [13] and are called graphs with convex-QP stability number. A few algorithmic techniques for the recognition of this type of graphs in particular families are presented. [ABSTRACT FROM AUTHOR]